close

Вход

Забыли?

вход по аккаунту

?

bd000101459

код для вставкиСкачать
, Аt
На правах рукописи
МАЛИКОВ АНДРЕЙ ВАЛЕРЬЕВИЧ
ПРОЕКТИРОВАНИЕ И ИССЛЕДОВАНИЕ СВОЙСТВ РЕЛЯЦИОННЫХ
БАЗ Д А Н Н Ы Х , Н О Р М А Л И З О В А Н Н Ы Х НА О С Н О В Е О П Е Р А Ц И Й
ВЫБОРКИ И СОЕДИНЕНИЯ
Специальность 05.13.18 - Математическое моделирование, численные методы и
комплексы программ
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
доктора технических наук
Ставрополь - 2005
Работа
выполнена
в Северо-Кавказском
государственном
техническом
университете.
Научный консультант: доктор технических наук, профессор
Чефранов А . Г .
Официальные оппоненты: доктор технических наук, профессор
Кузнецов С Д .
доктор технических наук, профессор
Смирнов С . Н .
доктор технических наук, доцент
Кандаурова Н.В.
Ведущая
организация:
Московский
инженерно-физический
институт
(государственный университет), М И Ф И , г. Москва
Защита состоится « 23 » декабря 2005 г. в 14"° часов на заседании
диссертационного
совета
Д М 212.245.09
при
Северо-Кавказском
государственном
техническом университете
по адресу:
г. Ставрополь,
пр. Кулакова, 2, конфе[>енцзал.
С диссертацией можно ознакомиться в библиотеке Северо-Кавказского
государственного технического университета.
Автореферат разослан « 7 3 »
Н-о-сирчй^
2005 г.
Отзывы на автореферат в двух экземплярах, заверенные печатью
организации, просим направлять по адресу: 355000, Ставропольский край,
г. Ставрополь, пр. Кулакова, 2, Северо-Кавказский государственный технический
университет.
Ученый секретарь
диссертационного совета
к.ф.-м.н., доцент
/^А^-^'С^'У.^
^-^^ Мезенцева
<^1^Р°'
^•оо^-ч
"iJoesB
*1%01KK\
3
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Анщаяьность темы. Деятельность человека во многом связана со сбором,
накоплением и обработкой информации. Бурное развитие и применение
компьютерной техники приводит к неуклонному росту объемов накапливаемой
информации и повышению требований к ее структуре и качеству. При этом
качество информации может оцениваться по целому раду критериев. Одним из
самых удачных инструментариев обрабопгки информации стала реляционная
теория,
представлжощая
собой
комплекс
математических
методов
проектирования и обеспечения функционирования реляционных баз данных
(РБД).
Необходимым условием эффективного использования РБД является
отсутствие аномалий обработки информации, которое достигается посредством
методики нормализации отношений. Стандартные методы нормализации,
основанные на реляционных операциях проекции и соединения, не позволяет
эффективно описывать произвольные предметные области (ПО) с полностью не
определенными структурами. Данная проблема имеет частичное решение в
случае дополнения классической реляционной теории методами моделирования
квазиструктурированной (полуструктурированной) информации. В этом случае
структуру П О рассматривают как обычные данные, к которым могут быть
применены операции манипулирования информацией: добавление, удаление,
изменение.
Несмотря на развитый математический аппарат, значительную программную
и информационную поддержку, множество прикладных реализаций, реляционной
модели данных npnofmn следующие основные недостатки:
1. Для разных уровней пользователей системы информация РБД
представляется различными уровнями абстракции. Как правило, конечный
пользователь (клиентское приложение) не в состоянии изменить набор и
струк1уру таблиц, вследствие изменения информации ПО: реляционная система
становится зависимой от прикладного программиста и администратора, что
сказывается на коммерческих свойствах системы.
2. Декларативные языки манипулирования данными, несмотря на
универсализм, чэляются языками уровня прикладного программиста и/или
администратора системы, но не конечного пользователя. Пользователь не
знающий структуры РБД не может сформулировать свой запрос, а если запрос
написан на языке SQL, то изменение структуры РБД влечет за собой его
переформулирование.
3. Наличие NULL-значений в таблицах и, вообще, трехзначная логика
усложняет бизнес-логику клиентских приложений.
Развитие математического аппарата реляционной теории с целью решения
указанных проблем представляется актуальной задачей. В диссертационной
работе проведено развитие и обобщение реляционной теории с целью
преодоления недостатков проектирования и обеспечения функционирования
классических РБД, для этого вводятся новые методы моделирования
квазиструктурированной информации, новые-нравила поддержания ссылочной
целостности, новые методы манипулирован!^! ^Щ^йЬ^Ией.-я ••ч - ,
! iFJnk^'^
—'
-^ it
4
Объектом исследования являются математические методы реляционной
теории управления большими объемами квазиструктурированной информации.
Научная задача заключается в разработке математических методов
эффективного управления большими объемами
квазиструктурированной
информации.
Цель и задачи работы. Целью настоящей диссертационной работы является
развитие и обоснование .математических методов реляционной теории для
эффективного управления большими объемами информации предметных
областей с полностью неопределенными структурами.
Для достижения поставленной цели были решены следующие задачи:
1. Проанализированы существующие методы реляционной теории
управления информацией, в том числе моделирование квазиструктурированных
данных.
2. Разработан формальный математический аппарат нормализации
реляционных отношений на основе операций выборки и соединения, в результате
чего была получена структура РБД, содержащей квазиструктурированные
данные.
3. Введено понятие роли реляционного отношения как идентификатора
отдельного ссылочного пути на любой паре отношений, на основе чего
спроектирована уточненная структура РБД, нормализованной на основе операций
выборки и соединения.
4. Определена методика проектирования РБД, нормализованных на основе
операций выборки и соединения. Определен алгоритм перевода ER-диаграмм в
полученную структуру.
5. Определены
правила
поддержания ссылочной
целостности
и
использования NULL-значений в РБД, нормализованных на основе операций
выборки и соединения.
6. Определены особенности языка манипулирования данными полученной
структуры. Определен синтаксис, BNF-грамматика, правила использования
инструкций языка.
7. Для инструкции выборки данных определены алгоритмы поиска
информации в Р Б Д нормализованных на основе выборки и соединения.
8. Определены
методы
проектирования
распределенных
РБД
нормализованных на основе операций выборки и соединения.
9. Определены методы администрирования доступа к информации РБД на
основе реляционной операции выборки.
10. Построена
математическая
модель
задачи
оптимизации
вычислительного процесса в многопользовательских системах обработки
информации и управления, построенных на основе РБД, нормализованных на
основе операций выборки и соединения.
И . Показаны результаты использования полученных результатов в
автоматизированных системах управления (АСУ) учебным процессом
Методы исследования. При решении поставленных в диссертационной
работе задач использовались* методы теории реляционной модели данных,
методы теории множеств, методы теории графов, методы математического
5
моделирования, методы теории вероятностей и математической статистики,
методы построения вычислительных систем и программирования.
Основные положения, выносимые на защиту. В работе получены и
выносятся на защиту следующие основные положения и результаты,
характеризующиеся научной новизной:
1. Методы моделирования квазиструктурированной
информации и
структурная часть РБД, нормализованных на основе операций выборки и
соединения.
2. Целостная часть РБД, нормализованных на основе операций выборки и
соединения.
3. Синтаксис, BNF-грамматика, правила использования инструкций языка
манипулирования да1шыми РБД, нормализованных на основе операций выборки
и соединения.
4. Алгоритмы поиска информации в РБД, нормализованных на основе
операций выборки и соединения.
5. Алгоритм перевода ER-диаграмм в структуру РБД, нормализованных на
основе выборки и соединения.
6. Алгоритмы перевода РБД в структуру баз данных, нормализованных на
основе операций выборки и соединения.
7. Методы проектирования распределенных РБД, нормализованных на
основе операций выборки и соединения.
8. Методы администрирования доступа к информации РБД на основе
реляционной операции выборки.
9
Комплекс программ проектирования и обеспечения функционирования
РБД, нормализованных на основе операций выборки и соединения.
10. Математическая модель задачи оптимизации вычислительного процесса
в многопользовательских системах обработки информации и управления,
построенных на основе РБД, нормализованных на основе операций выборки и
соединения.
Практическая ценность результатов диссертационной работы заключается
в создании программного комплекса (на платформе M S SQL Server 2000 +
Visual C#.NET), поддерживающего работу с нормализованными на основе
операций выборки и соединения РБД, модификация и анализ содержимого
которых доступны на уровне конечного пользователя. Тем самым существенно
повышаются скорость разработки, внедрения, модификации и сопровождения
приложений РБД.
Достоверность
полученных
результатов
работы
подтверждается
коррекгаым использованием теоретических и практических методов обоснования
полученных результатов. Основные выводы и положения диссертационной
работы обоснованы использованием при их получении известных. Проверенных
практикой моделирования на Э В М теоретических методов исследования,
базирующихся на принципах теории реляционной модели данных, теории
множеств, теории графов, теории вероятностей и математической статистики,
программирювания, а также применением разработанных методов при решении ■
конкретных задач предприятия, что подтверждается актами внедрения
результатов работы.
6
Реализация
и
внедрение результатов
работы.
Полученные
в
диссертационной работе результаты реализованы и внедрены:
1) в Северо-Кавказском государственном техническом университете
(СевКавГТУ) г. Ставрополя;
2) в филиалах СевКавГТУ в городах Невинномысске, Георгиевске,
Пятигорске, Кисловодске;
3) в Северо-Кавказском гуманитарно-техническом институте (СевКавГТИ)
г. Ставрополя;
4) в Народном Шпаковском Транспортном Предприятии (НШТП)
г. Михайловска.
Апробация результатов работы. Основные этапы работы докладывались и
обсуждались на 17 научных конференциях и семинарах. По итогам IV
Международной научно-технической конференции «Кибернетика и технологии
X X I века» (Воронеж, 2003 г ) работы награждены дипломом за лучший доклад
конференции.
Публикации. По теме диссертации автором опубликовано 49 печатных
работ.
Структура и объем работы. Материал основной части диссертационной
работы изложен на 210 страницах машинописного текста Диссертация состоит
из введения, семи разделов, заключения, списка литературы из 199
наименования, 27 рисунков, 34 таблиц и 5 приложений. Всего 256 страниц.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность представленных исследований,
сформулированы цели и задачи, решаемые в работе, изложены основные
положения, выносимые на защиту. Кратко рассмотрено содержание разделов
диссертации.
В первой главе проведен анализ литературных источников по теории
реляционной модели данных и методике проектирования и обеспечения
функционирования РБД. Определены понятия предмета исследования —
структурная часть, целостная часть и манипуляционная часть реляционной
модели данных, понятие сущности и взаимоотношения данных, нормальные
формы, квашструктурированные данные, реляционная алгебра, реляционные
операции, языки манипулирования информацией, архитектуры РБД.
Аналитический
обзор литературных
источников
показывает,
что
теоретическая
часть
реляционной
модели
данных
имеет
серьезное
математическое обоснование, фундаментом которой является теория множеств.
Всякая ПО может быть описана конечным набором реляционных отношений. В
этой связи РБД получили широкое распространение в различных областях
человеческой деятельности.
Любую систему РБД принято рассматривать как совокупность трех частей:
структурной, целостной и манипуляционной.
Структурная часть определяет понятия домена; отношения, построенного на
множестве доме1Юв; кортежей; атомарных значений. Определяет правила
использования системы ключей.
Целостная часть рассматривает вопросы согласования ключей отношений.
Определяются потенциальные, первичные, внешние ключи. Определяются
7
правила ссылочной целостности, необходимые для подцержания согласованных
копий внешних ключей, которые обычно представлены либо офаничением
выполнения, либо каскадным обновлением ключевой информации. Вводится
понятие NULL-значений.
Манипуляционная часть представлена реляционным исчислением, наиболее
значимыми видами которого являются исчисление кортежей и исчисление
доменов; и реляционной алгеброй, замкнутой на понятии отношения.
Для построения корректных РБД применяется методика нормализации
реляционных отношений. Нормализация отношений представляет собой
формализованный подход в виде аксиом и теорем нормализации, проектирования
схемы данных ПО.
Для доступа к информации РБД применяются специальные языки
манипулирования
данными,
среди
которых
предпочтение
отдается
декларативным языкам. В настоящее время наибольшее распространение
получил язык SQL.
Для повышения надежности реляционных систем и оперативности доступа к
информации могут быть реализованы различные подходы к архитектуре РБД,
такие как
файл-серверная, клиент-серверная архитектуры, реализация
п^аллельных и распределенных РБД. Для реализации распределенных и
параллельных
РБД
существует
несколько
подходов:
горизонтальная
фрагментация или вертикальная фрагментация таблиц, репликация данных,
комбинированные подходы.
В задачах обработки информации с нечетко определенной структурой
применяют моделирование квазиструктурированных данных, что позволяет
строить РБД стандартной структуры, при этом ПО представляется в виде графа.
Для
доступа
к
квазиструктурированным
данным
разработаны
специализированные языки: графовые языки G, G+ и GraphLog и языки запросов
к квазиструктурированным данным Lorel, UnQL, SfruQL, Y A T L , X Q L , Quilt, XQuery и др. Основное применение описываемые РБД нашли как средство
интеграции и преобразования данных из различных источников, например,
WWW-pecypcoB.
Во второй главе с целью описания ПО с полиостью неопределенными
структурами проектируется РБД на основе операций выборки и соединения.
Детальное изучение вопросов, связанных с проектированием и обеспечением
функционирования РБД, позволяет определить основные проблемы, связанные с
классической методикой нормализацией отношений на основе операций
проекции и соединения.
Проблема №1: определение полноты и законченности структуры РБД.
Связано это с тем, что изменение структуры информации на входе в
реляционную систему может менять структуру последней. Данная проблема
возникает вследствие того, что проектирование РБД начинается с отношения,
находящегося в первой нормальной форме (НФ), число атрибутов которого
является конечным числом. В случае достаточно полного описания ПО в
процессе эксплуатации РБД у различных сущностей могут проявляться новые
свойства, и вслед за ними должна меняться структура определенных отношений.
Появление новьк атрибутов отношений приводит к пересмотру зависимостей
между атрибутами и непременному изменению структуры отношений. Под
изменениями структуры РБД понимается выполнение операций добавления и
удаления таблиц, а также изменение структуры таблиц: добавление, удаление
столбцов и переопределение доменов. Как правило, пользовательский интерфейс
приложений не в состоянии справится с поставленной задачей, и конечным
пользователям РБД приходится обращаться за помощью разработчиков В
действительности описываемая проблема является еще более широкой:
1. Реляционные системы проектируются таким образом, что конечному
пользователю доступны лишь операции по изменению содержимого строк
таблиц- добавление, удаление строк и изменение их содержимого. Аналогично
определяется бизнес-логика приложений и разрабатывается пользовательский
интерфейс доступа к данным.
2. Изменение структуры таблиц приводит к пересмотру бизнес-логики и
внесению изменений в пользовательские приложения.
3. Из-за различия выполняемых функций реляционная система интуитивно
воспринимается по-разному на различных уровнях абстракции: разработчика
РБД, программиста приложений, конечного пользователя.
Проблема №2
наличие NULL-значений в таблицах. Разрешение на
использование ^fULL-знaчeний для описания отсутствующей информации
приводит к пересмотру бизнес-логики приложений. Использование NULLзначений в полях ключей усложняет контроль целостности реляционных систем
и приводит к пересмотру правил ссылочной целостности.
Проблема №3: отсутствие прямого отображения иерархических сущностей и
взаимосвязей типа «многие-ко-многим». Реляционная модель решает эту
проблему посредством дополнительных соглашений об использовании системы
ключей. При отображении сущности ПО, представляющей собой иерархическую
структуру, в таблицу РБД, согласно определению внешнего ключа, добавляется
дополнительный атрибут, являющийся внешним по отношению к первичному
ключу этой же таблицы, либо используют множественную модель деревьев.
Между объектами реального мира достаточно часто встречаются взаимосвязи
типа «многие-ко-многим», которые'непосредственно не могут быть отражены в
реляционной системе. Разработчикам в такой ситуации приходится создавать
дополнительные таблицы, содержащие первичные ключи исходных таблиц.
Таким образом, взаимоотношения типа «многие-ко-многим» заменяются
совокупностью взаимоотношений типа «один-ко-многим».
Любая ПО может быть отображена в реляционной системе конечным числом
отношений, находящихся как минимум в 1НФ. Таким образом, при
проектировании РБД разработчик взаимодействует одновременно с двумя ПО:
\. Экспертная ПО, для которой требуется построить, по возможности,
правдоподобную модель. Будем называть данную ПО — внутренней.
2. ПО реляционной модели данных. Будем называть данную ПО —
внешней.
Если внутренние ПО могут значительно отличаться друг от друга в
различных реляционных системах, то внешняя остается постоянной и обладает
строго определенными свойствами, описанными в теории реляционной модели
данных. Возможность нормализации внешней ПО позволит формализовать
9
работу групп разработчиков и решить представленные ранее проблемы
проектирования и обеспечения функционирования РБД.
Минимальной информационной единицей реляционной системы является
атомарное значение единичного атрибута отдельного отношения. Любое такое
атомарное значение согласно определениям понятия зависимости, если не
является независимым, то вступает в некоторые отношения со значениями других
атрибутов. Зависимости могут быть одного из следующих типов:
• функциональные зависимости;
• транзитивные зависимости;
• многозначные зависимости;
• зависимости соединения.
На множестве атомарных значений ПО можно построить ориентированный
граф связей:
G = iV,E),
где V — конечное множество вершин (атомарных значений);
Е — множество упорядоченных пар (дуг) на V, т.е. подмножество
множества VxV; Е определено на множестве связей атомарных значений.
' Основой построения ориентированного графа связей атомарных значений
является семантика исследуемой ПО. Условимся подписьгаать вершины
значением атрибутов и обозначать дугой e-{u,v), ведущей из вершины и в
вершину V: (и -> v) ситуацию уточняющей связи от значения потомка к значению
родителя.
Пусть в некоторой ПО определено конечное мтюжество атомарных значений
K = {v,,Vj,. ,v„}. На множестве V строится граф G, определяющий все связи
ff = {«■,,«2,.. ,е„}. Множество Е является конечным в силу конечности V. Подграф
графа связей G без потери общности может быть представлен в виде рисунка 1.
Рисунок 1 - Представление связей подмножества из 5-ти атомарных значений в
виде ориентированного графа
Построение фафов связей является альтернативным
графическим
представлением зависимостей между атомарными значениями ПО и с учетом
всех значений может обладать достаточно сложной структурой. Учитывая
сложности построения и машинной обработки графов, связи между атомарными
значениями атрибутов отношений РБД можно представить в виде отдельного
реляционного отношения.
10
Построим плоское отношение D, с размерностью тела 2х(я» + п'), где п' число несвязанных атомарных значений (подвешенных вершин), такое, что:
•
в первый столбец снесены вершины v, такие, что (v, е r{v^))u (v, t /'(vj);
•
во второй столбец снесены вершины v^ такие, что Vj € r"'(v,).
Заголовок отношения D представляет собой строку заголовков столбцов и
содержит фиксированное множество пар
<имя-атрибутагшя-домена>:
{<А1 •D1>,<A2:D2>}, причем каждый атрибут Aj соответствует одному и только
одному из лежащих в основе доменов Dj (j-1.2). Домен /)/ определяет множество
атомарных значений ПО, при этом D,<zD^, так как справедливо D^. {D,,NULL).
Искомое отношение D будет иметь вид таблицы 1. В ячейках таблицы 1
присутствуют NULL-зиачения для обозначения ситуации, когда конкретное
атомарное значение не зависит от других значений рассматриваемой ПО. В этой
связи кардинальное число к отношение D равно к = т + п' ,к от = 0 при л' = «.
Таблица 1 - Отношение связей атомарных значений
Значение
VI
V/
Определено значением
v,«
V/+;
V/+2
V,4
NULL
VM
VlU
V,+J
Vi4
V/И
VM
v,+<
Рассмотрим множественную модель РБД. Пусть А - множество отношений,
В - множество атрибутов. Всякая ПО определяется как подмножество Р/
декартово произведения AxB^VxE: Р,С{АХВ\УХЕ),
при этом структура РБД
определяется как подмножество P j декартово произведения Ах В: Р^^{АХВ).
В
общем случае, множество атомарных значений есть многозначное соответствие
на множестве Рг {/-У-^Рг), т.к. реляционные отношения могут быгь не
достаточно нормализованы. Но даже при полной нормализации отношений, при
когорой всякое атомарное значение присутствует в РБД один раз, избыточное
дублирование атомарных значений будет присутствовать в ключевых атрибутах
при установлении соответствия внешних ключей первичным. В общем случае
РБД состоит из четырех частей: отношение, связь, атрибут, значение атрибута; и
может быть представлена в 1НФ с конкретными значениями указанных частей в
виде таблицы 2. Отношение D, представленное в таблице 1, дополнено
атрибутами:
fIDz
(простой
идентификатор),
IDch
(дочерний ключ),
Юраг (родительский ключ), отношение, атрибут}; связи между атомарными
значениями описаны с помощью введенных атрибутов (IDch, IDpar}. Очевидно,
что после преобразования D: P,=D. В таблице 2 представлены абстрактные
данные о некоторой РБД. Без потери общности принадлежность атомарных
значений к отношениям и атрибутам представлена условно. Атрибут /Dz является
и
простым первичным ключом отношения D. Двойка {IDch, IDpar) является
альтернативным первичным ключом отношения. Атрибут IDch является простым
идентификатором атрибута значение.
Таблица 2 - Представление внешней предметной области в I Н Ф
IDz
IDch
п
п+1
п+2
п+3
1
1
2
3
4
4
5
п+4
п+5
п+6
ГОраг
4
2
3
NULL
5
2
3
...
Отношение
Атрибут
Значение
Of
А,
А,
V,
Ai+i
v,+;
AHI
VM
AM
V,*3
О,
о,„
Ом
0,
О,
Ом
Анг
Анз
VI
Vi*}
Viu
Представленное отношение, назовем его связь, находится в 1НФ, так как в
его полях отсутствуют повторяющиеся группы. Отношение связь (IDz, IDpar,
Отношение, Атрибут, Значение, IDch} содержит атрибуты:
•
IDz — пфвичный ключ, идентификатор связи (в простейшем случае —
счетчик). Связь двух значений атрибутов в модели данных внутренней ПО
представлена двойкой {IDpar, IDch}, т.е. всякое значение может быть определено
ноль, одним и более други.ми значениями и оно само может определять ноль,
одно и более значений. Допустимо описание связей атомарных значений другими
способами, например, множественной моделью деревьев. Двойка {IDpar,
IDch} — это формализованное описание реляционной зависимости любого рода.
•
Отношение — информативный атрибут, определенный на домене
множества отношений внутренней ПО.
•
Атрибут
— информативный атрибут, определенный на домене
множества атрибутов отношений внутренней ПО.
•
Значение — информативный атрибут, определенный на домене
множества атомарных значений атрибутов отношений внутренней ПО.
•
IDch — идентификатор атомарного значения, на которое могут
ссылаться другие значения (в простейшем случае — счетчик).
•
IDpar — идентификатор родительского значения, на которое ссылается
некоторое значение, указанное в IDch. ^ШLL-знaчeния в полях данного атрибута
означают независимость некоторого атомарного значения внутренней ПО от
других значений. Ситуацию независимости значения можно смоделировать
посредством указания ert) идентификатора в каждом из атрибутов подмножества
{IDpar, IDch}. Последний способ является более предпочтительным, т.к., вопервых, позволяет полностью отказаться от использования в РБД NULLзначений, во-вторых, позволяет напрямую выполнять операцию соединения
связанных отношений по атрибуту IDpar. В противном случае при использовании
инструкций запросов к РБД независимые атомарные значения ПО можно выбрать
только подзапросом.
12
Таким образом, основная идея проектирования РБД заключается в
построении плоского отношения зависимостей между атомарными значениями
внутренней ПО и последующей его нормализации. Проведение стандартной
процедуры нормализации отношения D позволяет определить структуру РБД,
представленную на рисунке 2.
Полученные в процессе нормализации результаты очень хорошо
согласуются с реляционными моделями, содержащими квазиструктурированные
данные. Анализ полученной схемы показывает, что основными объекгами ПО
реляционная модель данных являются отношения, атрибуты,
атомарные
значения, связи атомарных значений. Спроектированная структура обладает
двумя основными недостатками. Во-первых, она не совсем адекватно описывает
особенности ПО, т.к типы всех связей между объектами предполагаются «одинко-многим». Такие связи являются частным случаем связей «многие-ко-многим».
В
общем случае сущности атрибут
и атомарное значение связаны
взаимоотношением «многие-ко-многим»: одному атрибуту могут принадлежать
несколько атомарных значений и одно атомарное значение может принадлежать
нескольким атрибутам. Во-вторых, между отношениями внутренней ПО может
существовать более одного ссылочного ограничения. Эти ссылочные
ограничения могут быть как сонаправленными, так и циклическими. В
полученной структуре данная информация потеряна, поэтому описанный ранее
метод нормализации отношения связей атомарных значений требует доработки, а
полученная модель уточнения структуры.
Связь
*IDz
Сраг
IDch
Отношение
•Do
Отношение
Значение
•IDch
Da
Значение
Рисунок 2 - ER-диаграмма ПО реляционная модель данных
В
третьей
главе
рассматриваются
основные
свойства
РБД,
нормализованных на основе операций выборки и соединения.
Показано, что восстановление отношений внутренней ПО осуществляется
посредством операций выборки и соединения, т.е. представленная модель данных
является «выборочно-соединительной».
Пусть существует отношение R {А, В, С}, соответствующее внутренней ПО,
содержащее кортежи {{al, Ы, с1}
{an, bn, en}}, тля п — кардинальное число R.
Пусть согласно проекционно-соединительной теории нормализации R (А, В, С}
может быть заменено проекциями: {А, С} и {А, В}. Исходное отношение R может
быть восстановлено как соединение {А, С} и {А, В} по атрибуту А.
13
в структуре, представленной на рисунке 2, Л {А, В, С} заменяется
совокупностью кортежей: отношение {l.R}, атрибут {{1,1,А}, {2,1,В}, {3,1,С}},
значение
{{1,1,а1}, {2,2,Ы}, {3,3,с1},...,{т-2,1,ап}, {т-1,2,Ьп}, {т,3,сп}},
где
т<3*п, И Связь {{1.1,2}, {2,1,3}
{1-1,т-2,т-1},{1,т-2,т}}, где /s2*/i. Здесь и
далее, для простоты представления информации, в качестве первичного ключа
отношений внешней ПО используются уникальные значения счетчика.
Физический смысл неравенства т<ъ*п
заключается в следующем.
Максимальное число атомарных значений отношения R {А, В, С} составляет а*п,
где а=3 — степень R. Пусть t — число NULL-значений в полях атрибутов, не
являющихся первичным ключом. В модели, представленной на рисунке 2, NULLзначение в поле атриб)аа отношения внутренней ПО не заносится в отношение
значение, т.е. не добавляется новый кортеж в значение и соответственно в связь.
Таким образом, число кортежей отношения значение т составляет m = a*n-i или
т<.Ъ*п, аналогично для числа кортежей / отношения связь справедливо 1йЬ*п,
где Ь=2 — число зависимостей в одном кортеже Л.
В данной постановке отношение R {А, В, С} восстанавливается как
соединение по атрибуту значение выборки значение.значение из соединения по
совпадающим ключам отношений отношение, атрибут, значение, связь для
отношение.omHouteHUC^R и/или {атрибут.атрибут=А,
атрибут.атрибут=В,
атрибут, атрибут =С/.
№ SQL запрос имеет вид:
S E L E C T а.Значение as А, Ь.Значение as В, с.Значение as С
F R O M связь,
( S E L E C T Значение.* F R O M Значение, Атрибут W H E R E
Атрибут.Атрибут='А' and Значение.ГОа=Атрибут.ГОа) а,
( S E L E C T Значение.* F R O M Значение, Атрибут W H E R E
Атрибут.Атрибут='В' and Значение.ГОа=Атрибут.П5а) Ь,
( S E L E C T Значение.* F R O M Значение, Атрибут W H E R E
Атрибут.Атрибут='С' and Значение.ГО»=Атрибут.ГОа) с,
W H E R E а.ГОсЬ=связь.ГОсЬ and Ь.ЮсЬ=связь.10раг and с.11)сЬ=связь.ГОраг
Пусть
согласно проекционно-соединительной теории нормализации
отношение R {А, В, С} без потери информации может быгь заменено проекциями:
Х{А, С}, состоящим из кортежей {{al, с1},...,{ах, сх}}, х<,п и Y{А, В}, состоящим
из кортежей {{at. Ы },...,{ау, by}}, у<.п. Значит, данная операция должна быть
выполнима по отношению к структуре, представленной на рисунке 2.
Действительно, после нормализации в новую структуру занооггся кортежи:
отношение {{1,Х}, {2,Y}}, атрибут {{1,1,А}. {2,1.С}, {3.2,А}, {4,2,В}}, значение
{{l.l.al}, {2.2.С1}
{2х-1,1,ах}, {2х,2,сх}, {2х+1,1,а1}, {2х+2.2,Ы}
{у'-1,1,ау},
{у'.г.Ьу}},
/ = 2дг + 2^,
и
Связь {{1,1.2}
{х,2х-1.2х}.{х-\-1,2х+1,2х+2}
{yV2,y:i.y'}}.
В данной постановке отношение R {А, В, С} восстанавливается как
соединение по атрибуту значение двух выборок, таких что:
•
выборка 1 — выборка значение.значение из соединения по совпадающим
ключам
отношений
отношение,
атрибут,
значение,
связь
для
отношение, отношение =Х;
14
•
выборка 2 — выборка значение значение из соединения по совпадающим
ключам
отношений
отношение,
атрибут,
значение,
связь
для
отношение. отношение=¥.
На S Q L запрос имеет вид:
S E L E C T <1.3начение as А, д.Значение as В, с.Значение as С
F R O M связь связь!,
( S E L E C T а.3начение as А, Ь.Значение as В, a.IDch
F R O M связь,
( S E L E C T Значение.* F R O M Значение, Атрибут, Отношение W H E R E
Отношение.Отношение='Х' and Отношение.ГОо=Атрибут.Шо
and Атрибут.Атрибут='А' and Значение.1Е)а=Атрибут.ГОа) а,
( S E L E C T Значение.* F R O M Значение, Атрибут, Отношение W H E R E
Отношение.Отношение='Х' and Отношение.ГОо=Атрибут.Юо
and Атрибут.Атрибут='В' and Значение.ГОа=Атрибут.Юа) Ь,
W H E R E a.IDch=CBH3b.IDch and Ь.ГОсЬ=связь.ГОраг) d,
( S E L E C T Значение.* F R O M Значение, Атрибут, Отношение W H E R E
Отношение.Отношение='У and Отношение.ГОо=Атрибут.ГОо and
Атрибут.Атрибут='С' and Значение.Юа=Атрибут.Ша) с
W H E R E d.IDch=cвязьLIDch and с.ГОсЬ=связь1.ГОраг
В отношениях выборочно-соединительной реляционной модели данных не
используются NULL-значения для обозначения отсутствующей информации.
Пусть существует отношение R {А, В, С} соответствующее внутренней ПО,
содержащее кортежи {{al,bJ,clJ,...{ai,bi.NULL},...,{an,hn,cnJJ,
где п —
кардинальное число R. Пусть согласно проекционно-соединительной теории
нормализации R {А, В, С} может быть заменено проекциями: {А, С) и {А. В}.
Исходное отношение Я может быть восстановлено как соединение {А, С} и {А, В}
по атрибуту А.
В структуре, представленной на рисунке 2, R {А, В, С} заменяется
совокупностью кортежей отношение {1,R}, атрибут {{1,1,А}, {2,1,В}, {3,1,С}},
значение
{{1.1,а1}, {2,2,Ы}, {3,3.с1}
{i'-l,l.ai}, {Г.2,ы}
{т-2,1,ап}. {т1,2,Ьп}, {т,3,сп}}, где т<7>*п, и свюь {{1,1,2}, {2,l,3),...,{i",i',i'-l},...,{l-l,m-2,m1),{1,т-2,т}}, где /<2*л. При таком подходе число кортежей значение и связь
уменьшается. В данном случае содержимое отношений предложенной структуры
будет
следующим:
отношение
{{1,Ю> {2,У}},
атрибут
{{1,1.А), {2,1,С}, {3,2,А}, {4,2,В}},
значение
{{1.1,al}, {2,2.с1}....,{2х-1,1,ах}.
{2х.2,сх}, {2х+1,1,а1), {2х+2,2,Ы)
{j-l3,ai},{i,4,bi},...{y'-l,l,ay}.
{y;2,by}),
и
связь {{1.1,2}....,{х,2х-1,2х},{х+1,2х+1,2х+2}
{j'J-U}.-{y'/2,y--l.y-}}.
Для корректного отображения объектов реального мира в выборочносоединительной реляционной модели данных должны выполняться правила
ссылочной целостности. При этом достаточно выполнения правил ссылочной
целостности для отношений внешней ПО, правила ссылочной целостности для
внутренней ПО вводятся дополнительно на основе операций выборки и
соединения. Для внешней ПО, как нормализованной классическим образом,
должны быть определены правила внешних ключей. Эти правила определяются
для множества первичных ключей {IDo, IDa, IDpar, IDz} и соответствующих им
внешних ключей.
15
Для
ссылочного
пути
связь—>значение—>атрибут—>отношение
целесообразно установить правило каскадирования операций удаления и
обновления.
В качестве второй системы ключей представленной реляционной структуры
может выступать система ключей внутренней ПО, которая после процедуры
нормализации будет преобразована в множество кортежей отношения атрибут.
Соответствующие значения ключей отношений внутренней ПО будут
преобразованы в кортежи отношений значения, связи - в кортежи отношения
связь. В результате образуется две системы ключей:
•
Система ключей внутренней ПО, представленная кортежами отношений
атрибут, значение, связь. В данном случае правила ссьыочной целостности,
помимо указанных ранее, должны накладываться на кортежи отношения связь.
•
Система
ключей
внешней
ПО,
представленная
атрибутами
{Юо. Юа. Юраг. IDzJ.
Таким образом, всякое атомарное значение информативного атрибута
отношения внутренней П О в любой момент времени зависит по ссылке от
атрибута первичного ключа отношения из множества (Юо, Юа, Юраг, Юг} и от
значения соответствующего кортежа, которое является первичным ключом
отношения внутренней ПО, представленного в виде кортежа в связь. Если уже
определены правила ссылочной целостности для отношений внешней ПО, то
вторая система ключей может быть удалена из системы. При этом следует ввести
дополнительные офаничения:
1. Отношение связь должно быть перестроено для отображения
зависимостей значений информативных атрибутов внутренней ПО от ключей
внешней П О (Юраг. ЮсН).
2. В о внутренней ПО могут существовать особые возможности
согласования системы ключей отношений. Эти правила должны накладываться
на выборки ключей из отношения связь.
Второе замечание является очень важным при выборочно-соединительном
подходе к нормализации. Пусть существуют два отношения внутренней ПО R1
{А}, где А — информативный атрибут, содержащее кортежи {al,...,ai}, и R2 {В},
где В — информативный атрибут, содержащее кортежи {bl,...,bj}. При этом
объекты (bl,...,bj} некоторым образом зависят от {al,...,ai}, т.е. R2—>R1.
Согласно предложенной структуре имеем: отношение {{l,Rl}, {2,R2}}, атрибут
{{/,1,А},{2.2,В}}, значение {{l,l,al},...,{i.l,ai}.
{i+l,2.bl}.....{i+j,2,bj}},
и связь,
например, {{1,1,1+1},. .,{x,i,i+j}}. Ограничение ссылочной целостности должно
быть наложено на выборки из связь, связанные с выборками по первичному
ключу Юраг из значение {l,...,i}—>{i+l, -...i+j}Пусть выполняется операция удаления кортежа отношения значение.
Согласно последнему определению предварительно должна бьггь выполнена
операция выборки из связь по первичному ключу Юраг, соответствующему
удаляемому кортежу. Возможны 3 варианта удаления:
1. Операция удаления только первоначального кортежа проводится тогда и
только тогда, когда выборка пуста.
2. Из значение удаляются дополнительные кортежи по ключу ЮсН тогда и
только тогда, когда действует правило каскадного удаления для отношений
16
внутренней ПО и выборка не пуста. Программно каскадирования операции
удаления кортежей из значение организуется с использованием механизма
рекурсии.
3. Операция удаления ограничивается тогда и только тогда, когда
действует правило ограничения удаления для отношений внутренней ПО и
выборка не пуста.
Аналогично определяются правила дня операции обновления
Определены домены атрибутов отношений РБД, нормализованных на основе
операций выборки и соединения.
В
четвертой
'главе
проектируется
уточненная
структура
РБД,
нормализованных на основе операций выборки и соединения.
Приводится формальный алгоритм перевода ER-диаграммы внутренней ПО
в выборочно-соединительную РБД:
1
Определяются типы взаимоотношений между сущностями. Все
взаимоотношения типа «один-к-одному», «один-ко-многим», «мпогие-комногим» и иерархические взаимоотношения между сущностями ПО не
изменяются.
2. Для сущностей, не содержащих информативных атрибутов, могут быть
введены дополнительные атрибуты. В противном случае сущность не
преобразуется в РБД, а для поддержания целостности соответствующих данных
будет использоваться система ключей внешней ПО
3
Выбирается система ключей внешней ПО, в качестве которой могут
быть выбраны значения счетчиков для атрибутов flDo, IDa, IDpar, IDzj.
4. Для каждой сущности ER-диафаммы создается кортеж в отношении
отношение.
5. Для каждого атрибута создается кортеж в отношении атрибут,
связанный с соответствующим кортежем отношения отношение. После
выполнения данного этапа создается структура внутренней ПО.
6. При заполнении полученной структуры создаются кортежи в отношении
значение, связанные с соответствующими кортежами в отношении атрибут.
1. При
заполнении
отношения
связь
руководствуются
типами
взаимоотношений между соответствующими сущностями ER-диаграммы.
В РБД нередко встречаются особые случаи связей пар отношений, когда в
дочернем отношении присутствуют более одного внешнего ключа по отношению
к первичному ключу родительского отношения, или существует несколько
альтернативных ссылочных путей между двумя отношениями. В таких случаях
родительское отношение выступает одновременно в нескольких ролях по
отношению к дочернему отношению. Под ролью будем понимать описание одной
такой конкретной связи
В разработанной ранее структуре РБД (рисунок 2) отношение связь
построено из «безликих» зависимостей между значениями атрибутов отношений.
Реализация возможности существования более одной связи между отношениями
должна быть проведена за счет системы ключей внешней модели Для этого
должны быть проведены дополнительные изменения структуры, за счет
дополнения отношения D, представленного в таблице 2, информативным
атрибутом
Роль
Нормализация
полученного
отношения
проводится
17
классическим методом на основе операций проекции и соединения. В результате
нормализации получим РБД со структуррй, представленной на рисунке 3.
Связь
RVb
'tea
Сраг
(Dch
•СГ
[
Значение
♦IDzn
Значение
+—о
Do
ii
Значение_атрибу1 ■о—(■
*ЮсН
Ют
Dao
■о—f
Отношение
Xto
Отношение
POFb
1'
Атрибуг_ропь
Атрибут
IDao
Or
Da
Атрибут
*Da
Рисунок 3 - Уточненная структура реляционной модели данных
Анализ полученной структуры показывает, что решены основные проблемы,
свойственные структуре, представленной на рисунке 2:
1. Между отношениями: значение и атрибут, значение и отношение,
атрибут кроль, реализованы самые полные связи типа «многие-ко-многим».
2. В структуре возможна реализация любого количества ссылочных путей
между произвольными значениями, посредством введения отношения роль, т.е.
всякому единственному атомарному значению, может быть сопоставлен О, 1 или
более кортежей в отношении значеиие_атрибут, соответствующие различным
ролям, и участвующие в различных связях.
Уточненная структура реляционной модели данных позволяет решить
значительную проблему при проектировании РБД — идентификации связи
между двумя атомарными значениями в ситуациях, когда таких связей
множество. Сюда относятся не только случаи непосредственной связи двух
отношений, но и множественные связи двух отношений через любое число
промежуточных (существование альтернативных ссылочных путей).
Отношения, .соответствующие сутдностям ER-диаграммы, представленной на
рисунке 3, имеют следующий физический смысл:
•
Отношение — каждый кортеж соответствует некоторому отношению
внутренней ПО.
•
Роль — каждый кортеж соответствует некоторой роли отношения
внутренней ПО.
•
Атрибут
— каждый кортеж соответствует некоторому атрибуту
отношения, не роли, внутренней ПО.
•
Атрибут_роль — данное отношение добавлено для устранения связи
типа «многие-ко-многим» между ролью и атрибутом. Несколько ролей одного
отношения внутренней ПО содержат идентичный набор атрибутов.
•
Значение — каждый кортеж соответствует некоторому атомарному
значению атрибута отношения внутренней ПО. Данное значение имеет
единственную копию в отношении значение, но может ссылаться на множество
атрибутов множества ролей отношений.
18
•
Значение_атрибут — данное отношение добавлено для устранения
связи типа «многие-ко-многим» между отдельными значениями и атрибутами
ролей.
•
Связь — каждый кортеж описывает связь между двумя отдельными
значениями отношений внутренней ПО.
Рассмотрены практические вопросы использования РБД с уточненной
структурой, нормализованньрс на основе операций выборки и соединения, при
моделировании ПО «учебный процесс». В результате проектирования выявлено,
что использование новой структуры позволяет избежать недостатков, описанных
в главах 1 и 2.
В пятой главе рассматриваются основные свойства РБД с уточненной
структурой, нормализованных на основе операций выборки и соединения.
РБД с уточненной структурой, нормализованные на основе операций
выборки и соедине1ШЯ, помимо представленных ранее, обладают рядом
дополнительных свойств.
При использовании уточненной структуры РБД в виде, представленном на
рисунке 3, требования к обязательной нормализации отношений внутренней ПО
неактуальны
Достаточным
условием
отсутствия
аномалий
обработки
информации является единственность существования соответствующего кортежа
в отношении значение. Достаточно иметь единственную копию всякого
отдельного атомарного значения в отношении значение и несколько зависимых
кортежей в отношении значение_атрибут в случае реализации в системе
ненормализованного отношения внутренней ПО. В
случае изменения
единственной копии отдельного атомарного значения при восстановлении
исходного отноп1ения измененное значение будет присутствовать во всех
соответствующих полях атрибутов.
Основное
отличие
выборочно-соединительного
от
проекционносоединительного метода проектирования РБД заключается в способе обобщения
множества однотипных атомарных значений ПО:
1. Проекционно-соединительный метод, называемый нормализацией,
подразумевает обобщение множества однотипных атомарных значений понятием
«отношение». Результатом такого обобщения является появление проблемы
NULL-значений: не во всех однотипных подграфах G может присутствовать один
и тот же фиксированный набор значений атрибутов.
2. Выборочно-соединительный
метод
подразумевает
обобщение
множества атомарных значений кортежами отношения значение, а множество
связей кортежами отношения связь.
РБД, представленная на рисунке 3, позволяет реализовать в своей структуре
любую другую РБД, т.е. может быть определен формальный алгоритм такого
преобразования.
Алгоритм перевода РБД (конвертируемая РБД) в РБД с уточненной
структурой, нормализованную на основе операций выборки и соединения:
1. Для всякого отношения конвертируемой РБД создается кортеж в
отношении отношение В атрибуте отношение.отношение указывается название
конвертируемого отношения.
19
2. Определяются все максимальные ссылочные пути с участием отношения
конвертируемой РБД. Для каждого пути создается кортеж в отношении роль,
связанный с соответствующим кортежем отношения отношение. В качестве
названия роли может быть выбрано название отношения с порядковым номером
пути.
3. Для всякого атрибута отношения конвертируемой РБД, за исключением
атрибутов внешних ключей, создается кортеж в отношении атрибут. В атрибуте
атрибут, атрибут указывается название конвертируемого атрибута.
4. В отношении атрибут_роль
прописываются взаимосвязи между
соответствующими ролями и атрибутами.
5. Для всякого атомарного значения отношения конвертируемой РБД, не
являющегося ^fULL-знaчeниeм, создается кортеж в отношении значение. В
атриб5те значение.значение указывается соответствующее атомарное значение
6. В отношении значение_атрибут прописываются взаимосвязи между
соответствующими атрибутами ролей и атомарными значениями.
7. Определяются связи между атомарными значениями внутри отношения
конвертируемой РБД. В отношении связь прописываются взаимосвязи между
атомарными значениями на основе информации отношения значение_атрибут.
8. Для всякой связи между отношениями конвертируемой РБД
определяются пары {первичный ключ, внешний ключ}. Информация полученного
отношения используется для заполнения отношения связь на основе информации
отношения
значение_атрибут.
Связи
меяоду
кортежами
отношений
конвертируемой РБД в отношение связь заносятся парами (первичный ключ
родительского отношения, первичный ключ дочернего отношения}.
Для реализации п.2 алгоритма перевода РБД в РБД с уточненной структурой,
нормализованную на основе операций выборки и соединения, предложен
алгоритм определения ролей отношений и последующей модификации графа
связей отношений РБД.
Для реализации алгоритма рассматривается граф связей конвертируемой
РБД Для иллюстрации работы алгоритма рассмотрим следующий граф связей, в
котором отражены все возможные ситуации ссылочных путей между
отношениями (см. рисунок 4).
D
Рисунок 4 - Граф связей 5-ти реляционных отношений
На шаге 1 для устранения циклических ссылочных ограничений
определяются все подграфы исходного графа, у которых совпадает источник и
сток (при этом пути вида Лг->Лг—>..—>/?„—>Л,, R2—>Rs—>..—>R„—>R2 и
20
подобные будем считать определением одного и того же циклического
ссылочного ограничения), а затем разделяется одна из вершин, участвующая в
циклическом ссылочном ограничении так, что первая будет ассоциирована
только с исходящими дугами, а вторая только с входящими. На данном графе
таких циклов два: А—>С—>Е—>А и А—>В—>С—>Е—>А, разделение вершин Е
на El и Е2 так, что вершина £/ будет ассоциирована только с исходящими дугами,
а Е2 только с входящими избавит исходный граф от циклических ссылочных
ограничений.
На шаге 2 производится анализ и модификацию фафа для выявления
альтернативных ссылочных путей, для чего строится таблица связей отдельных
отношений (таблица 3). В ситуациях непосредственной достижимости узлов
R„—>R„.i и наличия меэвду ними альтернативных ссылочных ограничений
идентификаторы родительских отношений будем нумеровать
числами
натурального ряда.
Таблица 3 - Связи отдельных отношений
Определяющее (рюдительское)
отношение
А
В,
Зависимое (дочернее) отношение
Е,
А
А
В2
С
А
В
С
D
В
D
С
С
Е2
На шаге 3 алгоритм анализирует все ссылочные пути между всеми парами
отношений. На основе анализа таблицы 3 определяются следующие ссылочные
пути для всех пар отношений:
А.>Е,: {А->Е,};
B->Ej: {B,->A->Ei; В2->А->Е,};
C->Ei: {С->А->Е,; С->Вг>А->Е,; С->В2->А->Е,};
D->E,: {D->Bi->A->E,: D->B2->A->E,; D->C->Br>A->E,; D->C->B2->A->E,};
Er->E,: {Er>C->A->Ei: Er>C->B,->A->E,: E2->C->Br>A->E,J;
B->A: {B,->A, B2->A};
C->A: {C->A, C->B,->A. C->B2->A};
C->B: {C->B};
D->A: {D->Br>A. D->B2->A. D->C->A, D->C->B,->A. D->C->Br>AJ:
D->B: {D->B, D->C->B};
D->C: {D->C}:
Er>A: {Er>C->A, E2->C->Br>A, Er>C->B2->A}:
E2->B: {Er>C->B}:
E2->C. {E2->Q.
Ha шаге 4 определенные пути сносятся в новую таблицу, игнорируя
повторяющиеся подфафы (см. таблицу 4).
21
Таблица 4 - Описание подграфов достижимости отношений
Роль
Отношение
СВ,АЕ,
E,
El
СВгАЕ,
DB,AE,
E,
DBiAE,
E,
DCAE,
E,
DCB,AE,
E,
El
DCBiAE,
El
EiCAE,
E2CB1AE,
E,
E2CB2AE,
E,
ролей.
Используется
следующие
правило
именования
RiR2R3...R„=>R„->R,.,R„uR„ ,R„->R„2R„ ,R„u .. UR2R3. R„->RiR2R}.. R„
где R, ,i=l..n- отношение ПО;
п - количество отношений, участвующих в определении роли/
соответствующем ссылочном пути.
Например,
восстановим
подграф,
определяющий
роль DCB2AEjDCB2AE,^>Er>AE,
и АЕг>В2АЕ, и B2AEi->CB2AE, и СВ2АЕ,-> DCB2AE1.
Аналогично определяются подграфы, для остальных ролей.
Для исходного фафа связей реляционных отношений, представленного на
рисунке 4, итоговый, модифицированный граф связей ролей отношений приведен
на рисунке 5.
Е2СВ2А
v_^DCB2A
Рисунок 5 - Граф связей ролей отношений
Если РБД имеет упрощенную структуру, представленную на рисунке 2, то
при конвертации в уточненную структуру РБД, нормализованную на основе
операции выборки и соединения необходимо скопировать только содержимое
отношений, т.к. оно полностью описывает внутреннюю ПО Предложенная
конвертация всегда возможна, в виду того, что структура, представленная на
рисунке 3, позволяет хранить больше информации: арность взаимосвязей между
отношениями отношение, атрибут, значение в упрощенной структуре «один-комногим», а в уточненной структуре — «многие-ко-многим».
22
Алгоритм перевода информации РБД с упрощенной структурой
(конвертируемая РБД) в РБД с уточненной структурой, нормализованную на
основе операций выборки и соединения:
1. Для всякого кортежа отношения отношение конвертируемой РБД
создается кортеж в отношении отношение с аналогичным значением атрибута
отношение .отношение.
2
Для всякого кортежа отношения отношение конвертируемой РБД
создается кортеж в отношении роль с аналогичным значением атрибута
отношение.отношение, связанный с соответствующим кортежем отношения
отношение.
3. Для всякого кортежа отношения атрибут
конвертируемой РБД
создается кортеж в отношении атрибут с аналогичным значением атрибута
ampt^m.атрибут.
4. В отношении атрибут_роль
прописываются взаимосвязи между
соответствующими ролями и атрибутами.
5. Для всякого кортежа отношения значение конвертируемой РБД
создается кортеж в отношении значение с аналогичным значением атрибута
значение.значение.
6. В отношении значение_атрибут прописываются взаимосвязи между
соответствующими атрибутами ролей и атомарными значениями.
7. На основе информации связь конвертируемой РБД заполняется
отношение связь на основе значения ключей отношения значение_атрибут.
' В шестой главе разрабатываются надстройки декларативных языков
манипулирования данными РБД, нормализованных на основе операций выборки
и соединения.
Для реализации инструкции запросов к РБД, нормализованным на основе
операций выборки и соединения, расширяется классическая реляционная алгебра.
Учитывая, что исследуемые РБД, являются реляционными по построению,
можно определить их манипуляционную часть в виде классической реляционной
алгебры, включающей в себя 8 операторов: /4 = (л,с/^Д,х,8,П,><,д), где
Я = {й„л,,л„я,,л,,д,,,я,} - множество отношений РБД, нормализованных на
основе
операций
выборки
и
соединения
{отношение,
атрибут,
атомарное значение, роль отношения, аттрибут_роль, значение_атрибут, связь}, и
соответственно начертание операторов (объединение, пересечение, разность,
декартово произведение, выборка, проекция, соединение, деление). Отметим, что
информативные атрибуты содержаться в отношениях /?/ («название отношения»),
Лг («название атрибута»), R} («атомарное значение»), Л< («название роли»).
Расширим набор стандартных операторов реляционной алгебры введением
оператора Vp(R) такого, что Vp(R)={r|P(r)}, где
г - упорядоченная тройка («название отношения», «название атрибута»,
«атомарное значение»);
Р(г) - отбирающий предикат.
Тогда: Vp(R) = Sp„(R,)><iSp^,„(R,)><R,><]Sp_„(Rj)><R,>4Sp^(„(R3)><lR,,
где Sp|,)(R,) - операция выборки кортежей отношения R,, удовлетворяющих
условию Р,(г).
23
На рисунке 6 представлен план выполнения оператора Vp(R).
><
(>^0 (^®
Рисунок 6 - План выполнения оператора Vp(R)
Пусть f(a,Pi(r)) - двухместная функция, возвращающая количество
отношений, выбранное из РБД а с использованием предиката Pi(r), аналогично,
f(a,?3(t)) - функция, возвращающая количество атрибутов, выбранное из РБД а с
использованием предиката Рз(г).
Представление результатов оператора Vp(R) в виде упорядоченной тройки
(«название отношения», «название атрибута», «атомарное значение») неудобно,
поэтому для восстановления исходного плоского отношения В,, i=l..f(a,Pi(r)),
введем оператор Ощ, такой что:
где Attij - j-й атрибут отношения й^, j = l . Д а ,Рз(г)).
Таким образом, в качестве манипуляционной части Р Б Д нормализованных
на основе операций выборки и соединения может использоваться алгебра вида:
^ = (л,и,о,\^<, S, П. ><J, Д. V, (г), D B j .
Для реализации реляционного оператора Vp(R) определим инструкцию
В Ы Б Р А Т Ь со следующей БНФ-фамматикой формулирующую запросы к БД,
нормализованным на основе операций выборки и соединения:
<оператор запроса>::= ВЫБРАТЬ <текст>
<текст>::=
<основной текст> | <основиой текст> В <имя новой таблицы> | В <имя новой таблицы>
<имя новой таблицы>:= <идентификатор>
<основной тскст>:;= <тело запроса> | <тело запроса> <командная с1рока>
<тело запроса>:~ <значсние выбора> | <значение выбора> ГДЕ <предикат>
<командная строка>::= <команда>{ <комзнда>)
<команда>--=
<идентификатор
команцьс> <идентификатор
роли> <идентификатор
атрибута>
{, <идентификатор роли> -^идентификатор атрибута>}
<идентификатор комавды>..= СОРТИРОВАТЬ ПО | ГРУППИРОВАТЬ ПО
Оначение выбора>":= <описание>{, <описание>)
<описание>: =
<отдельное описанне>|<отдельное описание> К А К <идентификатср атрибута>
24
<отдельное описание>::= <источник данных> |
<агрегативная функция> (<идентификатор роли> <идентификатор атрибута>)
<агрегативная функция>::=
СУММА I КОЛИЧЕСТВО | М А К С И М У М | М И Н И М У М
<источник данных>:=<идентификатор роли> <указатель атрибута> |
^идентификатор роли>
<указатель атри6ута>:?= <идентификатор атрибута> | В С Е
<преди1сат>::= <отдепьное условно
{<логический оператор> <отдельное условие>)
<логический оператор>:.= ИЛИ | И
<отдельное условие>::= <основа условия> | Н Е <основа условия>
<основа условия>:г= <простое условие> | ВОЗМОЖНО <оператор запроса>
<простое условие>::=
<идентификатор роли> <идентификатор атрибута> <идентификатор значения> (
<идентификатор роли> <идентификатор атрибута> <оператор отношения> <идентификатор
значения>
<оператор отношения>: := > | < | = | о | <= | >=
<идентификатор роли>::= <идентифи1сатор>
<идентификатор атрибута>:?= <идентификатор>
<идентификатор значения>:~ <константа неопределенного типа> |
<идентифнкатор>
<идентификатор>::= <буква> {<буква>|<цифра>)
<буква>:-А|Б|В|...1Я|...
<цифра>::= О 11 | 2 | . . . | 9
<коистанта неопределенного типа>::= <символ>{<символ>}
<символ>::= А I Б I В I .. | Я | 0 | 1 |2 [.. | 9 | ! | ? | ..
Выполнение инструкций запросов к РБД предполагает определение
некоторого подмножества атомарных значений, принадлежащих заданным
атрибутам отношений, согласно заданному предикату. В предикате явным
образом указываются связанные между собой логическими операциями исходные
данные, представляющие собой наименование исходных атомарных значений,
принадлежащих определенным атрибутам отношений. Если в качестве
инструкции запросов используется S E L E C T языка SQL, то в предикате
обязательно указание ссылочных ограничений, на основе чего компилятором
строится план выполнения запроса и определяется порядок выполнения
соединений.
В
случаях
применения
уточненной
структуры
РБД,
нормализованной на основе операций выборки и соединения, согласно
введенному определению роли отношения, ссылочный путь между любыми
двумя атомарными значениями и/или ролями однозначен и может быть
автоматически определен на основе анализа информации семи представленных
отношений. Поэтому в предикате инструкции В Ы Б Р А Т Ь не указываются явным
образом ссылочные ограничения между ролями. В этом случае все ссылочные
Офаничения определяются автоматически на этапе компиляции, что позволяет
отказаться от необходимости модификации инструкций выборки данных
вследствие изменений структуры РБД.
Инструкция В Ы Б Р А Т Ь является более высокоуровневой по отношению к
инструкции S E L E C T и на этапе выполнения запроса может бьпъ ею заменена. С
этой целью разработано специализированное программное обеспечение,
выполняющее функции компилятора, т.е. для нужд прикладных программ
разработан конвертор (компилятор) перевода инструкции В Ы Б Р А Т Ь в SELECT.
25
Выполнение инструкции В Ы Б Р А Т Ь происходит как вызов функции компиляции,
а сама инструкция определяется как параметр этой функции.
Задачу определения ссылочных ограничений для пары ролей определим в
виде: требуется найти путь из искомой роли R, в исходную роль Rj.
Решим задачу с использованием теории графов. На множествах ролей
отношений Л и взаимосвязей между ними F построим ориентированный фаф
G = {R,F) и перерисуем его в виде ориентированной сети G={R,F).
Алгоритм
восстановления ссылочных ограничений на ориентированной сети G ролей
отношений:
1. Выбирается вершина Ro уровня О (вершина с полустепенью захода
равной 0), из которой достижимы вершины с исходной и требуемой роля.ми.
Указанная задача является частной к определению обратного транзитивного
замыкания Г'(л,)=|г"(л,)иГ''(д,)иГ'^(й,)^...} для некоторой искомой вершины
и обратного транзитивного замыкания r{Rj) для некоторой исходной вершины,
где Г' — многозначное отображение: Г*(д,)=г{г*"'(Д;)}, полагая r''{Ri)=Ri и
r''{R,)=Rj, если r(Rj)=Ri. Если * > 0 , то Г'(л,) — множество вершин
ориентированного графа, в которые существует путь длины к из вершины Д,
Если А >0, то Г '(л,) — множество вершин, из которых существует путь длины
к в вершину л , .
2. Из вершины Ro определяются два простых пути к исходной R, и
требуемой Rj ролям.
3. Поисковый путь определяется как совокупность найденных двух
простых путей за исключением совпадающих дуг.
Представленные задача и алгоритм ее решения могут быть сведены к
определению поисковых путей на сети взаимосвязей атомарных значений.
Проблема построения ориентированной сети, т.е. расположения вершин
графа на плоскости с целью визуадьного распределения вершин по уровням
назьюается проблемой топологической сортировки и может быть решена путем
вычисления порадковой функции сети на основе адгоритма Демукрона.
Реализация алгоритма Демукрона в компиляторе инструкции запросов приводит
к увеличению времени его выполнения. Можно повысить производительность
алгоритма выборки данных в случае, если информация об ориентированной сети
на момент выполнения запроса будет известна, т.е. будет вычисляться
динамически согласно происходящим изменениям в исследуемой ПО. При
добавлении в РБД новой роли/атомарного значения должен вычисляться
соответствующий им уровень и пересчитываться уровни связанных с ними
ролей/атомарных значений. Следующий алгоритм динамически вычисляет
уровень ориентированной сети, которому принадлежит добавляемое атомарное
значение v, и пересчитывает уровни атомарных значений, связанных с v, (для
хранения номеров уровней в отношение "значение_атрибут" вводится атрибут
"уровень_значения"):
1. Добавляется атомарное значение v,.
2.
Атомарному значению v, ставится в соответствие уровень С, = 0.
26
3.
Если
атомарное
{vj,v^^,.. ,v^_}=r"'(v,),
значение
соответсггвующим
v,
определено
уровням
сети
множеством
{Ui,Ui<-M,},
т.е.
(t/„t/j,. .,(/„) = y(vj,v^j
v^J, где (о) — упорадоченный набор, кортеж, /(») —
вычисляемое многозначное соответствие на множествах вершин и уровней сети,
С/, =max(c/|,c/j,. .,[/„), то v, ставится В соответствие уровень t/, = С/, +1.
4.
Если
атомарное
значение
соответствующие уровням сети
v,
определяет
{u„U2,.-,uJ,
множество
{*'^.»'t,.-.n_)
т.е. (t/|,t/j,. .,t/„)=/(v, ,i'j^,...,Vi_),
t/^=min(t/|,C/2, ,t/,), V,-♦{vj ,v,_,. ,Vj_}or'(v,), TO ДЛЯ многозначного отображения
r*(v,)={r°(v,)i..;r'(v,)ur^(v,)>j...}
:r*(v,).U,
изменяется
номер
С, +/,e«iHVj = r'(v,),t/, >: /(r'(v,))lit * (•
очевидно,
U/,, иначе
ft/,+1.еслиi/. Si/,
вычислений С, = '^,,
'
' \и у, иначе
уровня
что
после
5. Обновляются
соответствующие
поля
атрибута
значение_атрибут.уровень.
Алгоритм перестройки ориентированной сети при удалении агомарного
значения v,:
1.
Если
атомарное
значение
v,
определено
множеством
{v^ ,v^, ..,v, }= r''(vi), то удаляются соответствующие дуги.
2.
Если атомарное значение v, определяет множество {vti.Vjj, ,v,_}=r'(v,),
соответствующее уровням сети {o,,U2, >С/„}. то удаляются соответствующие дуги
и уровни вершин V, 6 r*(v,), V, # V, определяются на ос1Юве алгоритма добавления
атомарных значений предметной области.
3. Удаляется атомарное значение v,.
Производительность алгоритмов восстановления ссылочных ограничений на
ориентированной сети ролей/атомарных значений может быть увеличена, т.е.
минимизировано время выполнения алгоритмов, если выделить подграф,
соответствующий параметрам запроса, (сужение области поиска):
1. Пространство поиска может быть сужено по высоте, путем определения
подмножества уровней ориентированной сети, которым принадлежат требуемые
значения. При этом заранее известными данными являются принадлежности
атомарных значений соответствующим ролям и уровням сети. В представленной
постановке справедлива следующая теорема о выборке атомарных значений ПО.
если множество искомых вершин \уj,,vj^,., vj } соответствует уровням сети
pj^,Uj^. ,U^J, а множество исходных вершин ]y|,,v^^
v^ } соответствует
уровням сети {c/j^,{/,^,...,t/,_} и эти вершины достижимы из одного и того же
подмножества
вершин
{v„ ,v, , ,v„ }
K-f^*.. . f ^ . J = / k . % . - . n J ,
u, =msx{u^,Uj^,:.,Uj,Ui,,,Ui^,:,UtJ,
уровня 0:
(^^j,,^,,,-,0^ )= f{vj ,v^ ,. ,v^ ),
k-\,--^j.-\'\
njer^vj,
TO операция выборки данных о может быть
реализована как соединение и, выборок атомарных значений соответствующих
27
уровням [O.Z/;] =>о = 0|,р-<1 о, ><!...><(?„_, где о, —выборка атомарных значений
уровня ; ориентированной сети, "><i" — начертание операции соединения.
Доказателылво теоремы основано на определениях роли отношения и
ориентированной сети.
2. Пространство поиска может быть сужено по ширине, путем определения
подмножества вершин уровня О для исходного множества значений и
последующего выделения соответствующего им подграфа значений. Теорема о
выборке атомарных значений ПО с ограничением: операция выборки данных О
может быть реализована как соединение и^ выборок атомарных значений
соответствующих уровням [O.i'j=>i9 = yi//e/-(oj><0, >< ..хОц , где filierio^) —
операция выборки
ограниченного подмножества вершин {v,,} уровня 0;
{v„}er-(v,,,Vj, v , J .
3. Множество атомарных значений ПО есть многозначное соответствие на
множестве
ролей
отношений
ПО:
/:{U.
■^ш).{А2-Уш)
(4» :v^)i-.{Ki :v„,),(^.2 :v^,)....,(^w :v,^)}}-*{/f„/?j
Л.)и
поэтому задача определения поискового пути на ориентированной сети
атомарных значений может быть сведена к задаче определения поискового пути
на ориентированной сети ролей отношений ПО. Теорема о соединении ролей
отношений ПО: если множество искомых вершин принадлежат ролям отношений
^^,Rj^,...,RjJ, соответствующим уровням сети
исходных
вершин
принадлежат
ролям
соответствующим уровням сети {У^,,!/,^
из
одного
и
того
К '^j. f/y. )= / К .■«;.
к,л,.
f/^J, а множество
отношений
{^,,,^j_,..,VfjJ
{/,_} и эти роли отношений достижимы
же подмножества
Л,.),
й^.,Л,,,Л,,,...Л^.]егЧя,),
^J^,f/y,
вершин
^^,R.,
Л„_} уровня 0:
{{/, ,и,_ .....и.. )= А^Л, Л..),
С/, =m8x(t/^_.t/^,
Uj^.U,,,U,, uj,
то
результатом выборки данных о служит выборка атомарных значений из
соединения
ролей
отношений
Л,,
таких
что
/(^,)e{0.i/,],
R,er*(R^)\r(R^\j
= l.jn,
где Г ° { « ^ ) -
множество
родительских
ролей
отношений, принадлежащих совпадающим дугам поискового пути .
Алгоритм определения поискового пути на сетях ролей отношений
выполняется для каждой пары исходных и искомых ролей:
1. Для искомой роли определяется множество соответствующих ролей
отношений уровня 0.
2. Для исходной роли определяется множество соответствующих ролей
отношений уровня 0.
3. Определяется подмножество ролей отношений уровня О как пересечение
определенных на шаге 1 и 2 множеств.
4. Из поисковых пзпгей, соответствующих определенному подмножеству
ролей отношений уровня О удаляются совпадающие дуги путей, ведущие к
исходной и искомой ролям отношений.
28
В ситуациях, при которых не возможно определить роль отношения Л„
уровня О, из которой достижимы роли R, и Л,, возможен один из двух исходов
выполнения алгоритма определения поискового пути:
1. Исходные данные запроса логически не связаны, т.е. выборка пуста.
2. Исходные и искомые роли достижимы из непересекающихся
подмножеств ролей отношений уровня О и связаны через некоторые обобщающие
роли отношений. Последние могут быть определены и использованы на
следующем шаге поиска в качестве исходных ролей отношений.
Показано, что однотипные запросы с использованием инструкции В Ы Б Р А Т Ь
формулируются проще по сравнению с инструкцией S E L E C T ; их структура не
изменяется при изменении структуры внутренней ПО и отсутствует
необходимость использования системных функций, обрабатывающих NULLзначения.
В седьмой главе представлены методы проектирования и обеспечения
функционирования распределенных РБД, нормализованных на основе операций
выборки и соединения.
При создании корпоративной информационной системы, решающей
различного рода задачи по автоматизации большого предприятия с множеством
подразделений и удаленных филиалов, с целью увеличения эффективности всей
системы, возникает потребность в разделе единой РБД на отдельные элементы.
Т.е. распределение единой РБД между некоторыми узлами вычислительной сети.
Показаны результаты реализации стандартных подходов к проектированию
распределенных РБД применительно к РБД, нормализованной на основе
операций выборки и соединения:
1. Если предполагается вертикальная фрагментация исходных отношений,
то содержимое отношений (Отношение, Роль} остается неизменным, отношения
{Атрибут, Ampu6ymj?0M, Зиачение_атрибут, Значение, Связь} подвергаются
горизонтальной фрагментации.
2. Если
предполагается
горизонтальная
фрагментация
исходных
отношений, то содержимое отношений {Отношение,
Роль,
Атрибут,
Атрибут_роль} остается неизменным, отношения {Значение_атрибут. Значение,
Связь} подвергаются горизонтальной фрагментации.
3. Если предполагается территориальное разнесение отношений по узлам
сети, то горизонтальной фрагментации подвергаются либо все отношения, либо
подмножество {Роль, Атрибут, Атрибут_роль, Значение_атрибут. Значение,
Связь}.
4. При тиражировании данных в узлах сети сохраняются копии РБД, с
описываемой структурой.
Таким образом, каким бы ни был метод построения распределенной Р Б Д он
сводится к горизонтальной фрагментации таблиц на основе некоторого
предопределенного правила. Во всех узлах распределенной СУБД должен
функционировать собственный фрагмент РБД со структурой, представленной на
рисунке 3.
Предложен метод администрирования доступа к информации РБД,
нормализованных
на
основе
операций
выборки
и
соединения, в
многопользовательских клиент-серверных системах. Согласно теоретическому
29
аппарату построения таких РБД, рассмотрешюму в предыдущих разделах,
информация о системных пользователях записывается следующим образом:
1. В отношение отношение добавляется запись {Mj, пользователь}, где
М/ — значение первичного ключа записи.
2. В отношение pcwb добавляется запись {Мг, М/, пользователь), где Мг —
значение первичного ключа записи, а Л// — значение внешнего ключа.
3. В отношение атрибут добавляется запись {М^, пользователь), где Л/j —
значение первичного ключа записи.
4. В отношение значение добавляются записи о конкретных системных
пользователях.
5. На основе первых четырех пунктов определяется содержимое таблиц
атри6ут_роль и значение_атрибут.
6. На основе первых пяти пунктов и информации о структуре ПО из
таблиц отношение, роль, атрибут, атрибут_роль определяется содержимое
таблицы связь.
В данной постановке, по отношению к операции выборки данных (например,
выборка данных из отношения "подразделения"), согласно пользовательским
полномочиям, запрос будет иметь следующую содержательную часть:
В Ы Б Р А Т Ь подразделение В С Е
Г Д Е пользователь пользователь U S E R _ N A M E ( )
где U S E R _ N A M E O - функция, возвращающая имя пользователя.
Аналогично
определяются
правила
администрирования
функций
добавления, обновления и удаления инфор.мации.
Строится
математическая
модель
оптимизации
параллельного
вычислительного
процесса
применительно
к
многопользовательской
автоматизированной
системе,
построенной
с
использованием
РБД,
нормализованной на основе операций выборки и соединения. Оптимальные
характеристики параллельной вычислительной системы выбираются из условия
достижения максимальной производительности к от числа вычислительных
узлов т при ограничениях на заданную эффективность е„е{o,l) (зшрузку
одиночных вычислительных узлов):
Г
[к{т) = шах
e(/n)se„
I
' +Ч)У
mi»,
.ЕК
где ^, е[0,оо) JJ p j e ( а>;оо) — экспериментально определяемые параметры
для конкретных программно-аппаратных платформ.
С целью определения вида функции прюизводительности: к = ( т ' + р(т^^
использовались результаты более 200 экспериментов. Для определения вида
аппроксимирующей функции k = f(m) от числа используемых процессоров на
основе дискретных выборок точек (т,,к,) использовались метод наименьших
30
квадратов и методы выравнивания для приведения исследуемой зависимости к
линейному виду. Функция р{т) имеет вид: JJ{m) = <p^m*', т.к. экспериментально
показано, что коэффициент парной корреляции величин ln(m) и ln(/?(m)) близок к
1: ln(^(m))=ln(^,)+^jln(m).
Представленная математическая модель корректно описывает все известные
функциональные
зависимости
производительности
параллельного
вычислительного процесса от числа вычислительных узлов и позволяет
определять основные характеристики вычислительных систем: время окончания
вычислительных процессов, оптимальное число вычислительных узлов,
оптимальную зафузку процессоров.
В заключении изложены основные теоретические и практические
результаты, полученные в диссертационной работе.
В приложении приведены реализация РБД, нормализованной на основе
операций выборки и соединения, с использованием M S SQL Server 2000; БНФграмматика инструкции В Ы Б Р А Т Ь ; листинги основных методов и экранные
формы СУБД, основанной на РБД, нормализованных на основе операций
выборки и соединения; акты внедрения результатов работы.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
Получены следующие научные и практические результаты:
1. Структурная часть РБД, нормализованных на основе операций выборки
и соединения.
2. Целостная часть Р Б Д нормализованных на основе операций выборки и
соединения.
3. Синтаксис, БНФ-грамматика, правила использования инструкций языка
манипулирования данными РБД, нормализованных на основе операций выборки
и соединения.
4. Алгоритмы поиска информации в РБД, нормализованных на основе
выборки и соединения.
5. Алгоритм перевода ER-диаграмм в структуру РБД, нормализованных на
основе выборки и соединения.
6. Алгоритмы перевода РБД в структуру РБД, нормализованных на основе
выборки и соединения.
7. Методы проектирования распределенных РБД, нормализованных на
основе операций выборки и соединения.
8. Методы администрирования доступа к информации РБД на основе
реляционной операции выборки.
9. Комплекс программ проектирования и обеспечения функционирования
РБД, нормализованных на основе операций выборки и соединения.
10. Математическая модель задачи оптимизации вычислительного процесса
в многопользовательских системах обработки информации и управления,
построенных на основе РБД, нормализованных на основе операций выборки и
соединения.
ОСНОВНЫЕ ПУБЛИКАЦИИ ПО Т Е М Е ДИССЕРТАЦИИ
1.
Маликов А.В. Организация параллельных вычислительных систем на
базе Л В С для обработки баз данных большого объема. //Депонировано В И Н И Т И
№754-82001,2001,31 с.
31
2.
Маликов А.В. Проектирование реляционных баз данных на основе
операций выборки и соединения. Исследование их свойств. /Под редакцией проф.
Чефранова А.Г., Ставрополь: СевКавГГУ, 2002, 244 с.
3.
Маликов А.В.,
ЧефрановА.Г.
Аналитическая
зависимость
производительности
параллельных
вычислительных
систем
от
числа
процессоров. //Известия вузов. Северо-Кавказский регион. Технические науки,
2003, № 2, с.25-28.
4.
Маликов А.В. К вопросу нормализации реляционных баз данных.
//Кибернетика и технологии X X I века /Материалы IV Международной научнотехнической конференции, Воронеж: В Г У , 2003, с.79-86.
5.
Маликов А.В. Разработка надстрюек инструкций манипулирования
данными БД, нормализованных на основе операций выборки и соединения.
//Кибернетика и технологии X X I века /Материалы I V Международной научнотехнической конференции, Воронеж: В Г У , 2003, с.87-96.
6.
Маликов А.В. Методика проектирования реляционных баз данных на
основе операций, отличных от проекции и соединения. //Известия вузов. СевероКавказский регион. Технические науки». Специальный выпуск «Математическое
моделирование и компьютерные технологии», 2003, с.7-11.
7.
Маликов А.В. Разработка синтаксиса и алгоритма функционирования
инструкций манипулирования данными реляционных баз данных. //Известия
вузов. Северо-Кавказский регион. Технические науки. Специальный выпуск
«Математическое моделирование и компьютерные технологии», 2003, с. 12-17.
8.
Маликов А.В., Евдокимов А.А., Кириченко В.И. Реализация АСУ
учебным процессом на базе СевКавГТУ. //Новые информационные технолетии.
Разработка и аспекты применения / Материалы I V всероссийской конференции с
международным участием, Таганрог: ТРТУ, 2003, с. 18-22.
9.
Маликов А.В., Лидовской К.В. Алгоритм поиска информации в
реляционных базах данных, нормализованных на основе операций выборки и
соединения. //Современные наукоемкие технологии, 2004, №2, с.41-44.
10. Маликов А.В., Лидовской К.В. Оптимизация на графах поиска
информации в реляционных базах данных, нормализованных на основе операций
выборки и соединения. //Теория, методы проектирования, програ.ммнотехническая платформа корпоративных информационных систем /Материалы I I
международной научно-практической конференции, Новочеркасск, 2004, с.219221.
11.
Маликов А.В. Методы проектирования и поддержания ссылочной
целостности реляционных баз данных, нормализованных на основе операций
выборки и соединения. //Татищевские чтения: актуальные проблемы науки и
практики /Материалы Международной научной конференции, Тольятти:
Волжский университет им. В.Н.Татищева, 2004, с.247-253.
12. Маликов А.В., Евдокимов А.А., Кириченко В.И., Лидовской К.В.
Интегрированная автоматизированная система управления учебным процессом
вуза- ИАСУ «Деканат». //Новые образовательные технологии в вузе /Материалы
I I научно-методической конференции, Екатеринбург: УГТУ-УПИ, 2004, с.30-32.
13. Маликов А.В., Лидовской К.В. Анализ и модификация графа связей
отношений
реляционной
базы
данных.
//Инфотелекоммуникационные
32
технологии в науке, производстве и образовании /Материалы первой
международной научно-технической конференции, Ставрюполь:СевКавГТУ, 2005,
с.46-49.
14. Маликов А.В. Реализация инструкций запросов к реляционным базам
данньв4. //Известия вузов. Приборостроение, 2005, №9, с.7-12.
15. Маликов А.В., Лидовской К.В. Расширение реляционной алгебры для
декларативных языков запросов к нормализованным на основе операций выборки
и соединения базам данных. //Известия вузов. Северо-Кавказский регион.
Технические науки. Специальный выпуск «Математическое моделирование и
компьютерные технологии», 2005, с.9-10.
16. Маликов А.В. Использование нормализованных на основе операций
выборки и соединения реляционных баз данных в
корпоративных
автоматизированных системах управления. //Вестник СевКавГТУ, 2005, №4,
с.64-69.
17. Маликов А.В.,
Лидовской К.В.
К
вопросу
обеспечения
функционирования реляционных баз данных, нормализованных на основе
операций выборки и соединения //Безопасность информационных технологий,
2005, №3, с.62-67.
18. Маликов А.В., Синельников Б.М., Цвиринько И.А. и др. Свидетельство
об официальной регистрации программы для Э В М
«Интегрированная
автоматизированная система управления (ИАСУ) «ВУЗ»» №2005612457
зарегистрировано 19.09.2005.
19. Маликов А.В., Синельников Б.М., Цвиринько И.А. и др. Свидетельство
об официальной регистрации базы данных «База данных интегрированной
автоматизированной системы управления (ИАСУ) «ВУЗ»» №2005620267
зарегистрировано 18.10.2005.
Личный вклад соискателя в работах, выполненных в соавторстве: [3] —
предложена и обоснована аналитическая зависимость производительности
параллельной системы от числа процессоров, [8, 12, 18, 19] - реализована
подсистема ведения учебных планов и спроектирован соответствующий
фрапиент РБД, [9, 10] - предложен поисковый алгоритм, [13] - предложен
модифицирующий алгоритм, [15] - введены новые реляционные операторы,
[17]- введены новые реляционные операторы и реализующие их инструкции
выборки данных.
Формат 60x84 1/16 Усл. печ. л. 2 Уч.-изд. л. 1 ^
Бумага офсетная. Печать офсетная Заказ 659 Тираж 100 экз.
ГОУВПО «Северо-кавказский государственный технический университет»
355029 г. Ставрополь, пр. Кулакова, 2
Издательство Северо-кавказского государственного технического университета
Отпечатано в типографии СевКавГТУ
Р21792
РНБ Русский фонд
2006-4
20558
Документ
Категория
Без категории
Просмотров
0
Размер файла
1 666 Кб
Теги
bd000101459
1/--страниц
Пожаловаться на содержимое документа