автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Проектирование и исследование свойств реляционных баз данных, нормализованных на основе операций выборки и соединения



-V

I

На правах рукописи

МАЛИКОВ АНДРЕЙ ВАЛЕРЬЕВИЧ

ПРОЕКТИРОВАНИЕ И ИССЛЕДОВАНИЕ СВОЙСТВ РЕЛЯЦИОННЫХ БАЗ ДАННЫХ, НОРМАЛИЗОВАННЫХ НА ОСНОВЕ ОПЕРАЦИЙ ВЫБОРКИ И СОЕДИНЕНИЯ

Специальность 05.13.18 - Математическое моделирование, численные методы и

комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук

Ставрополь - 2005

Работа выполнена в Северо-Кавказском государственном техническом университете.

Научный консультант: доктор технических наук, профессор

Чефранов А.Г.

Официальные оппоненты: доктор технических наук, профессор

Кузнецов С .Д. доктор технических наук, профессор

Смирнов С.Н. доктор технических наук, доцент

Кандаурова Н.В.

Ведущая организация: Московский инженерно-физический институт (государственный университет), МИФИ, г. Москва

Защита состоится « 23 » декабря 2005 г. в 1400 часов на заседании

диссертационного совета ДМ 212.245.09 при Северо-Кавказском

государственном техническом университете по адресу: г. Ставрополь, пр. Кулакова, 2, конференцзал.

С диссертацией можно ознакомиться в библиотеке Северо-Кавказского государственного технического университета.

Автореферат разослан «•/£) » 2005 г.

Отзывы на автореферат в двух экземплярах, заверенные печатью организации, просим направлять по адресу: 355000, Ставропольский край, г. Ставрополь, пр. Кулакова, 2, Северо-Кавказский государственный технический университет.

Ученый секретарь диссертационного совета

к.ф.-м.н., доцент

О.С. Мезенцева

Ш6-Ч 'Я01Ш

2&5S8

3

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Деятельность человека во многом связана со сбором, накоплением и обработкой информации. Бурное развитие и применение компьютерной техники приводит к неуклонному росту объемов накапливаемой информации и повышению требований к ее структуре и качеству. При этом качество информации может оцениваться по целому раду критериев. Одним из самых удачных инструментариев обработки информации стала реляционная теория, представляющая собой комплекс математических методов проектирования и обеспечения функционирования реляционных баз данных

(РБД).

Необходимым условием эффективного использования РБД является отсутствие аномалий обработки информации, которое достигается посредством методики нормализации отношений. Стандартные методы нормализации, основанные на реляционных операциях проекции и соединения, не позволяет эффективно описывать произвольные предметные области (ПО) с полностью не определенными структурами. Данная проблема имеет частичное решение в случае дополнения классической реляционной теории методами моделирования квазиструктурированной (полуструктурированной) информации. В этом случае структуру ПО рассматривают как обычные данные, к которым могут быть применены операции манипулирования информацией: добавление, удаление, изменение.

Несмотря на развитый математический аппарат, значительную программную и информационную поддержку, множество прикладных реализаций, реляционной модели данных присущи следующие основные недостатки:

1. Для разных уровней пользователей системы информация РБД представляется различными уровнями абстракции. Как правило, конечный пользователь (клиентское приложение) не в состоянии изменить набор и структуру таблиц, вследствие изменения информации ПО: реляционная система становится зависимой от прикладного программиста и администратора, что сказывается на коммерческих свойствах системы.

2. Декларативные языки манипулирования данными, несмотря на универсализм, являются языками уровня прикладного программиста и/или администратора системы, но не конечного пользователя. Пользователь не знающий структуры РБД не может сформулировать свой запрос, а если запрос написан на языке SQL, то изменение структуры РБД влечет за собой его переформулирование.

3. Наличие NULL-значений в таблицах и, вообще, трехзначная логика усложняет бизнес-логику клиентских приложений.

Развитие математического аппарата реляционной теории с целью решения

указанных проблем представляется актуальной задачей. В диссертационной

работе проведено развитие и обобщение реляционной теории с целью

преодоления недостатков проектирования и обеспечения функционирования

классических РБД, для этого вводятся новые методы моделирования

квазиструктурированной информации, новые-нравила поддержания ссылочной

целостности, новые методы манипулировав^ й^форй^цией. -д. - .

Т Библиотека I

!

**" А

Объектом исследования являются математические методы реляционной теории управления большими объемами квазиструктурированной информации.

Научная задача заключается в разработке математических методов эффективного управления большими объемами квазиструктурированной информации.

Цель и задачи работы. Целью настоящей диссертационной работы является развитие и обоснование математических методов реляционной теории для эффективного управления большими объемами информации предметных областей с полностью неопределенными структурами.

Для достижения поставленной цели были решены следующие задачи:

1. Проанализированы существующие методы реляционной теории управления информацией, в том числе моделирование квазиструктурированных данных.

2. Разработан формальный математический аппарат нормализации реляционных отношений на основе операций выборки и соединения, в результате чего была получена структура РБД, содержащей квазиструктурированные данные.

3. Введено понятие роли реляционного отношения как идентификатора отдельного ссылочного пути на любой паре отношений, на основе чего спроектирована уточненная структура РБД, нормализованной на основе операций выборки и соединения.

4. Определена методика проектирования РБД, нормализованных на основе операций выборки и соединения. Определен алгоритм перевода ЕЯ-диаграмм в полученную структуру.

5. Определены правила поддержания ссылочной целостности и использования М1ЛХ-значений в РБД, нормализованных на основе операций выборки и соединения.

6. Определены особенности языка манипулирования данными полученной структуры. Определен синтаксис, ВОТ-грамматика, правила использования инструкций языка.

7. Для инструкции выборки данных определены алгоритмы поиска информации в РБД нормализованных на основе выборки и соединения.

8. Определены методы проектирования распределенных РБД нормализованных на основе операций выборки и соединения.

9. Определены методы администрирования доступа к информации РБД на основе реляционной операции выборки.

10. Построена математическая модель задачи оптимизации вычислительного процесса в многопользовательских системах обработки информации и управления, построенных на основе РБД, нормализованных на основе операций выборки и соединения.

11. Показаны результаты использования полученных результатов в автоматизированных системах управления (АСУ) учебным процессом

Методы исследования. При решении поставленных в диссертационной работе задач использовались- методы теории реляционной модели данных, методы теории множеств, методы теории графов, методы математического

моделирования, методы теории вероятностей и математической статистики, методы построения вычислительных систем и программирования.

Основные положения, выносимые на защиту. В работе получены и выносятся на защиту следующие основные положения и результаты, характеризующиеся научной новизной:

1. Методы моделирования квазиструктурированной информации и структурная часть РБД, нормализованных на основе операций выборки и соединения.

2. Целостная часть РБД, нормализованных на основе операций выборки и соединения.

3. Синтаксис, BNF-грамматика, правила использования инструкций языка манипулирования данными РБД, нормализованных на основе операций выборки и соединения.

4. Алгоритмы поиска информации в РБД, нормализованных на основе операций выборки и соединения.

5. Алгоритм перевода ER-диаграмм в структуру РБД, нормализованных на основе выборки и соединения.

6. Алгоритмы перевода РБД в структуру баз данных, нормализованных на основе операций выборки и соединения.

7. Методы проектирования распределенных РБД, нормализованных на основе операций выборки и соединения.

8. Методы администрирования доступа к информации РБД на основе реляционной операции выборки.

' 9 Комплекс программ проектирования и обеспечения функционирования

РБД, нормализованных на основе операций выборки и соединения.

10. Математическая модель задачи оптимизации вычислительного процесса в многопользовательских системах обработки информации и управления, построенных на основе РБД, нормализованных на основе операций выборки и соединения.

Практическая ценность результатов диссертационной работы заключается в создании программного комплекса (на платформе MS SQL Server 2000 + Visual C#.NET), поддерживающего работу с нормализованными на основе операций выборки и соединения РБД, модификация и анализ содержимого которых доступны на уровне конечного пользователя. Тем самым существенно повышаются скорость разработки, внедрения, модификации и сопровождения приложений РБД.

Достоверность полученных результатов работы подтверждается корректным использованием теоретических и практических методов обоснования полученных результатов. Основные выводы и положения диссертационной работы обоснованы использованием при их получении известных, Проверенных практикой моделирования на ЭВМ теоретических методов исследования, базирующихся на принципах теории реляционной модели данных, теории множеств, теории графов, теории вероятностей и математической статистики, программирования, а также применением разработанных методов при решении конкретных задач предприятия, что подтверждается актами внедрения результатов работы.

Реализация и внедрение результатов работы. Полученные в диссертационной работе результаты реализованы и внедрены:

1) в Северо-Кавказском государственном техническом университете (СевКавГТУ) г. Ставрополя;

2) в филиалах СевКавГТУ в городах Невинномысске, Георгиевске, Пятигорске, Кисловодске;

3) в Северо-Кавказском гуманитарно-техническом институте (СевКавГТИ) г. Ставрополя;

4) в Народном Шпаковском Транспортном Предприятии (НШТП) г. Михайловска.

Апробация результатов работы. Основные этапы работы докладывались и обсуждались на 17 научных конференциях и семинарах. По итогам IV Международной научно-технической конференции «Кибернетика и технологии XXI века» (Воронеж, 2003 г) работы награждены дипломом за лучший доклад конференции.

Публикации. По теме диссертации автором опубликовано 49 печатных работ.

Структура и объем работы. Материал основной части диссертационной работы изложен на 210 страницах машинописного текста Диссертация состоит из введения, семи разделов, заключения, списка литературы из 199 наименования, 27 рисунков, 34 таблиц и 5 приложений. Всего 256 страниц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность представленных исследований, сформулированы цели и задачи, решаемые в работе, изложены основные положения, выносимые на защиту. Кратко рассмотрено содержание разделов диссертации.

В первой главе проведен анализ литературных источников по теории реляционной модели данных и методике проектирования и обеспечения функционирования РБД. Определены понятия предмета исследования — структурная часть, целостная часть и манипуляционная часть реляционной модели данных, понятие сущности и взаимоотношения данных, нормальные формы, квашструктурированные данные, реляционная алгебра, реляционные операции, языки манипулирования информацией, архитектуры РБД.

Аналитический обзор литературных источников показывает, что теоретическая часть реляционной модели данных имеет серьезное математическое обоснование, фундаментом которой является теория множеств. Всякая ПО может быть описана конечным набором реляционных отношений. В этой связи РБД получили широкое распространение в различных областях человеческой деятельности.

Любую систему РБД принято рассматривать как совокупность трех частей: структурной, целостной и манипуляционной.

Структурная часть определяет понятия домена; отношения, построенного на множестве доменов; кортежей; атомарных значений. Определяет правила использования системы ключей.

Целостная часть рассматривает вопросы согласования ключей отношений. Определяются потенциальные, первичные, внешние ключи. Определяются

правила ссылочной целостности, необходимые для поддержания согласованных копий внешних ключей, которые обычно представлены либо ограничением выполнения, либо каскадным обновлением ключевой информации. Вводится понятие NULL-значений.

Манипуляционная часть представлена реляционным исчислением, наиболее значимыми видами которого являются исчисление кортежей и исчисление доменов; и реляционной алгеброй, замкнутой на понятии отношения.

Для построения корректных РБД применяется методика нормализации реляционных отношений. Нормализация отношений представляет собой формализованный подход в виде аксиом и теорем нормализации, проектирования схемы данных ПО.

Для доступа к информации РБД применяются специальные языки манипулирования данными, среди которых предпочтение отдается декларативным языкам. В настоящее время наибольшее распространение получил язык SQL.

Для повышения надежности реляционных систем и оперативности доступа к информации могут быть реализованы различные подходы к архитектуре РБД, такие как файл-серверная, клиент-серверная архитектуры, реализация параллельных и распределенных РБД. Для реализации распределенных и параллельных РБД существует несколько подходов: горизонтальная фрагментация или вертикальная фрагментация таблиц, репликация данных, комбинированные подходы.

В задачах обработки информации с нечетко определенной структурой применяют моделирование квазиструктурированных данных, что позволяет строить РБД стандартной структуры, при этом ПО представляется в виде графа. Для доступа к квазиструктурированным данным разработаны специализированные языки: графовые языки G, G+ и GraphLog и языки запросов к квазиструктурированным данным Lorel, UnQL, StruQL, YATL, XQL, Quilt, X-Query и др. Основное применение описываемые РБД нашли как средство интеграции и преобразования данных из различных источников, например, WWW-ресурсов.

Во второй главе с целью описания ПО с полиостью неопределенными структурами проектируется РБД на основе операций выборки и соединения.

Детальное изучение вопросов, связанных с проектированием и обеспечением функционирования РБД, позволяет определить основные проблемы, связанные с классической методикой нормализацией отношений на основе операций проекции и соединения.

Проблема Ml: определение полноты и законченности структуры РБД. Связано это с тем, что изменение структуры информации на входе в реляционную систему может менять структуру последней. Данная проблема возникает вследствие того, что проектирование РБД начинается с отношения, находящегося в первой нормальной форме (НФ), число атрибутов которого является конечным числом. В случае достаточно полного описания ПО в процессе эксплуатации РБД у различных сущностей могут проявляться новые свойства, и вслед за ними должна меняться структура определенных отношений. Появление новых атрибутов отношений приводит к пересмотру зависимостей

между атрибутами и непременному изменению структуры отношений. Под изменениями структуры РБД понимается выполнение операций добавления и удаления таблиц, а также изменение структуры таблиц: добавление, удаление столбцов и переопределение доменов. Как правило, пользовательский интерфейс приложений не в состоянии справится с поставленной задачей, и конечным пользователям РБД приходится обращаться за помощью разработчиков В действительности описываемая проблема является еще более широкой:

1. Реляционные системы проектируются таким образом, что конечному пользователю доступны лишь операции по изменению содержимого строк таблиц- добавление, удаление строк и изменение их содержимого. Аналогично определяется бизнес-логика приложений и разрабатывается пользовательский интерфейс доступа к данным.

2. Изменение структуры таблиц приводит к пересмотру бизнес-логики и внесению изменений в пользовательские приложения.

3. Из-за различия выполняемых функций реляционная система интуитивно воспринимается по-разному на различных уровнях абстракции: разработчика РБД, программиста приложений, конечного пользователя.

Проблема №2 наличие ЫиЬЬ-значений в таблицах. Разрешение на использование ЖЛХ-значений для описания отсутствующей информации приводит к пересмотру бизнес-логики приложений. Использование ?ЧиНазначений в полях ключей усложняет контроль целостности реляционных систем и приводит к пересмотру правил ссылочной целостности.

Проблема №3: отсутствие прямого отображения иерархических сущностей и взаимосвязей типа «многие-ко-многим». Реляционная модель решает эту проблему посредством дополнительных соглашений об использовании системы ключей. При отображении сущности ПО, представляющей собой иерархическую структуру, в таблицу РБД, согласно определению внешнего ключа, добавляется дополнительный атрибут, являющийся внешним по отношению к первичному ключу этой же таблицы, либо используют множественную модель деревьев. Между объектами реального мира достаточно часто встречаются взаимосвязи типа «многие-ко-многим», которые'непосредственно не могут быть отражены в реляционной системе. Разработчикам в такой ситуации приходится создавать дополнительные таблицы, содержащие первичные ключи исходных таблиц. Таким образом, взаимоотношения типа «многие-ко-многим» заменяются совокупностью взаимоотношений типа «один-ко-многим».

Любая ПО может быть отображена в реляционной системе конечным числом отношений, находящихся как минимум в 1НФ. Таким образом, при проектировании РБД разработчик взаимодействует одновременно с двумя ПО:

1. Экспертная ПО, для которой требуется построить, по возможности, правдоподобную модель. Будем называть данную ПО — внутренней.

2. ПО реляционной модели данных. Будем называть данную ПО — внешней.

Если внутренние ПО могут значительно отличаться друг от друга в различных реляционных системах, то внешняя остается постоянной и обладает строго определенными свойствами, описанными в теории реляционной модели данных. Возможность нормализации внешней ПО позволит формализовать

работу групп разработчиков и решить представленные ранее проблемы проектирования и обеспечения функционирования РБД.

Минимальной информационной единицей реляционной системы является атомарное значение единичного атрибута отдельного отношения. Любое такое атомарное значение согласно определениям понятия зависимости, если не является независимым, то вступает в некоторые отношения со значениями других атрибутов. Зависимости могут быть одного из следующих типов:

• функциональные зависимости;

• транзитивные зависимости;

• многозначные зависимости;

• зависимости соединения.

На множестве атомарных значений ПО можно построить ориентированный граф связей:

С = (У,Е),

где V — конечное множество вершин (атомарных значений);

Е — множество упорядоченных пар (дуг) на V, т.е. подмножество множества УхУ; Е определено на множестве связей атомарных значений.

' Основой построения ориентированного графа связей атомарных значений является семантика исследуемой ПО. Условимся подписывать вершины значением атрибутов и обозначать дугой е-(и,у), ведущей из вершины и в вершину у: (и V) ситуацию уточняющей связи от значения потомка к значению родителя.

Пусть в некоторой ПО определено конечное множество атомарных значений К = (у,,у2,. На множестве V строится граф С, определяющий все связи Е = \е^ег,.. ,еа). Множество Е является конечным в силу конечности V. Подграф графа связей с? без потери общности может быть представлен в виде рисунка 1.

Рисунок 1 - Представление связей подмножества из 5-ти атомарных значений в виде ориентированного графа

Построение графов связей является альтернативным графическим представлением зависимостей между атомарными значениями ПО и с учетом всех значений может обладать достаточно сложной структурой. Учитывая сложности построения и машинной обработки графов, связи между атомарными значениями атрибутов отношений РБД можно представить в виде отдельного реляционного отношения.

Построим плоское отношение О, с размерностью тела 2х(т + п'), где п' -число несвязанных атомарных значений (подвешенных вершин), такое, что:

• в первый столбец снесены вершины V, такие, что е г(^))и (V, е

• во второй столбец снесены вершины V, такие, что V, € Г"'(у,). Заголовок отношения В представляет собой строку заголовков столбцов и

содержит фиксированное множество пар <имя-атрибутаимя-домена>: {<А101>,<А2:й2>}, причем каждый атрибут А} соответствует одному и только одному из лежащих в основе доменов И) 0=1,2). Домен И, определяет множество атомарных значений ПО, при этом £>, £ £>г, так как справедливо В2. {о^ыии}.

Искомое отношение й будет иметь вид таблицы 1. В ячейках таблицы 1 присутствуют ЖЛХ-значения для обозначения ситуации, когда конкретное атомарное значение не зависит от других значений рассматриваемой ПО. В этой связи кардинальное число к отношение £> равно Л = от + я', и т = 0 при п' = п.

Таблица 1 - Отношение связей атомарных значений

Значение Определено знамением

4 4*1

V/ 4*2

4*/ ыиьь

4*2 4*4

4*з 4*1

4*з 4*2

4*4

Рассмотрим множественную модель РБД. Пусть А - множество отношений, В - множество атрибутов. Всякая ПО определяется как подмножество Р/ декартово произведения АхВхУхЕ: Р, с(ахВхУх.е), при этом структура РБД определяется как подмножество Р; декартово произведения Ах В: Р2 с (ЛхВ). В общем случае, множество атомарных значений есть многозначное соответствие на множестве Р2 (/:Ут.к. реляционные отношения могут быть не достаточно нормализованы. Но даже при полной нормализации отношений, при которой всякое атомарное значение присутствует в РБД один раз, избыточное дублирование атомарных значений будет присутствовать в ключевых атрибутах при установлении соответствия внешних ключей первичным. В общем случае РБД состоит из четырех частей: отношение, связь, атрибут, значение атрибута; и может быть представлена в 1НФ с конкретными значениями указанных частей в виде таблицы 2. Отношение Д представленное в таблице 1, дополнено атрибутами: {Юг (простой идентификатор), ЮсЬ (дочерний ключ), Юраг (родительский ключ), отношение, атрибут/; связи между атомарными значениями описаны с помощью введенных атрибутов (ЮсЬ, Юраг}. Очевидно, что после преобразования Э: Р^=о. В таблице 2 представлены абстрактные данные о некоторой РБД. Без потери общности принадлежность атомарных значений к отношениям и атрибутам представлена условно. Атрибут Юг является

и

простым первичным ключом отношения й. Двойка {ЮсИ, Юраг} является альтернативным первичным ключом отношения. Атрибут ЮсИ является простым идентификатором атрибута значение.

Таблица 2 - Представление внешней предметной области в 1НФ

Юг ЮсЬ Юраг Отношение Атрибут Значение

4

п 1 2 о. А, V,

п+1 1 3 О, А, VI

п+2 2 ыиьь Л/+/

п+3 3 5 ом Л/+/

п+4 4 2 о, Ам

п+5 4 3 о, АН2 Ум

п+6 5 о1+2 Анз У/+4

...

Представленное отношение, назовем его связь, находится в 1НФ, так как в его полях отсутствуют повторяющиеся группы. Отношение связь {Юг, Юраг, Отношение, Атрибут, Значение, ЮсИ} содержит атрибуты:

• Юг — первичный ключ, идентификатор связи (в простейшем случае — счетчик). Связь двух значений атрибутов в модели данных внутренней ПО представлена двойкой {Юраг, ЮсЬ}, т.е. всякое значение может быть определено ноль, одним и более другими значениями и оно само может определять ноль, одно и более значений. Допустимо описание связей атомарных значений другими способами, например, множественной моделью деревьев. Двойка {Юраг, ЮсЬ) — это формализованное описание реляционной зависимости любого рода.

• Отношение — информативный атрибут, определенный на домене множества отношений внутренней ПО.

• Атрибут — информативный атрибут, определенный на домене множества атрибутов отношений внутренней ПО.

• Значение — информативный атрибут, определенный на домене множества атомарных значений атрибутов отношений внутренней ПО.

• ЮсИ — идентификатор атомарного значения, на которое могут ссылаться другие значения (в простейшем случае — счетчик).

• Юраг — идентификатор родительского значения, на которое ссылается некоторое значение, указанное в ЮсИ. ЖЛХ-значения в полях данного атрибута означают независимость некоторого атомарного значения внутренней ПО от других значений. Ситуацию независимости значения можно смоделировать посредством указания егЬ идентификатора в каждом из атрибутов подмножества {Юраг, ЮсИ}. Последний способ является более предпочтительным, т.к., во-первых, позволяет полностью отказаться от использования в РБД N11IX-значений, во-вторых, позволяет напрямую выполнять операцию соединения связанных отношений по атрибуту Юраг. В противном случае при использовании инструкций запросов к РБД независимые атомарные значения ПО можно выбрать только подзапросом.

Таким образом, основная идея проектирования РБД заключается в построении плоского отношения зависимостей между атомарными значениями внутренней ПО и последующей его нормализации. Проведение стандартной процедуры нормализации отношения £> позволяет определить структуру РБД, представленную на рисунке 2.

Полученные в процессе нормализации результаты очень хорошо согласуются с реляционными моделями, содержащими квазиструктурированные данные. Анализ полученной схемы показывает, что основными объектами ПО реляционная модель данных являются отношения, атрибуты, атомарные значения, связи атомарных значений. Спроектированная структура обладает двумя основными недостатками. Во-первых, она не совсем адекватно описывает особенности ПО, т.к типы всех связей между объектами предполагаются «один-ко-многим». Такие связи являются частным случаем связей «многие-ко-многим». В общем случае сущности атрибут и атомарное значение связаны взаимоотношением «многие-ко-многим»: одному атрибуту могут принадлежать несколько атомарных значений и одно атомарное значение может принадлежать нескольким атрибутам. Во-вторых, между отношениями внутренней ПО может существовать более одного ссылочного ограничения. Эти ссылочные ограничения могут быть как сонаправленными, так и циклическими. В полученной структуре данная информация потеряна, поэтому описанный ранее метод нормализации отношения связей атомарных значений требует доработки, а полученная модель уточнения структуры.

Связь

'Юг Сраг ЮсЪ

5-*

Значение *ЮсЬ

Значение

Отношение

*Юо Отношение

Рисунок 2 - ЕЯ-диаграмма ПО реляционная модель данных

В третьей главе рассматриваются основные свойства РБД, нормализованных на основе операций выборки и соединения.

Показано, что восстановление отношений внутренней ПО осуществляется посредством операций выборки и соединения, т.е. представленная модель данных является «выборочно-соединительной».

Пусть существует отношение Я {А, В, С}, соответствующее внутренней ПО,

содержащее кортежи {{а1, Ы, с1}.....{ап, Ьп, сп}}, где п — кардинальное число Л.

Пусть согласно проекционно-соединительной теории нормализации Я {Л, В, С} может быть заменено проекциями: {А, С} и {А, В}. Исходное отношение Л может быть восстановлено как соединение (А, С} и (А, В} по атрибуту А.

В структуре, представленной на рисунке 2, R {А, В, С} заменяется совокупностью кортежей: отношение {1.R}, атрибут {{1,1,А}, {2,1,В}, {3,1,С}}, значение {{1,1,al}, {2,2,Ы}, {3,3,cl},...,{m-2,l,an}, {т-1,2,Ьп}, {т,3,сп}}, где

т<3*п, и связь {{1,1,2}, {2,1,3}.....{1-1,т-2,т-1},{1,т-2,т}}, где ¡<,7*п. Здесь и

далее, для простоты представления информации, в качестве первичного ключа отношений внешней ПО используются уникальные значения счетчика.

Физический смысл неравенства т<ъ*п заключается в следующем. Максимальное число атомарных значений отношения R {А, В, С} составляет а*п, где а=3 — степень R. Пусть t — число NULL-значений в полях атрибутов, не являющихся первичным ключом. В модели, представленной на рисунке 2, NULL-значение в поле атрибута отношения внутренней ПО не заносится в отношение значение, т.е. не добавляется новый кортеж в значение и соответственно в связь. Таким образом, число кортежей отношения значение т составляет т = a*n-t или тИ*п, аналогично для числа кортежей / отношения связь справедливо 1йЬ*п, где 6=2 — число зависимостей в одном кортеже R.

В данной постановке отношение R {А, В, С} восстанавливается как соединение по атрибуту значение выборки значение.значение из соединения по совпадающим ключам отношений отношение, атрибут, значение, связь для отношение.отношение=Д и/или {атрибут, атрибут =А, атрибут, атрибут=В, атрибут, атрибут -С}.

7 На SQL запрос имеет вид:

SELECT а.Значение as А, Ь.Значение as В, с.Значение as С FROM связь,

► (SELECT Значение* FROM Значение, Атрибут WHERE

Атрибут. Атрибут^'А' and Значение.ГОа=Атрибут.ГОа) а, (SELECT Значение.* FROM Значение, Атрибут WHERE

Атрибут.Атрибут='В' and Значение.ГОа=Атрибут.ГОа) Ь, (SELECT Значение.* FROM Значение, Атрибут WHERE

Атрибут.Атрибут='С' and Значение.Ша= Атрибут.IDa) с, WHERE а.ГОсЬ=связь.ГОсЬ and Ь.ЮсЬ=евязь.ГОраг and с.ГОсЬ=связь.[Г>раг

Пусть согласно проекционно-соединительной теории нормализации отношение R {А, В, С} без потери информации может быть заменено проекциями: Х{А, С}, состоящим из кортежей {{al, cl},..., {ах, сх}}, х<п и У {А, В}, состоящим из кортежей {{al, Ы },...,{ay, by}}, у<,п. Значит, данная операция должна быть выполнима по отношению к структуре, представленной на рисунке 2. Действительно, после нормализации в новую структуру заносятся кортежи: отношение {{1,Х}, {2,Y}}, атрибут {{1,1,А}, {2,1,С}, {3.2.А}, {4,2,В}}, значение

{{1,1,al}. {2.2,cl}.....{2х-1,1,ах}, {2х,2,сх}, {2х+1,1,а1}, {2х+2,2,Ы}.....{у'-1,1,ау},

{у',2,by}}, у' - 2х + 2у, и связь {{1,1,2}.....{х,2х-1,2х),{х+1,2х+1,2х+2}.....

{у'/2,у-1,у-}}.

В данной постановке отношение R {А, В, С} восстанавливается как соединение по атрибуту значение двух выборок, таких что:

• выборка 1 — выборка значение.значение из соединения по совпадающим ключам отношений отношение, атрибут, значение, связь для отношение, отношение =Х;

• выборка 2 — выборка значение значение из соединения по совпадающим ключам отношений отношение, атрибут, значение, связь для отношение. отношение=У.

На SQL запрос имеет вид: SELECT d.Значение as А, ¿.Значение as В, с.Значение as С FROM связь связь 1,

(SELECT а.3начение as А, Ь.Значение as В, a.IDch FROM связь,

(SELECT Значение.* FROM Значение, Атрибут, Отношение WHERE Отношение.Отношение='Х' and Отношение.Шо=Атрибут.Шо and Атрибут.Атрибут='А' and Значение.ГОа=Атрибут.ГОа) а, (SELECT Значение.* FROM Значение, Атрибут, Отношение WHERE Отношение.Отношение='Х' and Отношение.ГОо=Атрибут.Юо and Атрибут.Атрибут='В' and Значение.ГОа=Атрибут.Ша) Ь, WHERE а.ГОсЬ=связь.ГОсЬ and Ь.ГОсЬ=связь.ГОраг) d, (SELECT Значение.* FROM Значение, Атрибут, Отношение WHERE

Отношение.Отношение='Y' and Отношение.ГОо=Атрибут.ГОо and Атрибут.Атрибур^С' and Значение.ГОа=Атрибут.Юа) с WHERE d.IDch=cвязьl.IDch and с.ГОсЬ=связь1.ГОраг

В отношениях выборочно-соединительной реляционной модели данных не используются NULL-значения для обозначения отсутствующей информации.

Пусть существует отношение R {А, В, С} соответствующее внутренней ПО, содержащее кортежи {{al, bl,cl},...{ai,bi,NULL},...,{an, bn, en}}, где n — кардинальное число R. Пусть согласно проекционно-соединительной теории нормализации R {А, В, С} может быть заменено проекциями: {А, С} и {А, В}. Исходное отношение R может быть восстановлено как соединение {А, С} и {А, В} по атрибуту А.

В структуре, представленной на рисунке 2, R {А, В, С} заменяется совокупностью кортежей отношение {1,R}, атрибут {{1,1,А}. {2,1,В}, {3,1,С}},

значение {{1,1,al}, {2,2,Ы}, {3,3,cl}.....{¡'-1,1,ai}, {Г,2,Ы}.....{т-2,1,ап}, {т-

1,2,Ьп}, {т,3,сп}}, где т<7>*п, и связь {{1,1,2}, {2,l,3},...,{i",i',i'-l},...,{l-l,m-2,m-1},{1,т-2,т}}, где /<2*л. При таком подходе число кортежей значение и связь уменьшается. В данном случае содержимое отношений предложенной структуры будет следующим: отношение {{!,Х}, {2.Y}}, атрибут

{{1,1.А}, {2,1,С}, {3,2,А}, {4,2,В}}, значение {{1,1,al}, {2,2,cl}.....{2х-1,1,ах},

{2х,2,сх}, {2х+1,1,а1}, {2х+2,2,Ы}.....{j-l,3,ai},{j,4,bi},...{y'-l,l,ay}, {у\2,Ьу)}, и

связь {{1,1,2},...,{х,2х-1,2х},{х+1,2х+1,2х+2}.....0'ПЛ-{у'/2,у'-1,у'}}-

Для корректного отображения объектов реального мира в выборочно-соединительной реляционной модели данных должны выполняться правила ссылочной целостности. При этом достаточно выполнения правил ссылочной целостности для отношений внешней ПО, правила ссылочной целостности для внутренней ПО вводятся дополнительно на основе операций выборки и соединения. Для внешней ПО, как нормализованной классическим образом, должны быть определены правила внешних ключей. Эти правила определяются для множества первичных ключей {IDo, IDa, IDpar, IDzj и соответствующих им внешних ключей.

Для ссылочного пути связь—>значение—>атрибут—>отношение целесообразно установить правило каскадирования операций удаления и обновления.

В качестве второй системы ключей представленной реляционной структуры может выступать система ключей внутренней ПО, которая после процедуры нормализации будет преобразована в множество кортежей отношения атрибут. Соответствующие значения ключей отношений внутренней ПО будут преобразованы в кортежи отношений значения, связи - в кортежи отношения связь. В результате образуется две системы ключей:

• Система ключей внутренней ПО, представленная кортежами отношений атрибут, значение, связь. В данном случае правила ссылочной целостности, помимо указанных ранее, должны накладываться на кортежи отношения связь.

• Система ключей внешней ПО, представленная атрибутами {Юо, Юа, Юраг, Юг}.

Таким образом, всякое атомарное значение информативного атрибута отношения внутренней ПО в любой момент времени зависит по ссылке от атрибута первичного ключа отношения из множества {Юо, Юа, Юраг, Юг} и от значения соответствующего кортежа, которое является первичным ключом отношения внутренней ПО, представленного в виде кортежа в связь. Если уже определены правила ссылочной целостности для отношений внешней ПО, то вторая система ключей может быть удалена из системы. При этом следует ввести дополнительные ограничения:

1. Отношение связь должно быть перестроено для отображения зависимостей значений информативных атрибутов внутренней ПО от ключей внешней ПО {Юраг, ЮсИ}.

2. Во внутренней ПО могут существовать особые возможности согласования системы ключей отношений. Эти правила должны накладываться на выборки ключей из отношения связь.

Второе замечание является очень важным при выборочно-соединительном подходе к нормализации. Пусть существуют два отношения внутренней ПО Л/ {А}, где А — информативный атрибут, содержащее кортежи {а!,...,а1'}, и К2 {В}, где В — информативный атрибут, содержащее кортежи {Ы, ...,Ь}}. При этом объекты {Ы,...,Ь}} некоторым образом зависят от {а1, ...,ах}, т.е. Я2—>Я1. Согласно предложенной структуре имеем: отношение {{!Д1}, {2,112}}, атрибут

{{1,1,А}, {2,2,В}}, значение {{1,1,а1}.....{И,а1}, {¡+1,2,Ы}.....0+].2,ЬЛ}, и связь,

например, {{1,1,1+1},. ,,{х,Ц+]}}. Ограничение ссылочной целостности должно быть наложено на выборки из связь, связанные с выборками по первичному ключу Юраг из значение /7,—>{'1+1,...,/+/'}■

Пусть выполняется операция удаления кортежа отношения значение. Согласно последнему определению предварительно должна быть выполнена операция выборки из связь по первичному ключу Юраг, соответствующему удаляемому кортежу. Возможны 3 варианта удаления:

1. Операция удаления только первоначального кортежа проводится тогда и только тогда, когда выборка пуста.

2. Из значение удаляются дополнительные кортежи по ключу ЮсН тогда и только тогда, когда действует правило каскадного удаления для отношений

внутренней ПО и выборка не пуста. Программно каскадирования операции удаления кортежей из значение организуется с использованием механизма рекурсии.

3. Операция удаления ограничивается тогда и только тогда, когда действует правило ограничения удаления для отношений внутренней ПО и выборка не пуста.

Аналогично определяются правила для операции обновления

Определены домены атрибутов отношений РБД, нормализованных на основе операций выборки и соединения.

В четвертой •гливе проектируется уточненная структура РБД, нормализованных на основе операций выборки и соединения.

Приводится формальный алгоритм перевода ЕЯ-диаграммы внутренней ПО в выборочно-соединительную РБД:

1 Определяются типы взаимоотношений между сущностями. Все взаимоотношения типа «один-к-одному», «один-ко-многим», «многие-ко-многим» и иерархические взаимоотношения между сущностями ПО не изменяются.

2. Для сущностей, не содержащих информативных атрибутов, могут быть введены дополнительные атрибуты. В противном случае сущность не преобразуется в РБД, а для поддержания целостности соответствующих данных будет использоваться система ключей внешней ПО

3 Выбирается система ключей внешней ПО, в качестве которой могут быть выбраны значения счетчиков для атрибутов {Юо, Юа, Юраг, Юг}.

4. Для каждой сущности ЕЯ-диаграммы создается кортеж в отношении отношение.

5. Для каждого атрибута создается кортеж в отношении атрибут, связанный с соответствующим кортежем отношения отношение. После выполнения данного этапа создается структура внутренней ПО.

6. При заполнении полученной структуры создаются кортежи в отношении значение, связанные с соответствующими кортежами в отношении атрибут.

7. При заполнении отношения связь руководствуются типами взаимоотношений между соответствующими сущностями ЕЯ-диаграммы.

В РБД нередко встречаются особые случаи связей пар отношений, когда в дочернем отношении присутствуют более одного внешнего ключа по отношению к первичному ключу родительского отношения, или существует несколько альтернативных ссылочных путей между двумя отношениями. В таких случаях родительское отношение выступает одновременно в нескольких ролях по отношению к дочернему отношению. Под ролью будем понимать описание одной такой конкретной связи

В разработанной ранее структуре РБД (рисунок 2) отношение связь построено из «безликих» зависимостей между значениями атрибутов отношений. Реализация возможности существования более одной связи между отношениями должна бьпь проведена за счет системы ключей внешней модели Для этого должны быть проведены дополнительные изменения структуры, за счет дополнения отношения Д представленного в таблице 2, информативным атрибутом Роль Нормализация полученного отношения проводится

классическим методом на основе операций проекции и соединения. В результате нормализации получим РБД со структуррй, представленной на рисунке 3.

Связь

*Ю2 Ораг

ЮсН

Вэгъ

иг

Оэ Рогь

Значение

*ЮЛ1 Значение

Отношение

"Юо Отношение

Значение_атри0у1 ю—(■

*ЮсИ Юл1 Сею

Атрибут_роль

ТСао

Сг

Оа

Атрибут

*Оа

Атрибут

Рисунок 3 - Уточненная структура реляционной модели данных

Анализ полученной структуры показывает, что решены основные проблемы, свойственные структуре, представленной на рисунке 2:

1. Между отношениями: значение и атрибут, значение и отношение, атрибут и роль, реализованы самые полные связи типа «многие-ко-многим».

2. В структуре возможна реализация любого количества ссылочных путей между произвольными значениями, посредством введения отношения роль, т.е. всякому единственному атомарному значению, может быть сопоставлен 0, 1 или более кортежей в отношении значение_атрибут, соответствующие различным

» ролям, и участвующие в различных связях.

Уточненная структура реляционной модели данных позволяет решить значительную проблему при проектировании РБД — идентификации связи между двумя атомарными значениями в ситуациях, когда таких связей множество. Сюда относятся не только случаи непосредственной связи двух отношений, но и множественные связи двух отношений через любое число промежуточных (существование альтернативных ссылочных путей).

Отношения, .соответствующие сущностям ЕЯ-диаграммы, представленной на рисунке 3, имеют следующий физический смысл:

• Отношение — каждый кортеж соответствует некоторому отношению внутренней ПО.

• Роль — каждый кортеж соответствует некоторой роли отношения внутренней ПО.

• Атрибут — каждый кортеж соответствует некоторому атрибуту отношения, не роли, внутренней ПО.

• Атрибут_роль — данное отношение добавлено для устранения связи типа «многие-ко-многим» между ролью и атрибутом. Несколько ролей одного отношения внутренней ПО содержат идентичный набор атрибутов.

• Значение — каждый кортеж соответствует некоторому атомарному значению атрибута отношения внутренней ПО. Данное значение имеет единственную копию в отношении значение, но может ссылаться на множество атрибутов множества ролей отношений.

• Значение_атрибут — данное отношение добавлено для устранения связи типа «многие-ко-многим» между отдельными значениями и атрибутами ролей.

• Связь — каждый кортеж описывает связь между двумя отдельными значениями отношений внутренней ПО.

Рассмотрены практические вопросы использования РБД с уточненной структурой, нормализованных на основе операций выборки и соединения, при моделировании ПО «учебный процесс». В результате проектирования выявлено, что использование новой структуры позволяет избежать недостатков, описанных в главах 1 и 2.

В пятой главе рассматриваются основные свойства РБД с уточненной структурой, нормализованных на основе операций выборки и соединения.

РБД с уточненной структурой, нормализованные на основе операций выборки и соединения, помимо представленных ранее, обладают рядом дополнительных свойств.

При использовании уточненной структуры РБД в виде, представленном на рисунке 3, требования к обязательной нормализации отношений внутренней ПО неактуальны Достаточным условием отсутствия аномалий обработки информации является единственность существования соответствующего кортежа в отношении значение. Достаточно иметь единственную копию всякого отдельного атомарного значения в отношении значение и несколько зависимых *

кортежей в отношении значение_атрибут в случае реализации в системе ненормализованного отношения внутренней ПО. В случае изменения единственной копии отдельного атомарного значения при восстановлении исходного отношения измененное значение будет присутствовать во всех соответствующих полях атрибутов.

Основное отличие выборочно-соединительного от проекционно-соединительного метода проектирования РБД заключается в способе обобщения множества однотипных атомарных значений ПО:

1. Проекционно-соединительный метод, называемый нормализацией, подразумевает обобщение множества однотипных атомарных значений понятием «отношение». Результатом такого обобщения является появление проблемы ЫиЬЬ-значений: не во всех однотипных подграфах С может присутствовать один и тот же фиксированный набор значений атрибутов.

2. Выборочно-соединительный метод подразумевает обобщение множества атомарных значений кортежами отношения значение, а множество связей кортежами отношения связь.

РБД, представленная на рисунке 3, позволяет реализовать в своей структуре любую другую РБД, т.е. может быть определен формальный алгоритм такого преобразования.

Алгоритм перевода РБД (конвертируемая РБД) в РБД с уточненной структурой, нормализованную на основе операций выборки и соединения:

1. Для всякого отношения конвертируемой РБД создается кортеж в отношении отношение В атрибуте отношение.отношение указывается название конвертируемого отношения.

2. Определяются все максимальные ссылочные пути с участием отношения конвертируемой РБД. Для каждого пути создается кортеж в отношении роль, связанный с соответствующим кортежем отношения отношение. В качестве названия роли может быть выбрано название отношения с порядковым номером пути.

3. Для всякого атрибута отношения конвертируемой РБД, за исключением атрибутов внешних ключей, создается кортеж в отношении атрибут. В атрибуте атрибут, атрибут указывается название конвертируемого атрибута.

4. В отношении атрибут_роль прописываются взаимосвязи между соответствующими ролями и атрибутами.

5. Для всякого атомарного значения отношения конвертируемой РБД, не являющегося ЖЛХ-значением, создается кортеж в отношении значение. В атрибуте значение.значение указывается соответствующее атомарное значение

6. В отношении значение_атрибут прописываются взаимосвязи между соответствующими атрибутами ролей и атомарными значениями.

7. Определяются связи между атомарными значениями внутри отношения конвертируемой РБД. В отношении связь прописываются взаимосвязи между атомарными значениями на основе информации отношения значение_атрибут.

8. Для всякой связи между отношениями конвертируемой РБД определяются пары {первичный ключ, внешний ключ}. Информация полученного отношения используется для заполнения отношения связь на основе информации отношения значение_атрибу т. Связи между кортежами отношений конвертируемой РБД в отношение связь заносятся парами {первичный ключ родительского отношения, первичный ключ дочернего отношения}.

Для реализации п.2 алгоритма перевода РБД в РБД с уточненной структурой, нормализованную на основе операций выборки и соединения, предложен алгоритм определения ролей отношений и последующей модификации графа связей отношений РБД.

Для реализации алгоритма рассматривается граф связей конвертируемой РБД Для иллюстрации работы алгоритма рассмотрим следующий граф связей, в котором отражены все возможные ситуации ссылочных путей между отношениями (см. рисунок 4).

А Е

Рисунок 4 - Граф связей 5-ти реляционных отношений

На шаге 1 для устранения циклических ссылочных ограничений определяются все подграфы исходного графа, у которых совпадает источник и сток (при этом пути вида Rr->Rr~>■■—>Rn—>Rh Л^—>Лг->..—>ЛЯ—>Л2 и

подобные будем считать определением одного и того же циклического ссылочного ограничения), а затем разделяется одна из вершин, участвующая в циклическом ссылочном ограничении так, что первая будет ассоциирована только с исходящими дугами, а вторая только с входящими. На данном графе таких циклов два: А—>С—>Е—>А и А—>В—>С—>Е—>А, разделение вершин Е на Е/ и Е2 так, что вершина Е/ будет ассоциирована только с исходящими дугами, а Е2 только с входящими избавит исходный граф от циклических ссылочных ограничений.

На шаге 2 производится анализ и модификацию графа для выявления альтернативных ссылочных путей, для чего строится таблица связей отдельных отношений (таблица 3). В ситуациях непосредственной достижимости узлов Л„—>/?„., и наличия между ними альтернативных ссылочных ограничений идентификаторы родительских отношений будем нумеровать числами натурального ряда.

Таблица 3 - Связи отдельных отношений

Определяющее (родительское) Зависимое (дочернее) отношение

отношение

А Е,

В, А

В2 А

С А

С В

£> В

С

е2 С

На шаге 3 алгоритм анализирует все ссылочные пути между всеми парами отношений. На основе анализа таблицы 3 определяются следующие ссылочные пути для всех пар отношений: А->Е,: {А->Е,};

В->Ег: {В,->А->Е,; В2->А->Е,};

С->Е]: (С->А->Е,; С->ВГ>А->Е,; С->В2->А->Е,};

й->Е,: {0->Вг>А->Е,; 0->В2->А->Е,; 0->С->В,->А->Е,; 0->С->В2->А->Е,};

Ег->Е,: {ЕГ>С->А->Е,; £г->С->Я,->Л->£;; ЕГ>С->ВГ>А->Е,};

В->А: {В,->А, Вг->А};

С->А: {С->А, С->В,->А, С->В2->А};

С->В: {С->В};

П->А: {0->Вг>А, 0->Вг>А, 0->С->А, 0->С->Вг>А, 0->С->Вг>А); 0->В {0->В, В->С->В}: й->С: {0->С};

ЕГ>А: {Ег>С->А, Е2->С->Вг>А, Ег>С->В2->А}; ЕГ>В: {ЕГ>С->В}; ЕГ>С. {ЕГ>С'}.

На шаге 4 определенные пути сносятся в новую таблицу, игнорируя повторяющиеся подграфы (см. таблицу 4).

Таблица 4 - Описание подграфов достижимости отношений

Роль Отношение

СВ,АЕ, Е,

СВ2АЕ, Е,

РВ,АЕ, Е,

ВВ2АЕ, Е,

ОСАЕ, Е,

ПСВ,АЕ, Е,

ЭСВгАЕ, Е,

Е2САЕ, Е,

е2св,ае, Е,

е2св2ае, Е,

Используется следующие правило именования ролей. й;Л2йз...Д„=>Л„->й„.;Я„ иЯ„ ;/?„->/?„ 211„ )И„ и .. иК2Я).. Д„

где Я,, 1=1..п- отношение ПО;

п - количество отношений, участвующих в определении роли/ соответствующем ссылочном пути.

Например, восстановим подграф, определяющий роль ОСВ2АЕ1-ОСВ2АЕг>Ег>АЕ, и АЕГ>В2АЕ, и В2АЕГ>СВ2АЕ1 и СВ2АЕ,-> ВСВ2АЕ,. Аналогично определяются подграфы, для остальных ролей.

Для исходного графа связей реляционных отношений, представленного на рисунке 4, итоговый, модифицированный граф связей ролей отношений приведен на рисунке 5.

Рисунок 5 - Граф связей ролей отношений

Если РБД имеет упрощенную структуру, представленную на рисунке 2, то при конвертации в уточненную структуру РБД, нормализованную на основе операции выборки и соединения необходимо скопировать только содержимое отношений, т.к. оно полностью описывает внутреннюю ПО Предложенная конвертация всегда возможна, в виду того, что структура, представленная на рисунке 3, позволяет хранить больше информации: арность взаимосвязей между отношениями отношение, атрибут, значение в упрощенной структуре «один-ко-многим», а в уточненной структуре — «многие-ко-многим».

Алгоритм перевода информации РБД с упрощенной структурой (конвертируемая РБД) в РБД с уточненной структурой, нормализованную на основе операций выборки и соединения:

1. Для всякого кортежа отношения отношение конвертируемой РБД создается кортеж в отношении отношение с аналогичным значением атрибута отношение .отношение.

2 Для всякого кортежа отношения отношение конвертируемой РБД создается кортеж в отношении роль с аналогичным значением атрибута отношение.отношение, связанный с соответствующим кортежем отношения отношение.

3. Для всякого кортежа отношения атрибут конвертируемой РБД создается кортеж в отношении атрибут с аналогичным значением атрибута атрибут.атрибут.

4. В отношении атрибут_роль прописываются взаимосвязи между соответствующими ролями и атрибутами.

5. Для всякого кортежа отношения значение конвертируемой РБД создается кортеж в отношении значение с аналогичным значением атрибута значение.значение.

6. В отношении значение_атрибут прописываются взаимосвязи между соответствующими атрибутами ролей и атомарными значениями.

7. На основе информации связь конвертируемой РБД заполняется ^ отношение связь на основе значения ключей отношения значение_атрибут. |

' В шестой главе разрабатываются надстройки декларативных языков <>

манипулирования данными РБД, нормализованных на основе операций выборки I

и соединения.

Для реализации инструкции запросов к РБД, нормализованным на основе операций выборки и соединения, расширяется классическая реляционная алгебра. Учитывая, что исследуемые РБД, являются реляционными по построению, можно определить их манипуляционную часть в виде классической реляционной алгебры, включающей в себя 8 операторов: А = (к,^,г\\,х,5,П,о<1,д), где « = {/?„/?,,я„й4,/г,,д6,й7} - множество отношений РБД, нормализованных на основе операций выборки и соединения {отношение, атрибут, атомарное значение, роль отношения, аттрибут_роль, значение_атрибут, связь}, и соответственно начертание операторов (объединение, пересечение, разность, декартово произведение, выборка, проекция, соединение, деление). Отметим, что информативные атрибуты содержаться в отношениях /?, («название отношения»), /?г («название атрибута»), Я; («атомарное значение»), («название роли»).

Расширим набор стандартных операторов реляционной алгебры введением оператора УР(Я) такого, что Ур(1*)={г|Р(г)}, где

г - упорядоченная тройка («название отношения», «название атрибута», «атомарное значение»);

Р(г) - отбирающий предикат.

Тогда: Ур(К) = 8Р(г)(К,)><181,((г)(К4)><Я5><]8Р1(г)(К2)><аб>48Рз(г)(К3)><1К7,

где 8,1М(Я,) - операция выборки кортежей отношения к,, удовлетворяющих условию Р,(г).

Рисунок 6 - План выполнения оператора УР(Я)

Пусть А>ЛУг)) - двухместная функция, возвращающая количество отношений, выбранное из РБД а с использованием предиката Р^г), аналогично, ^а,Р3(г)) - функция, возвращающая количество атрибутов, выбранное из РБД а с использованием предиката Рз(г),

Представление результатов оператора УР(Я) в виде упорядоченной тройки («название отношения», «название атрибута», «атомарное значение») неудобно, поэтому для восстановления исходного плоского отношения В,, М.Да.Р^г)), введем оператор Ов., такой что:

где АПУ - }-й атрибут отношения В,, ,Рз(г)).

Таким образом, в качестве манипуляционной части РБД нормализованных на основе операций выборки и соединения может использоваться алгебра вида: А = (л,и,п,\,х, в, П. Д, V, (г), Ов).

Для реализации реляционного оператора УР(Я) определим инструкцию ВЫБРАТЬ со следующей БНФ-грамматикой формулирующую запросы к БД, нормализованным на основе операций выборки и соединения: соператор запроса>::= ВЫБРАТЬ <текст> <текст>::=

<основной текст> | <основной текст> В <имя новой таблицы> | В <имя новой таблицы> <имя новой таблицы>:= <идентификаггор>

<основной тскст>::= <тело запроса> | <тело запроса> <командная строка> <тело запроса>:~ <значение выбора> | <значение выбора> ГДЕ <предикат> <командная строка>::= <команда>{ <команда>) <команда>- =

•«идентификатор команд ы> Идентификатор роли> Идентификатор атрибута>

{, <идентификатор роли> -¿идентификатор атрибута>} <идентификатор команды>..= СОРТИРОВАТЬ ПО | ГРУППИРОВАТЬ ПО <значение выбора>"~ <описание>{, <описание>) <описание>::=

■«отдельное описание>|<отдельное описание> КАК <идентификатор атрибута>

■«отдельное описание>::= <источник данных> |

«агрегативная функция> («идентификатор роли> «идентификатор атрибута>) <агрегативная функция»: :=

СУММА | КОЛИЧЕСТВО | МАКСИМУМ | МИНИМУМ «источник данных»: "«идентификатор роли> «указатель атрибута> |

«идентификатор роли> «указатель атрибута» ::= «идентификатор атрибута> | ВСЕ «предикат»::= «отдельное условие>

{«логический оператор> «отдельное условие>} «логический оператор»:.= ИЛИ | И

«отдельное условие»::= «основа условия> | НЕ «основа условия> «основа условия»:?» «простое условие> | ВОЗМОЖНО «оператор запроса> «простое условие>::=

«идентификатор роли> «идентификатор атрибута> «идентификатор значения> | «идентификатор роли> «идентификатор атрибута» «оператор отношения> «идентификатор значения»

«оператор отношения»: := > | < | = | о | «= | >= «идентификатор роли>::= «идентификатор» «идентификатор атрибута»:?3 «идентификатор» «идентификатор значения»: ~ «константа неопределенного типа» |

«идентификатор» «идентификатор»:" «буква» {«буква>|<цифра») «буква»:— А|Б|В|...|Я|... «цифра»: := 0 11 |2|...|9

«константа неопределенного типа»::= «символ»{«символ») «символ»: := А | Б | В | .. | Я |0 | 1 12 |.. |9|!|?| ..

Выполнение инструкций запросов к РБД предполагает определение некоторого подмножества атомарных значений, принадлежащих заданным атрибутам отношений, согласно заданному предикату. В предикате явным образом указываются связанные между собой логическими операциями исходные данные, представляющие собой наименование исходных атомарных значений, принадлежащих определенным атрибутам отношений. Если в качестве инструкции запросов используется SELECT языка SQL, то в предикате обязательно указание ссылочных ограничений, на основе чего компилятором строится план выполнения запроса и определяется порядок выполнения соединений. В случаях применения уточненной структуры РБД, нормализованной на основе операций выборки и соединения, согласно введенному определению роли отношения, ссылочный путь между любыми двумя атомарными значениями и/или ролями однозначен и может быть автоматически определен на основе анализа информации семи представленных отношений. Поэтому в предикате инструкции ВЫБРАТЬ не указываются явным образом ссылочные ограничения между ролями. В этом случае все ссылочные ограничения определяются автоматически на этапе компиляции, что позволяет отказаться от необходимости модификации инструкций выборки данных вследствие изменений структуры РБД.

Инструкция ВЫБРАТЬ является более высокоуровневой по отношению к инструкции SELECT и на этапе выполнения запроса может быть ею заменена. С этой целью разработано специализированное программное обеспечение, выполняющее функции компилятора, т.е. для нужд прикладных программ разработан конвертор (компилятор) перевода инструкции ВЫБРАТЬ в SELECT.

Выполнение инструкции ВЫБРАТЬ происходит как вызов функции компиляции, а сама инструкция определяется как параметр этой функции.

Задачу определения ссылочных ограничений для пары ролей определим в виде: требуется найти путь из искомой роли /?, в исходную роль Л;.

Решим задачу с использованием теории графов. На множествах ролей отношений Л и взаимосвязей между ними ^ построим ориентированный граф б = («,/=■) и перерисуем его в виде ориентированной сети С - (Л,/7). Алгоритм восстановления ссылочных ограничений на ориентированной сети С ролей отношений:

1. Выбирается вершина /?« уровня 0 (вершина с полустепенью захода равной 0), из которой достижимы вершины с исходной и требуемой ролями. Указанная задача является частной к определению обратного транзитивного замыкания /"(й,) = /"'(я,)и/"!(л,)и...) для некоторой искомой вершины и обратного транзитивного замыкания Г ) для некоторой исходной вершины, где Г' — многозначное отображение: Г1(я,)= г{г'~'(д,)}, полагая Г°(Л,)= Л, и

если /'(йу)= Д,. Если ¿>0, то Г*(Л,) — множество вершин ориентированного графа, в которые существует путь длины к из вершины Я, Если А >0, то Г — множество вершин, из которых существует путь длины к в вершину Л,.

2. Из вершины Л« определяются два простых пути к исходной Л, и требуемой Лу ролям.

3. Поисковый путь определяется как совокупность найденных двух простых путей за исключением совпадающих дуг.

Представленные задача и алгоритм ее решения могут быть сведены к определению поисковых путей на сети взаимосвязей атомарных значений.

Проблема построения ориентированной сети, т.е. расположения вершин графа на плоскости с целью визуального распределения вершин по уровням назьюается проблемой топологической сортировки и может быть решена путем вычисления порядковой функции сети на основе алгоритма Демукрона. Реализация алгоритма Демукрона в компиляторе инструкции запросов приводит к увеличению времени его выполнения. Можно повысить производительность алгоритма выборки данных в случае, если информация об ориентированной сети на момент выполнения запроса будет известна, т.е. будет вычисляться динамически согласно происходящим изменениям в исследуемой ПО. При добавлении в РБД новой роли/атомарного значения должен вычисляться соответствующий им уровень и пересчитываться уровни связанных с ними ролей/атомарных значений. Следующий алгоритм динамически вычисляет уровень ориентированной сети, которому принадлежит добавляемое атомарное значение у, и пересчитывает уровни атомарных значений, связанных с V, (для хранения номеров уровней в отношение "значение_атрибут" вводится атрибут "уровень_значения"):

1. Добавляется атомарное значение V,.

2. Атомарному значению V, ставится в соответствие уровень (/, = 0.

3. Если атомарное значение у, определено множеством К>"Л>- >УЛ}= г"'(0> соответствующим уровням сети {С/,,С2,.т.е.

= .....уу-), где (°) — упорядоченный набор, кортеж, /(») —

вычисляемое многозначное соответствие на множествах вершин и уровней сети, их =тах(с/,,с/г,. .,[/„), то V, ставится в соответствие уровень и, = и, + \.

4. Если атомарное значение V, определяет множество {у^.у^-.у*. ) соответствующие уровням сети {и„и2„..,£/„}, т.е. (и„и2,-..и„)=/{у^,^,-,^.), иу=тт(и„и2, ,ит), V, -» {у^,,. ,у,_}о Г'(у,), то для многозначного отображения Г*(у,)={г°(у,)^г1(у,)иг2(у,)^...} изменяется номер уровня

и, +/,еслиу4 = Г'(у,\и, >. /(г* (V,)} к* «

и, очевидно, что после

(У,, иначе

Г{/, +1, если С/ 5 С, вычислений '

' иначе

5. Обновляются соответствующие поля атрибута

значение_атрибут.уровень.

Алгоритм перестройки ориентированной сети при удалении атомарного значения у,:

1. Если атомарное значение у, определено множеством {уу .у^, ,.,у. }= Г"'(у,), то удаляются соответствующие дуги.

2. Если атомарное значение у, определяет множество {^.у»,, .у»„}= соответствующее уровням сети ,[/„}, то удаляются соответствующие дуги и уровни вершин у, е Г*(у,), у, # у, определяются на основе алгоритма добавления атомарных значений предметной области.

3. Удаляется атомарное значение у,.

Производительность алгоритмов восстановления ссылочных ограничений на ориентированной сети ролей/атомарных значений может быть увеличена, т.е. минимизировано время выполнения алгоритмов, если выделить подграф, соответствующий параметрам запроса, (сужение области поиска):

1. Пространство поиска может быть сужено по высоте, путем определения подмножества уровней ориентированной сети, которым принадлежат требуемые значения. При этом заранее известными данными являются принадлежности атомарных значений соответствующим ролям и уровням сети. В представленной постановке справедлива следующая теорема о выборке атомарных значений ПО. если множество искомых вершин {у^ , у у ,., V J } соответствует уровням сети

{с/л,1/л, а множество исходных вершин {у4 , ^..... Vк } соответствует

уровням сети {с/, 1/^,..} и эти вершины достижимы из одного и того же подмножества вершин {у^.у,,, ,у„ } уровня 0: (ил,ИИ,. ,. ,у, ),

К-^,. V---"*..), {№-•№>'',.....

и, = тах((УЛ,сЛ,ик1,и1г„. то операция выборки данных о может быть реализована как соединение и, выборок атомарных значений соответствующих

уровням [(Ш;] =>О = О0 [><10, ><!...><(>„_, где О, —выборка атомарных значений уровня / ориентированной сети, "х" — начертание операции соединения. Доказательство теоремы основано на определениях роли отношения и ориентированной сети.

2. Пространство поиска может быть сужено по ширине, путем определения подмножества вершин уровня 0 для исходного множества значений и последующего выделения соответствующего им подграфа значений. Теорема о выборке атомарных значений ПО с ограничением: операция выборки данных О может быть реализована как соединение £/, выборок атомарных значений соответствующих уровням [0.!;,]=> О = /Шег(0л)><01 >< ..хОи , где /Шег(ои) — операция выборки ограниченного подмножества вершин {у(0} уровня 0: кв}е ....."».)-

3. Множество атомарных значений ПО есть многозначное соответствие на множестве ролей отношений ПО:

•■"к.)-(А» .....К. ■^),{Лт1:ут1г),...,(Ат, .....

поэтому задача определения поискового пути на ориентированной сети атомарных значений может быть сведена к задаче определения поискового пути на ориентированной сети ролей отношений ПО. Теорема о соединении ролей отношений ПО: если множество искомых вершин принадлежат ролям отношений

{лУ1,ДЛ,...,яЛ}, соответствующим уровням сети ]иА,иА.....и)м\, а множество

исходных вершин принадлежат ролям отношений

соответствующим уровням сети {с/„(,£/41.....{/,_} и эти роли отношений достижимы

из одного и того же подмножества вершин {Л„,,Л„,.....*„.} уровня 0:

.....ии )= Д*л Л.....К)' К .....)= Ж,Л, ,-Л.),

с/, = «пафАд/А.....и^и^и^.....ик), то

результатом выборки данных О служит выборка атомарных значений из соединения ролей отношений Л(, таких что /(д,)е{0..£/,],

Л, е Г'(Л^) \ Г"(яш1 у = 1.м, где /'"(я^) - множество родительских ролей отношений, принадлежащих совпадающим дугам поискового пути .

Алгоритм определения поискового пути на сетях ролей отношений выполняется для каждой пары исходных и искомых ролей:

1. Для искомой роли определяется множество соответствующих ролей отношений уровня 0.

2. Для исходной роли определяется множество соответствующих ролей отношений уровня 0.

3. Определяется подмножество ролей отношений уровня 0 как пересечение определенных на шаге 1 и 2 множеств.

4. Из поисковых путей, соответствующих определенному подмножеству ролей отношений уровня 0 удаляются совпадающие дуги путей, ведущие к исходной и искомой ролям отношений.

В ситуациях, при которых не возможно определить роль отношения R0 уровня 0, из которой достижимы роли R, и R,, возможен один из двух исходов выполнения алгоритма определения поискового пути:

1. Исходные данные запроса логически не связаны, т.е. выборка пуста.

2. Исходные и искомые роли достижимы из непересекающихся подмножеств ролей отношений уровня 0 и связаны через некоторые обобщающие роли отношений. Последние могут быть определены и использованы на следующем шаге поиска в качестве исходных ролей отношений.

Показано, что однотипные запросы с использованием инструкции ВЫБРАТЬ формулируются проще по сравнению с инструкцией SELECT; их структура не изменяется при изменении структуры внутренней ПО и отсутствует необходимость использования системных функций, обрабатывающих NULL-значения.

В седьмой главе представлены методы проектирования и обеспечения функционирования распределенных РБД, нормализованных на основе операций выборки и соединения.

При создании корпоративной информационной системы, решающей различного рода задачи по автоматизации большого предприятия с множеством подразделений и удаленных филиалов, с целью увеличения эффективности всей системы, возникает потребность в разделе единой РБД на отдельные элементы. i,

Т.е. распределение единой РБД между некоторыми узлами вычислительной сети.

Показаны результаты реализации стандартных подходов к проектированию распределенных РБД применительно к РБД, нормализованной на основе ^

операций выборки и соединения:

1. Если предполагается вертикальная фрагментация исходных отношений, то содержимое отношений {Отношение, Роль} остается неизменным, отношения {Атрибут, Атрибут_роль, Значение_атрибут, Значение, Связь} подвергаются горизонтальной фрагментации.

2. Если предполагается горизонтальная фрагментация исходных отношений, то содержимое отношений {Отношение, Роль, Атрибут, Атрибут_роль} остается неизменным, отношения {Значение_атрибут, Значение, Связь} подвергаются горизонтальной фрагментации.

3. Если предполагается территориальное разнесение отношений по узлам сети, то горизонтальной фрагментации подвергаются либо все отношения, либо подмножество {Роль, Атрибут, Атрибут_роль, Значение_атрибут, Значение, Связь}.

4. При тиражировании данных в узлах сети сохраняются копии РБД, с описываемой структурой.

Таким образом, каким бы ни был метод построения распределенной РБД он сводится к горизонтальной фрагментации таблиц на основе некоторого предопределенного правила. Во всех узлах распределенной СУБД должен функционировать собственный фрагмент РБД со структурой, представленной на рисунке 3.

Предложен метод администрирования доступа к информации РБД, нормализованных на основе операций выборки и соединения, в многопользовательских клиент-серверных системах. Согласно теоретическому

аппарату построения таких РБД, рассмотренному в предыдущих разделах, информация о системных пользователях записывается следующим образом:

1. В отношение отношение добавляется запись {М,, пользователь}, где М1 — значение первичного ключа записи.

2. В отношение роль добавляется запись (М2, Ми пользователь}, где М2 — значение первичного ключа записи, а М, — значение внешнего ключа.

3. В отношение атрибут добавляется запись {М3, пользователь}, где М3 — значение первичного ключа записи.

4. В отношение значение добавляются записи о конкретных системных пользователях.

5. На основе первых четырех пунктов определяется содержимое таблиц атрибут_роль и значение_атрибут.

6. На основе первых пяти пунктов и информации о структуре ПО из таблиц отношение, роль, атрибут, атрибут_роль определяется содержимое таблицы связь.

В данной постановке, по отношению к операции выборки данных (например, выборка данных из отношения "подразделения"), согласно пользовательским полномочиям, запрос будет иметь следующую содержательную часть:

ВЫБРАТЬ подразделение ВСЕ

ГДЕ пользователь пользователь и8Е11_КАМЕ() где и8Е11_ЫАМЕ0 - функция, возвращающая имя пользователя.

Аналогично определяются правила администрирования функций добавления, обновления и удаления информации.

Строится математическая модель оптимизации параллельного вычислительного процесса применительно к многопользовательской автоматизированной системе, построенной с использованием РБД, нормализованной на основе операций выборки и соединения. Оптимальные характеристики параллельной вычислительной системы выбираются из условия достижения максимальной производительности к от числа вычислительных узлов т при ограничениях на заданную эффективность е0 е (0,1) (загрузку одиночных вычислительных узлов):

{к(т) = шах е(/фе0 1

-= шах

+ <р.т'1

■ т _ ,

V РА

где <р, е[0,оо) и р2е(-°°;°о) — экспериментально определяемые параметры для конкретных программно-аппаратных платформ.

С целью определения вида функции производительности: к = (т ' + /3(т)У использовались результаты более 200 экспериментов. Для определения вида аппроксимирующей функции к = /(т) от числа используемых процессоров на основе дискретных выборок точек (т,,к,) использовались метод наименьших

квадратов и методы выравнивания для приведения исследуемой зависимости к линейному виду. Функция ß{m) имеет вид: ß{m) = <рхт*, т.к. экспериментально показано, что коэффициент парной корреляции величин ln(m) и In(ß(m)) близок к 1: ln(/?(m))= \n(pl)+<p1 ln(m).

Представленная математическая модель корректно описывает все известные функциональные зависимости производительности параллельного вычислительного процесса от числа вычислительных узлов и позволяет определять основные характеристики вычислительных систем: время окончания вычислительных процессов, оптимальное число вычислительных узлов, оптимальную -загрузку процессоров.

В заключении изложены основные теоретические и практические результаты, полученные в диссертационной работе.

В приложении приведены реализация РБД, нормализованной на основе операций выборки и соединения, с использованием MS SQL Server 2000; БНФ-грамматика инструкции ВЫБРАТЬ; листинги основных методов и экранные формы СУБД, основанной на РБД, нормализованных на основе операций выборки и соединения; акты внедрения результатов работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

Получены следующие научные и практические результаты:

1. Структурная часть РБД, нормализованных на основе операций выборки и соединения.

2. Целостная часть РБД нормализованных на основе операций выборки и соединения.

3. Синтаксис, БНФ-грамматика, правила использования инструкций языка манипулирования данными РБД, нормализованных на основе операций выборки и соединения.

4. Алгоритмы поиска информации в РБД нормализованных на основе выборки и соединения.

5. Алгоритм перевода ER-диаграмм в структуру РБД нормализованных на основе выборки и соединения.

6. Алгоритмы перевода РБД в структуру РБД, нормализованных на основе выборки и соединения.

7. Методы проектирования распределенных РБД, нормализованных на основе операций выборки и соединения.

8. Методы администрирования доступа к информации РБД на основе реляционной операции выборки.

9. Комплекс программ проектирования и обеспечения функционирования РБД, нормализованных на основе операций выборки и соединения.

10. Математическая модель задачи оптимизации вычислительного процесса в многопользовательских системах обработки информации и управления, построенных на основе РБД, нормализованных на основе операций выборки и соединения.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Маликов A.B. Организация параллельных вычислительных систем на базе ЛВС для обработки баз данных большого объема. //Депонировано ВИНИТИ №754-В2001,2001,31 с.

2. Маликов A.B. Проектирование реляционных баз данных на основе операций выборки и соединения. Исследование их свойств. /Под редакцией проф. Чефранова А.Г., Ставрополь: СевКавГГУ, 2002, 244 с.

3. Маликов A.B., ЧефрановА.Г. Аналитическая зависимость производительности параллельных вычислительных систем от числа процессоров. //Известия вузов. Северо-Кавказский регион. Технические науки, 2003, № 2, с.25-28.

4. Маликов A.B. К вопросу нормализации реляционных баз данных. //Кибернетика и технологии XXI века /Материалы IV Международной научно-технической конференции, Воронеж: ВГУ, 2003, с.79-86.

5. Маликов A.B. Разработка надстроек инструкций манипулирования данными БД, нормализованных на основе операций выборки и соединения. //Кибернетика и технологии XXI века /Материалы IV Международной научно-технической конференции, Воронеж: ВГУ, 2003, с.87-96.

6. Маликов A.B. Методика проектирования реляционных баз данных на основе операций, отличных от проекции и соединения. //Известия вузов. СевероКавказский регион. Технические науки». Специальный выпуск «Математическое моделирование и компьютерные технологии», 2003, с.7-11.

7. Маликов A.B. Разработка синтаксиса и алгоритма функционирования инструкций манипулирования данными реляционных баз данных. //Известия вузов. Северо-Кавказский регион. Технические науки. Специальный выпуск «Математическое моделирование и компьютерные технологии», 2003, с. 12-17.

8. Маликов A.B., Евдокимов A.A., Кириченко В.И. Реализация АСУ учебным процессом на базе СевКавГТУ. //Новые информационные технолетии. Разработка и аспекты применения / Материалы IV всероссийской конференции с международным участием, Таганрог: ТРТУ, 2003, с. 18-22.

9. Маликов A.B., Лидовской К.В. Алгоритм поиска информации в реляционных базах данных, нормализованных на основе операций выборки и соединения. //Современные наукоемкие технологии, 2004, №2, с.41-44.

10. Маликов A.B., Лидовской К.В. Оптимизация на графах поиска информации в реляционных базах данных, нормализованных на основе операций выборки и соединения. //Теория, методы проектирования, программно-техническая платформа корпоративных информационных систем /Материалы II международной научно-практической конференции, Новочеркасск, 2004, с.219-221.

11. Маликов A.B. Методы проектирования и поддержания ссылочной целостности реляционных баз данных, нормализованных на основе операций выборки и соединения. //Татищевские чтения: актуальные проблемы науки и практики /Материалы Международной научной конференции, Тольятти: Волжский университет им. В.Н.Татищева, 2004, с.247-253.

12. Маликов A.B., Евдокимов A.A., Кириченко В.И., Лидовской К.В. Интегрированная автоматизированная система управления учебным процессом вуза- ИАСУ «Деканат». //Новые образовательные технологии в вузе /Материалы II научно-методической конференции, Екатеринбург: УГТУ-УПИ, 2004, с.30-32.

13. Маликов A.B., Лидовской К.В. Анализ и модификация графа связей отношений реляционной базы данных. //Инфотелекоммуникационные

технологии в науке, производстве и образовании /Материалы первой международной научно-технической конференции, Ставрополь:СевКавГТУ, 2005, с.46-49.

14. Маликов A.B. Реализация инструкций запросов к реляционным базам данных. //Известия вузов. Приборостроение, 2005, №9, с.7-12.

15. Маликов A.B., Лидовской К.В. Расширение реляционной алгебры для декларативных языков запросов к нормализованным на основе операций выборки и соединения базам данных. //Известия вузов. Северо-Кавказский регион. Технические науки. Специальный выпуск «Математическое моделирование и компьютерные технологии», 2005, с.9-10.

16. Маликов A.B. Использование нормализованных на основе операций выборки и соединения реляционных баз данных в корпоративных автоматизированных системах управления. //Вестник СевКавГТУ, 2005, №4, с.64-69.

17. Маликов A.B., Лидовской К.В. К вопросу обеспечения функционирования реляционных баз данных, нормализованных на основе операций выборки и соединения //Безопасность информационных технологий, 2005, №3, с.62-67.

18. Маликов A.B., Синельников Б.М., Цвиринько И.А. и др. Свидетельство об официальной регистрации программы для ЭВМ «Интегрированная автоматизированная система управления (ИАСУ) «ВУЗ»» №2005612457 зарегистрировано 19.09.2005.

19. Маликов A.B., Синельников Б.М., Цвиринько И.А. и др. Свидетельство об официальной регистрации базы данных «База данных интегрированной автоматизированной системы управления (ИАСУ) «ВУЗ»» №2005620267 зарегистрировано 18.10.2005.

Личный вклад соискателя в работах, выполненных в соавторстве: [3] — предложена и обоснована аналитическая зависимость производительности параллельной системы от числа процессоров, [8, 12, 18, 19] - реализована подсистема ведения учебных планов и спроектирован соответствующий фрагмент РБД, [9, 10] - предложен поисковый алгоритм, [13] - предложен модифицирующий алгоритм, [15] - введены новые реляционные операторы, [17]- введены новые реляционные операторы и реализующие их инструкции выборки данных.

Формат 60x84 1/16 Усл. печ. л. 2 Уч.-изд. л. 1,3 Бумага офсетная. Печать офсетная Заказ 659 Тираж 100 экз. ГОУВПО «Северо-кавказский государственный технический университет» 355029 г. Ставрополь, пр. Кулакова, 2

Издательство Северо-кавказского государственного технического университета Отпечатано в типографии СевКавГТУ

У

m

121792

РНБ Русский фонд

2006-4 20558

ВВЕДЕНИЕ.

1. СОСТОЯНИЕ ВОПРОСА.

I. I. Объекты реляционной модели данных. /. /. Структурная часть.

1.1.2. Целостная часть. 1.3. Реляционная алгебра и реляционное исчисление.

1.2. Сущности и взаимоотношения данных.

1.3. Нормализация отношений на основе операций проекции и соединения.

1.4. Квазиструктурированные данные.

1.5. Языки манипулирования данными.

1.6. Архитектуры реляционных баз данных.

1.7. Выводы.

2. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННОЙ БАЗЫ ДАННЫХ НА ОСНОВЕ ОПЕРАЦИЙ ВЫБОРКИ И СОЕДИНЕНИЯ.

2.1. Практическое использование и анализ проблем нормализации реляционных отношений.

2.2. Определение отношения связей атомарных значений в реляционной БД.

2.3. Метод нормализации отношения связей атомарных значений.

2.4. Выводы.

3. ОСНОВНЫЕ СВОЙСТВА БАЗ ДАННЫХ, НОРМАЛИЗОВАННЫХ НА ОСНОВЕ ОПЕРАЦИЙ ВЫБОРКИ И СОЕДИНЕНИЯ.

3.1. Методика восстановления отношений.

3.2. Использование NULL-значений в отношениях баз данных, нормализованных на основе операций выборки и соединения.

3.3. Реализация правил ссылочной целостности в базах данных, нормализованных на основе операций выборки и соединения.

3.4. Определение доменов атрибутов отношений баз данных, нормализованных на основе операций выборки и соединения.

3.5. Выводы.

4. ПРОЕКТИРОВАНИЕ УТОЧНЕННОЙ СТРУКТУРЫ БАЗ ДАННЫХ, НОРМАЛИЗОВАННЫХ НА ОСНОВЕ ОПЕРАЦИЙ ВЫБОРКИ И СОЕДИНЕНИЯ.

4.1. Алгоритм перевода ER-диаграммы в базу данных, нормализованную на основе операций выборки и соединения.

4.2. метод построения уточненной структуры баз данных, нормализованных на основе операций выборки и соединения.

4.3. практическое использование баз данных с уточненной структурой, нормализованных на основе операций выборки и соединения.

4.4. выводы.

5. ОСНОВНЫЕ СВОЙСТВА БАЗ ДАННЫХ С УТОЧНЕННОЙ СТРУКТУРОЙ, НОРМАЛИЗОВАННЫХ НА ОСНОВЕ ОПЕРАЦИЙ ВЫБОРКИ И СОЕДИНЕНИЯ.

5.1. Требования к нормализации отношений внутренней предметной области.

5.2. Реализация основных типов связей между атомарными значениями отношений в структуре баз данных, нормализованных на основе операций выборки и соединения.

5.3. Алгоритмы перевода реляционных баз данных в базу данных с уточненной структурой, нормализованную на основе операций выборки и соединения.

5.4. Основные недостатки баз данных с уточненной структурой, нормализованных на основе операций выборки и соединения.

5.5. Выводы.

6. РАЗРАБОТКА НАДСТРОЕК ДЕКЛАРАТИВНЫХ ЯЗЫКОВ МАНИПУЛИРОВАНИЯ ДАННЫМИ БАЗ ДАННЫХ, НОРМАЛИЗОВАННЫХ НА ОСНОВЕ ОПЕРАЦИЙ ВЫБОРКИ И СОЕДИНЕНИЯ.

6.1. Реализация функций добавления, удаления и модификации данных.

6.2. Сравнение результатов использования hhci рущии SELECT в базах данных с различным типом нормализации.

6.3. Разработка надстроек uncil'vkilmïï запросов к вазам данных, нормализованных на основе операций выборки и соедиш пия.

6.4. Разработка алгоритмов поиска информации в запросах к базам данных,

НОРМАЛИЗОВАННЫХ НА ОСНОВЕ ОПЕРД11ИЙ ВЫБОРКИ И СОЕДИНЕНИЯ.

6.5. Практическое использование инструкций выборки данных.

6.6. Выводы.

7. ПРОЕКТИРОВАНИЕ РАСПРЕДЕЛЕННЫХ РЕЛЯЦИОННЫХ БАЗ ДАННЫХ, НОРМАЛИЗОВАННЫХ НА ОСНОВЕ ОПЕРАЦИЙ ВЫБОРКИ И СОЕДИНЕНИЯ.

7.1. Методы проектирования распределенных реляционных баз данных, нормализованных на основе операций выборки и соединения.

7.2. Разграничение полномочий пользователей баз данных, нормализованных на основе операций проекции и соединения, с использованием операции выборки.

7.3. Разграничение полномочий пользователей баз данных, нормализованных на основе опера11ий выборки и соединения.

7.4. методы определения оптимальной конфигурации многопользовательской автоматизированной системы.

7.5. ВЫВОДЫ.

Деятельность человека во многом связана со сбором, накоплением и обработкой информации [72, 155]. Бурное развитие и применение компьютерной техники приводит к неуклонному росту объемов накапливаемой информации и повышению требований к ее структуре и качеству. При этом качество информации может оцениваться по целому ряду критериев. Одним из самых удачных инструментариев обработки информации стала реляционная теория, представляющая собой комплекс математических методов проектирования и обеспечения функционирования реляционных баз данных (РБД).

На настоящий момент существует несколько основных подходов к применению на практике той или иной модели представления данных при построении корпоративных автоматизированных систем управления (АСУ). Если не брать во внимание старые «дореляционные» модели данных: иерархическую и сетевую, то бесспорными лидерами на сегодняшний момент являются две модели: реляционная и сравнительно молодая — объектно-ориентированная [51, 70, 76, 86].

Ежегодно увеличивается число инсталляций программного обеспечения, поддерживающего различные структуры данных, различные способы их хранения и обработки, различные языки манипулирования данными [41,44,52,54,89], но бесспорными фаворитами на сегодняшний день ¿стаются~~реляционно-совместимые системы [102, 105, 160]. Их огромная популярность, в первую очередь, вызвана тем, что появление реляционной модели придало теории баз данных (БД) математическое обоснование и законченность.

Современное бурное развитие технологии реляционных баз данных подтверждается выходом в свет нового программного обеспечения. Корпорация Microsoft выпустила очередную версию популярного сервера баз данных Microsoft SQL Server 2000 [103, 178], являющего прямым приемником и продолжателем традиций, заложенных в Microsoft SQL Server 7.0. Microsoft SQL Server 2000 — это продукт, представляющий собой современное поколение комплексных программных средств управления базами и хранилищами данных для задач, требующих быстрого получения и анализа информации [154]. Он предназначен для широкого круга приложений во всех областях бизнеса [187]. Постоянное совершенствование программного обеспечения, работающего с реляционными БД, приводит к появлению у него новых качеств. К числу основных достоинств сервера Microsoft SQL Server 2000 следует отнести:

1. Осуществление запросов, анализ и управление данными через Интернет. Простой и безопасный доступ к данным посредством web-браузера с использованием межсетевых экранов.

2. SQL Server 2000 обеспечивает практически неограниченный рост объемов данных за счет увеличения надежности и расширяемости системы с использованием всех преимуществ мультипроцессорной обработки данных.

3. SQL Server 2000 уменьшает время создания, внедрения и выхода на рынок современных приложений для задач бизнеса и электронной коммерции, ускоряет процесс поиска данных, упрощает управление данными.

4. SQL Server 2000 в полном объеме использует аппаратные ресурсы многопроцессорных и кластерных систем, поддерживает преимущества многозадачности и параллельной обработки данных.

5. Аналитические возможности SQL Server 2000 позволяют исследовать собираемые реляционные данные и данные OLAP, включая входные потоки и историю обращений, чтобы выделить тренды и сформировать прогнозы. В SQL Server 2000 встроены новые типы данных, отладчик T-SQL и т.д.

Корпорация Oracle выпустила сервер баз данных Oracle 8 [60, 182]. По заявлениям фирмы производителя явный прогресс ощутился в области хранилищ данных. Стало возможным управление терабайтами данных. Было показано, что Oracle 8 хорошо масштабируется, прекрасно работает с многопроцессорным аппаратным обеспечением и может решать практически любую задачу. Для этого система была протестирована на реальных запросах, реальных нагрузках и задачах, характерных для современных хранилищ данных.

В настоящее время объектно-ориентированные базы данных применяются для некритичных по защите и объему хранимых данных приложениях, тем самым ограничивая их широкое использование в разработке корпоративных АСУ. К современным объектно-ориентированным СУБД относятся: Objectivity 5.0 компании Objectivity/DB, ONTOS DB компании ONTOS Inc, РОЕТ 5.0 компании РОЕТ Software GmbH, Jasmine 1.1 компании Computer Associates Inc и другие. Традиционными областями применения объектных СУБД являются системы автоматизированного проектирования, моделирование, мультимедиа, поскольку из нужд этих отраслей выросло новое направление в базах данных. Собственно, в перечисленных областях всегда была потребность найти адекватное средство хранения больших объемов разнородных данных, переплетенных многими связями.

Примером успешного внедрения объектной СУБД является система Predator («Хищник») [41], на основе базы ObjectStore, функционирующей в крупной финансовой компании «МакГрегор Груп». Она в режиме реального времени снабжает оператора информацией о состоянии рынка инвестиций одновременно для большого числа клиентов системы (около 3000).

Объектные базы находят широкое применение в телекоммуникациях и сети Интернет. Ведь Интернет — это собрание разнородных данных, поступающих из разных источников, с разнородными форматами: текст, картинки, видео, звук [52]. К удачным примерам внедрения объектных СУБД можно отнести применение базы ObjectStore компании DeutscheTelekom для организации информационного хранилища в своей интрасети, использование СУБД Gemstone в форумах Americanonline, использование СУБД РОЕТ в форумах CompuServe.

Для построения крупных корпоративных АСУ, в которых обрабатываются хорошо структурированные данные, оптимальным решением является использование реляционных СУБД [179].

В современной теории реляционных СУБД, являющейся наиболее распространенным аппаратом построения информационных систем, существует достаточное количество нерешенных или решенных не полностью проблем. Об этом свидетельствует поток статей, посвященных тематике чисто реляционных систем, а также активная деятельность компаний производителей коммерческих реляционных систем, стремящихся улучшать свои продукты и предавать им новые качества.

Аналитический обзор литературных источников показывает, что теоретическая часть реляционной модели данных имеет серьезное математическое обоснование [2, 9, 10, 16, 19, 20, 86, 112, 118, 119], фундаментом которой является теория множеств [56,73]. Всякая предметная область может быть описана конечным набором реляционных отношений. Необходимым условием эффективного использования реляционных баз данных является отсутствие аномалий обработки информации, которое достигается посредством методики нормализации отношений. Стандартная процедура нормализации основана на реляционных операциях проекции и соединения. Структура БД определяется на этапе проектирования, при этом выполняются этапы:

I. Определяется набор и назначение постоянных таблиц.

2. Определяется структура таблиц — перечень, название, назначение и гипы данных столбцов.

3. Определяется система ключей, и прописываются правила ссылочной целостности БД.

Дополнительно могут выполняться этапы по определению индексных структур, пользователей и их полномочий и т.п. Проектирование и поддержание функционирования БД — основная задача администратора БД. После разработки и внедрения клиентского приложения, информация БД доступна для модификации на уровне конечного пользователя, при этом ему, как правило, доступны только функции по изменению и анализу содержимого постоянных таблиц БД. При изменении структуры предметной области конечный пользователь (клиентское приложение), как правило, не в состоянии изменить набор и структуру таблиц — для этого администратор должен выполнить этапы, описанные ранее.

Структура данных также является данными и к ней могут быть применены операции манипулирования данными: добавление, удаление, изменение. Необходимость выполнения указанных операций обусловлена тем, что структура предметной области может динамически меняться. Стандартные методы нормализации, основанные на реляционных операциях проекции и соединения, не позволяет эффективно описывать произвольные предметные области с полностью не определенными структурами. Вообще выделяют 3 класса систем с полностью не определенными структурами [ 172]:

1. Данные, структура которых даже априорно неизвестна. В этом случае формирование структуры каталога данных и его заполнение происходит одновременно по мере поступления информации.

2. Структура данных известна частично. Известны основные описания базовых сущностей или классов системы; вместе с тем имеется необходимость хранения и обработки заранее неопределенной дополнительной информации.

3. Структура данных известна и четко определена, но может меняться с течением времени.

Такие данные в литературе принято называть квазиструктурированными или полуструктурированными. В зависимости от постановки задачи проектирования базы данных, основанной на квазиструктурированных данных, возможны реализации с различной реляционной структурой. Наибольшее распространение получили простые структуры, отношениями которых описывают отношения, атрибуты, атомарные значения и связи последних как ссылки на атомарные значения непосредственной достижимости. Полученная структура представлена в [172] и является описанием графа связей атомарных значений предметной области [93], где вершинами являются непосредственно атомарные значения, а ребрами - их связи. Анализ литературных источников показывает, что не существует единого подхода к проектированию описываемых баз данных, а структура, представленная в [172], не может использоваться в случаях описания реляционных систем, в которых существует несколько различимых ссылочных путей между отношениями [133]. Вообще существование определенных структур, описывающих квазиструктурированные данные, продиктовано необходимостью хранения единственной копии всякого атомарного значения предметной области, имеет строгое математическое обоснование и может быть представлено как методика нормализации реляционных отношений предметной области на основе операций, отличных от проекции и соединения [133].

Кроме того, использование единых структур, хранящих квазиструктурированные данные, требует использования специфичных языком манипулирования данными, так как применение стандартных декларативных языков ограничено в силу сложности формулирования запросов [133, 172]. В настоящее время не существует стандарта таких языков, исследования в данной области ведутся [7, 77, ПО, 172, 184].

Для доступа к информации реляционных баз данных применяются специальные языки манипулирования данными, среди которых предпочтение отдается декларативным языкам. В настоящее время наибольшее распространение получил язык SQL [86, 154, 187], достоинствами которого являются наглядность, приближенность к конечному пользователю. Для повышения надежности реляционных систем и оперативности доступа к информации могут быть реализованы различные подходы к архитектуре баз данных [85, 86, 108, 111, 118, 185], такие как файл-серверная, клиент-серверная архитектуры, реализация параллельных и распределенных баз данных.

Несмотря на развитый математический аппарат, значительную программную и информационную поддержку, множество прикладных реализаций, реляционной модели присущи следующие основные недостатки:

1. Для разных уровней пользователей системы информация базы данных представляется различными уровнями абстракции, как правило, конечный пользователь (клиентское приложение) не в состоянии изменить набор и структуру таблиц, вследствие изменения структуры предметной области. Реляционная система становится зависимой от прикладного программиста и администратора, что сказывается на коммерческих свойствах системы.

2. Декларативные языки манипулирования данными, несмотря на универсализм, являются языками уровня прикладного программиста и/или администратора системы, но не конечного пользователя. Пользователь не знающий структуры базы данных не может сформулировать свой запрос, а если запрос написан на языке SQL, то изменение структуры базы данных влечет за собой его переформулирование.

3. Не существует единого подхода к проектированию больших, сложных реляционных систем, подразумевающих наличие распределенных данных.

4. Наличие ЬГиЬЬ-значений в таблицах и, вообще, трехзначная логика усложняет бизнес-логику клиентских приложений.

Развитие математического аппарата реляционной теории с целью решения указанных проблем представляется актуальной задачей. В диссертационной работе проведено развитие и обобщение реляционной теории с целью преодоления недостатков проектирования и обеспечения функционирования классических РБД, для этого вводятся новые методы моделирования квазиструктурированной информации, новые правила поддержания ссылочной целостности, новые методы манипулирования информацией.

Объектом исследования являются математические методы реляционной теории управления большими объемами квазиструктурированной информации.

Целью настоящей диссертационной работы является развитие и обоснование математических методов реляционной теории для эффективного управления большими объемами информации предметных областей с полностью неопределенными структурами.

Для достижения поставленной цели были решены следующие задачи:

1. Проанализированы существующие методы реляционной теории управления информацией, в том числе моделирование квазиструктурированных данных.

2. Разработан формальный математический аппарат нормализации реляционных отношений на основе операций выборки и соединения, в результате чего была получена структура РБД, содержащей квазиструктурированные данные.

3. Введено понятие роли реляционного отношения как идентификатора отдельного ссылочного пути на любой паре отношений, на основе чего спроектирована уточненная структура РБД, нормализованной на основе операций выборки и соединения.

4. Определена методика проектирования РБД, нормализованных на основе операций выборки и соединения. Определен алгоритм перевода ЕЯ-диаграмм в полученную структуру.

5. Определены правила поддержания ссылочной целостности и использования КХЛХ-значений в РБД, нормализованных на основе операций выборки и соединения.

6. Определены особенности языка манипулирования данными полученной структуры. Определен синтаксис, ВИР-грамматика, правила использования инструкций языка.

7. Для инструкции выборки данных определены алгоритмы поиска информации в РБД, нормализованных на основе выборки и соединения.

8. Определены методы проектирования распределенных РБД, нормализованных на основе операций выборки и соединения.

9. Определены методы администрирования доступа к информации РБД на основе реляционной операции выборки.

10. Построена математическая модель задачи оптимизации вычислительного процесса в многопользовательских системах обработки информации и управления, построенных на основе РБД, нормализованных на основе операций выборки и соединения.

11. Показаны результаты использования полученных результатов в автоматизированных системах управления (АСУ) учебным процессом.

При решении поставленных в диссертационной работе задач использовались: методы теории реляционной модели данных, методы теории множеств, методы теории графов, методы математического моделирования, методы теории вероятностей и математической статистики, методы построения вычислительных систем и программирования.

Научная новизна работы сос тоит в следующем:

1. Разработаны методы моделирования квазиструктурированной информации понятия и структурная часть баз данных, нормализованных на основе операций выборки и соединения.

2. Определена целостная часть баз данных, нормализованных на основе операций выборки и соединения.

3. Определен синтаксис, BNF-грамматика, правила использования инструкций языка манипулирования данными баз данных, нормализованных на основе операций выборки и соединения.

4. Для инструкции выборки данных определены алгоритмы поиска информации в базах данных, нормализованных на основе выборки и соединения.

5. Определен алгоритм перевода ER-диаграмм в структуру баз данных, нормализованных на основе выборки и соединения. Определены алгоритмы перевода реляционных баз данных в структуру баз данных, нормализованных на основе выборки и соединения.

6. Определены методы проектирования распределенных реляционных баз данных, нормализованных на основе операций выборки и соединения.

7. Определены методы администрирования доступа к информации баз данных на основе реляционной операции выборки.

8. Построена математическая модель задачи оптимизации вычислительного процесса в многопользовательских системах обработки информации и управления, построенных на основе реляционных баз данных, нормализованных на основе операций выборки и соединения, позволяющая определять оптимальные характеристики функционирования вычислительной системы: число вычислительных узлов, загрузку вычислительных узлов, время окончания вычислительного процесса;

Практическая ценность результатов диссертационной работы заключается в создании программного комплекса (на платформе MS SQL

Server 2000 + Visual CU.NET), поддерживающего работу с нормализованными на основе операций выборки и соединения РБД, модификация и анализ содержимого которых доступны на уровне конечного пользователя. Тем самым существенно повышаются скорость разработки, внедрения, модификации, сопровождения приложений РБД.

На защиту выносятся:

1. Методы моделирования квазиструктурированной информации и структурная часть РБД, нормализованных на основе операций выборки и соединения.

2. Целостная часть РБД, нормализованных на основе операций выборки и соединения.

3. Синтаксис, BNF-грамматика, правила использования инструкций языка манипулирования данными РБД, нормализованных на основе операций выборки и соединения.

4. Алгоритмы поиска информации в РБД, нормализованных на основе операций выборки и соединения.

5. Алгоритм перевода ER-диаграмм в структуру РБД, нормализованных на основе выборки и соединения.

6. Алгоритмы перевода РБД в структуру баз данных, нормализованных на основе операций выборки и соединения.

7. Методы проектирования распределенных РБД, нормализованных на основе операций выборки и соединения.

8. Методы администрирования доступа к информации РБД на основе реляционной операции выборки.

9. Комплекс программ проектирования и обеспечения функционирования РБД, нормализованных на основе операций выборки и соединения.

10. Математическая модель задачи оптимизации вычислительного процесса в многопользовательских системах обработки информации и управления, построенных на основе РБД, нормализованных на основе операций выборки и соединения.

Достоверность полученных результатов работы подтверждается корректным использованием теоретических и практических методов обоснования полученных результатов. Основные выводы и положения диссертационной работы обоснованы использованием при их получении известных, проверенных практикой моделирования на ЭВМ теоретических методов исследования, базирующихся на принципах теории реляционной модели данных, теории множеств, теории графов, теории вероятностей и математической статистики, программирования, а также применением разработанных методов при решении конкретных задач предприятия, что подтверждается актами внедрения результатов работы. Экспериментальные исследования и тестирование разработанных комплексов алгоритмов показали непротиворечивость полученных результатов и подтвердили теоретические оценки качества комплексов алгоритмов.

Полученные в диссертационной работе результаты реализованы и внедрены:

1) в Северо-Кавказском государственном техническом университе г. Ставрополя;

2) в филиалах Северо-Кавказского государственного технического университа в городах Невинномысске, Георгиевске, Пятигорске, Кисловодске;

3) в Северо-Кавказском гуманитарно-техническом институте г. Ставрополя;

4) в Народном Шпаковском Транспортном Предприятии г. Михайловска.

Основные этапы работы докладывались и обсуждались на ежегодных научно-технических конференциях профессорско-преподавательского состава Северо-Кавказского государственного технического университета (Ставрополь, 1999 г., 2000 г., 2001 г., 2002 г.,

2003 г.), ежегодной научной конференции Таганрогского государственного радиотехнического университета (Таганрог, 2000 г.), Всероссийской научно-технической конференции «Проблемы создания автоматизированных обучающих и тестирующих систем» (Новочеркасск, 2000 г.), научном семинаре академика РАН А.В. Каляева в НИИ многопроцессорных систем (Таганрог, 2001 г.), научном семинаре Южно-Российского регионального центра информатизации высшей школы РГУ (Ростов-на-Дону, 2001 г.), VI всероссийской научной конференции с международным участием «Новые информационные технологии. Разработка и аспекты применения» (Таганрог, 2003 г.), IV Международной научно-технической конференции «Кибернетика и технологии XXI века» (Воронеж, 2003 г.) — работы награждены дипломом за лучший доклад конференции, X международной конференции «Современные технологии обучения» (Санкт-Петербург,

2004 г.), Международной научной конференции «Татищевские чтения: актуальные проблемы науки и практики» (Тольятти, 2004 г.), второй Международной научно-практической конференции «Теория, методы проектирования, программно-техническая платформа корпоративных информационных систем» (Новочеркасск, 2004 г.), ежегодной международной конференции «Технологии 2004» (Турция, Анталия, 2004 г.), II научно-методической конференции «Новые образовательные технологии в вузе» (Екатеринбург, 2004), Первой международной научно-технической конференции «Инфотелекоммуникационные технологии в науке, производстве и образовании» (Ставрополь, 2004).

По теме диссертации автором опубликовано 47 печатных работ.

Материал основной часта диссертационной работы изложен на 210 страницах машинописного текста. Диссертация состоит из введения, семи разделов, заключения, списка литературы из 199 наименования, 27 рисунков, 34 таблиц и 5 приложений.

7.5. Выводы

1. При проектировании распределенной реляционной БД, нормализованной на основе операций выборки и соединения, все известные способы построения распределенной БД вырождаются во фрагментацию отношений на основе реляционной операции выборки (горизонтальная фрагментация). Структура отдельных локальных БД в узлах сети одинакова и состоит из 7-ми стандартных отношений.

2. Задача разграничения доступа пользователей к информации БД решается на одном из трех уровней: таблиц, столбцов, строк. Для разграничения полномочий на уровне строк таблиц (горизонтальное разграничение) используется реляционная операция выборки, для чего отношения подвергаются процедуре нормализации с учетом информации о пользователях БД. При этом если используется БД, нормализованная на основе операций выборки и соединения, то ее отношения дополняются соответствующими кортежами. Инструкции манипулирования данными дополняются предложениями, обрабатывающими отношения (кортежи) с информацией о пользователях.

3. Рассмотрена возможность использования математической модели оптимизации параллельного вычислительного процесса [127, 152] применительно к многопользовательской автоматизированной системе, построенной с использованием БД, нормализованной на основе операций выборки и соединения. С помощью представленной математической модели могут быть определены основные характеристики вычислительных систем: время окончания вычислительных процессов, оптимальное число процессоров, оптимальная загрузка процессоров.

Заключение

Подавляющее большинство современных автоматизированных систем построено на основе реляционной модели данных. Такое широкое распространение модель получила благодаря наличию определенных преимуществ, частично или полностью отсутствующих в других моделях:

• простота и наглядность;

• развитый математический аппарат;

• возможность описания любых предметных областей реального мира.

Данные обстоятельства обуславливают применение реляционных баз данных в различных областях человеческой деятельности. Главной идеей представленной работы явилось исследование предметной области «реляционная модель данных» на основе анализа свойств реляционных систем и систем, содержащих квазиструктурированные данные. В предметной области были определены основные сущности, их свойства, типы взаимосвязей, на основе чего спроектирована структура соответствующей реляционной базы данных. При этом использовался теоретический аппарат нормализации отношений на основе реляционных операций проекции и соединения.

Основным научным результатом диссертационной работы является проектирование и исследование свойств уточненной структуры реляционных баз данных, нормализованных на основе операций выборки и соединения (рисунок 10). Основными достоинствами предложенной структуры являются:

1. Постоянство структуры БД внешней предметной области. Использование только семи отношений позволяет описать любую предметную область реального мира.

2. Отсутствие Ы1ЛХ-значение в описании информации. Для несуществующей информации отпадает необходимость определения дополнительных искусственных средств для ее описания в БД.

Автоматически отпадает необходимость в использовании операторов и функций, работающих с NULL-значениями, что упрощает бизнес-логику приложений.

3. Основные типы связей между атрибутами в предложенной модели данных поддерживаются напрямую. Отсутствует необходимость в искусственных средствах поддержания связей: «один-к-одному», «один-ко-многим», «многие-ко-многим», иерархических связей. К таким искусственным средствам относятся: поддержание системы ключей и создание дополнительных отношений внутренней предметной области.

4. Использование более простого декларативного языка манипулирования данными по сравнению со стандартным SQL. При этом предполагается, что по отношению к информации внутренней предметной области достаточно следующих инструкций модификации данных (INSERT, DELETE, UPDATE}. Для построения запросов к БД может использоваться инструкция ВЫБРАТЬ — более высокоуровневая по отношению к инструкции SELECT языка SQL. По отношению к БД внешней предметной области применимы все инструкции SQL, так как при ее нормализации использовался классический проекционно-соединительный подход. По отношению к БД внутренней предметной области также могут применяться стандартные инструкции языка SQL.

5. Построение распределенных клиент-серверных систем на основе методов горизонтального фрагментирования таблиц данных и/или репликации. Все многообразие методов построения распределенных БД, используемых при проекционно-соединительном подходе, теряют свою актуальность для предложенной модели, т.к. они вырождаются во фрагментации таблиц данных на основе реляционной операции выборки.

Основные теоретические и практические результаты диссертационной работы заключаются в следующем:

1. Определены понятия и структурная часть баз данных, нормализованных на основе операций выборки и соединения.

2. Определена целостная часть баз данных, нормализованных на основе операций выборки и соединения.

3. Определен синтаксис, BNF-грамматика, правила использования инструкций языка манипулирования данными баз данных, нормализованных на основе операций выборки и соединения.

4. Для инструкции выборки данных определены алгоритмы поиска информации в базах данных, нормализованных на основе выборки и соединения.

5. Определен алгоритм перевода ER-диаграмм в структуру баз данных, нормализованных на основе выборки и соединения. Определены алгоритмы перевода реляционных баз данных в структуру баз данных, нормализованных на основе выборки и соединения.

6. Определены принципы проектирования распределенных реляционных баз данных, нормализованных на основе операций выборки и соединения.

7. Определены методы администрирования доступа к информации баз данных на основе реляционной операции выборки.

8. Рассмотрена возможность использования математической модели оптимизации параллельного вычислительного процесса применительно к многопользовательской автоматизированной системе, построенной с использованием БД, нормализованной на основе операций выборки и соединения. С помощью представленной математической модели могут быть определены основные характеристики вычислительных систем: время окончания вычислительных процессов, оптимальное число процессоров, оптимальная загрузка процессоров.

На основе результатов, полученных в диссертационном исследовании, в Северо-Кавказском государственном техническом университете г. Ставрополя программистами Учебно-Методического Управления Евдокимовым A.A., Кириченко В.И., Лидовским К.В., Маликовым A.B. разработана опытная версия СУБД "BiZone" с использованием языка С# и

СУБД Microsoft SQL Server 2000. Практическая реализация основных положений диссертационного исследования с использованием СУБД "BiZone" представлена в приложении 4.

Результаты диссертационного исследования внедрены в СевероКавказском государственном техническом университете и его филиалах в городах Ставрополе, Невинномысске, Георгиевске, Пятигорске, Кисловодске, Северо-Кавказском гуманитарно-техническом институте города Ставрополя, Народном Шпаковском Транспортном Предприятии города Михайлове ка. В приложении 5 представлены акты о внедрении результатов диссертационного исследования.

1. Abiteboul S., Quass D., McHugh J., WidomJ., WeinerJ. The Lorel query language for semistructured data. 1.ternational Journal on Digital Libraries, l(l):68-88, 1997. http://pub-db.stanford.edu/publi.st.html.

2. Aho A.V., Beeri C., Ullman J.D. The theory of joins in relational databases. ACM TODS. 1979. №3.

3. AllFusion Erwin Data Modeler, www.interface.ru (www.erwin.ru ).

4. Anzeni P., Mecca G., Merialdo P. Semistructured and Structured Data in the Web: Going Back and Forth. Workshop on Management of Semistructured Data, 1997. www.research.att.com/~suciu/ workshop-papers.html.

5. Buneman P., Davidson S., Fernandez M., Suciu D. Adding Structure to Unstructured Data. http://db.cis.upenn.edu/Publications/.

6. Buneman P., Davidson S., Hillebrand G., Suciu D. A query language and optimization techniques for unstructured data. In Proc. of ACM SIGMOD Conf. On Management of Data, pages 505-516, Montreal, Canada, 1996.

7. Celko J., Trees in SQL, DBMS Online, 1996.

8. Cluet S., Delobel C., Sim'eon J., Smaga K. Your Mediators Need Data Conversion! In Proceedings of ACM-SIGMOD International Conference on Management of Data, 177-188, 1998.

9. Codd E.F. A relational model of data for large shared data banks. CACM. 1970. — 13. №6.

10. Codd E.F. Extending the relation database model to capture more meaning. ACM TODS. 1970. №4.

11. Codd E.F. Relational Completeness of Data Base Sublanguages, Data Base Systems. Courant Computer Science Symposia Series 6. — Englewood Cliffs. N.Y.: Prentice-Hall. 1972.

12. Consens M., Mendelzon A. GraphLog: a visual formalism for real life recursion. In Proc. Of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), page 404-416, Atlantic City, NJ, 1990.

13. Cruz I. F., Mendelzon Л. О., Wood Р. Т. Л graphical query language supporting recursion. In Proc. Of ACM SIGMOD Conf. On Management of Data, pages 323-330, San Francisco, СЛ, 1987.

14. Cruz I. F., Mendelzon A. O., Wood P. T. G+: Recursive queries without recursion. In Proc. Of the Second International Conference on Expert Database Systems, pages 355-368, 1988.

15. Darwen H. Adventures in relationland // C.J. Date. Relational database writings 1985-1989. — Reading. Mass.: Addison-Wesley. 1992.

16. Date C.J. What Is a Distributed Database System? // C.J. Date. Relational Database Writings 1985-1989. — Reading. Mass.: Addison-Wesley. 1990.17. dBase, www.dBase.com.18. Express 4GL фирмы Oracle.

17. Fagin R. Multivalued dependencies and new normal form for relational databases. ACM TODS. 1977. №3.

18. Fagin R. Normal forms and relational database operators. Proc. 1979 ACM SIGMOD Intern. Conf. on management of data. Boston, Mass. 1979.

19. Fernandez M., Florescu D., Levy A., Suciu D. A query language for a web-site management system. SIGMOD Record, 26(3):4-l 1, September 1997. www.acm.org/sigs/sigmod/record.

20. Garcia-Molina H., Papakonstantinou Y., Quass D., Rajaraman A., SagivY., UllmanJ., Vassalos V., WidomJ. The TSIMMIS Approach to Mediation: Data Models and Languages, www.db.stanford.edu/tsimmis.

21. Goldman R., WidomJ. DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases. Proceedings of the Twenty-Third International Conference on Very Large Data Bases, Athens, Greece, 1997.

22. Hall P.A.V., HichcockP., Todd S.J.P. An algebra of relations for machine computation, conference record of the 2nd ACM symposium on principles of programming languages. Palo Alto. Calif. 1975.

23. Hammer J., Garcia-Molina FI., Nestorov S., Ramana Yemeni. Template-Based Wrappers in the TSIMMIS System, www.db.stanlbrd.edu/tsimmis.

24. Held G.D. Stonebraker M.R., Wong E. INGRES — Л Relational Data Base System, Proc. NCC 44. — Anaheim, Calif.; Montvale, N.J.: AFIPS Press. 1975.

25. Henzinger M., HenzingerT., Корке P. Computing simulations on finite and infinite graphs. In Proceedings of 20th Symposium of Foundations of Computer Science, pages 453-462, 1995.

26. Kalyaev A.V., Kalyaev I.A. STORC-computer — a multiprocessor computer system with structure-organized calculations. Engineering Simulation. 1997. №10.

27. Li C., Yemeni R., Vassalos V., Garcia-Molina H., Papakonstantinou Y., UllmanJ., Valiveli M. Capability Based Mediation in TSIMMIS. www.db.stanford.edu/tsimmis.

28. McHughJ., Abiteboul S., Goldman R., Quass D., Widom J. Lore: A Database Management System for Semistructured Data. www.db.stanford.edu/lore.

29. Microsoft Visual Basic 6.0 Programmer's Guide. СПб.: БХВ, 2000.32. MSDN. www.microsoft.com.

30. Papakonstantinou Y., Garcia-Molina H., Widom J. Object Exchange Across Heterogeneous Information Sources. Proceedings of the Eleventh International Conference on Data Engineering, pp. 251-260, Taipei, Taiwan, 1995.

31. Papakonstantinou Y., Gupta A., Garcia-Molina H., Ullman J. A Query Translation Scheme for Rapid Implementation of Wrappers. www.db.stanford.edu/tsimmis.35. R:Base, vvvvw.rbase.com.

32. Robie J., Lapp J., Schach D. XML Query Language (XQL). In Proc. of the Query Languages workshop, Cambridge, Mass., 1998.

33. ZloofM.M. Query By Example. Proc. NCC 44. — Anaheim, Calif. Montvale, N.J.: AFIPS Press. 1975.

34. Акимов O.E. Дискретная математика. Логика, группы, графы. 2-е издание, дополненное. М.: ПБЗ, 2001.

35. Аксинрод Т., Беккерман М. и др. Программирование на параллельных вычислительных системах. Под редакцией Б. Бебба. М.: Мир, 1991.

36. Альянах И.Н. Моделирование вычислительных систем. Ленинград: Машиностроение, ленинградское отделение, 1988.

37. Андреев A.M., Березкин Д.В., Кантонистов Ю.А. Объектно-ориентированные базы данных: среда разработки программ плюс хранилище объектов, http://inteltec.ru/publish/articles/obitech/oodbmso.shtml.

38. Артаманов Г.Т., Тюрин В.Д. Топология сетей ЭВМ и многопроцессорных систем. 1991.

39. Архангельский A.B. Канторовская теория множеств. М.: Изд-во МГУ, 1988.

40. Архангельский А.Я. Работа с локальными базами данных в Delphi 5. М.: Бином, 2001.

41. Архангельский С.И. Учебный процесс в высшей школе, его закономерные основы и методы. М.: Высшая школа, 1980.

42. Архипенко С. Хранилища данных. От концепции до внедрения. М.: Диалог-МИФИ, 2002.

43. Асельдеров З.М., Донец Г.А. Представление и восстановление графов. АН УССР, Институт кибернетики им. В.И. Глушкова. Киев: Наукова Думка, 1991.

44. Атре Ш. Структурный подход к организации баз данных. Пер. с англ. A.A. Александрова, В.И. Будзко. Под редакцией В.И. Будзко. М.: Финансы и статистика, 1983.

45. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

46. Баас P. Delphi 5. К.: BHV, 2000.

47. Базы данных. Под ред. Хомоненко А.Д. 3-е издание, перер. и допол. СПб.: КОРОНА принт, 2003.

48. Байенс Джим. Разработка баз данных для Web. Шаг за шагом: практическое пособие. М.: ЭКОМ, 2001.

49. Барский А.Б. Параллельные процессы в вычислительных системах. М.: Радио и связь, 1990.

50. Барфилд Эд., Уолтере Б. Программирование «Клиент-сервер» в локальных вычислительных сетях. М.: Филинъ, 1997.

51. Белов В.В. Теория графов. М.: Высшая школа, 1976.

52. Белоусов А.И., Ткачев С.Б. Дискретная математика. М.: Издательство МГТУ им. Н.Э. Баумана. 2001.

53. Бердж К., Теория графов и ее применение. М.: ИЛ, 1962.

54. Березко Л.А., Вишенчук И.М., Троценко В.В. Принципы функционирования параллельных вычислительных машин и систем. Киев: УМКВО, 1989.

55. Биллингслей П. Эргодическая теория и информация. Перевод с английского И.Д. Светловой. Под редакцией Б.М. Гуревича. М.: Мир, 1969.

56. Бобровски Стив. Oracle 8: архитектура. М.: Лори, 1998.

57. Бройдо В.Л. Вычислительные системы, сети и телекоммуникации. СПб.: Питер, 2003.

58. Виленкин Н.Я. Комбинаторика. М.: Наука, 1969.

59. Вирт Н. Алгоритмы и структуры данных. Пер. с англ. М.: Мир, 1989.

60. Воеводин В.В. Информационная структура алгоритмов. М.: Издательство МГУ, 1997.

61. Воеводин В.В. Курс лекций: «Параллельная обработка данных». http://parallel.ru/vw/

62. Вудкок Дж. Современные информационные технологии совместной работы. Пер. с англ. М.: рус. ред., 1999.

63. Галкина В.А. Дискретная математика: комбинаторная оптимизация на графах. М.: Гелиос АРВ, 2003.

64. Гетц К., Гилберт М. Программирование на Visual Basic 6 и VBA: руководство разработчика. К.: Изд. группа BHV, 2001.

65. Гилл Ф. и др. Практическая оптимизация. Перевод с английского. Редактор А.А. Петров. М.: Мир, 1985.

66. Глушаков C.B., Ломотько Д.В. Базы данных. Харьков: Фолио, 2000.

67. Гмурман В.Е. Теория вероятностей и математическая статистика. М.: Высшая школа. 1977.

68. Голенищев Э.П. Информационное обеспечение систем управления. Ростов-на-Дону: Феникс, 2003.

69. Горбатов В.А. Фундаментальные основы дискретной математики. М.: Наука. Физматлит, 1999.

70. Грабер М. Справочное руководство по SQL. Технический редактор Джо Селко, ANSI ХЗН2 Комитет стандартов баз данных. М.: Лори, 1998.

71. Грегори К. Использование Visual C++.Net. Специальное издание. М., СПб., К.: Вильяме, 2002.

72. Грей Д. Управление данными: Прошлое, Настоящее и Будущее, журнал «Системы управления базами данных», №2, 1995, http://www.osp.ru/dbms/1998/03/71.htm.

73. Григорьев Е., Представления сложных идентифицируемых сложных объектов в реляционной базе данных, журнал «Открытые системы», №1-2, 2000, http://www.osp.ni/os/2000/01 -02/079.htm.

74. Гринев М., Системы управления полуструктурированными данными, журнал «Открытые системы», №5-6, 1999, http://wwvv.osp.ru/os/1999/05-06/09.htm.

75. Грофф Дж. SQL: полное руководство. Пер. с англ. 2-е издание, переработанное и дополненое. Киев: BHV, 2001.

76. Гусак А.А. Высшая математика. Мн.: ТетраСистемс, 1998.

77. Гутер P.C., Овчинский Б.В. Элементы численного анализа и математической обработки результатов опыта. М.: Наука, 1970.

78. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. Перевод с англ. М.: Мир, 1982.

79. ДевиттД., Грэй Д. Параллельные системы баз данных: будущее высоко эффективных систем баз данных. Журнал «СУБД» // «Открытые системы». 1995. №2.

80. ДейтК.Дж. Введение в системы баз данных. М., С-Пб., К.: Издательский дом «Вильяме». 2000.

81. Денисов А.А., Колесников Д.Н. Теория больших систем управления. Ленинград: Ленинградское отделение Энергоиздата, 1982.

82. Джобе К. Реляционные базы данных — одна из основ вычислительной науки. Computerworld. 1997. #17-18. http://www.osp.ru/cw/1997/17-18/024.htm.

83. Диго С.М. Проектирование и использование баз данных. М.: Финансы и статистика, 1995.

84. Долженков В. Visual Basic.Net: учебный курс. СПБ.: Питер, 2003.

85. ЕвреиновЭ.В. Распределенная обработка информации и распределенные вычислительные системы. М.: Знание, 1983.

86. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. М.: Наука, 1981.

87. Зыков А.А. Основы теории графов. М.: Наука, 1987.

88. Иванов Ю.Ы. Теория информационных объектов и системы управления базами данных. М.: Наука, 1988.

89. Исследования но прикладной теории графов. Сборник статей. АН СССР, Сибирское отделение. Отв. ред. A.C. Алексеев. Новосибирск, Сибирское отделение, 1986.

90. Ицик Бен-Ган. Иерархические структуры, не требующие сопровождения. 2001. http://ww\v.osp.nl/win2000/sql/967.htm.

91. Каипов В.Х. и др. Методы обработки данных в системах с нечеткой информацией. АНКиргССР. Фрунзе: Илим, 1988.

92. Калинин А.Г., Мацкевич И.В. Универсальные языки программирования: семантический подход. М.: Радио и связь, 1991.

93. Калиниченко Л.А., Рыбкин В.М. Машины баз данных и знаний. М.: Наука, 1990.

94. Кантор Г. Труды по теории множеств. Издание подготовили А.Н. Колмогоров и др. Отв. ред. А.Н. Колмогоров, А.П. Юшкевич. М.: Наука, 1990.

95. Каратыгин С.А., Тихонов А.Ф., Тихонова Л.Н. Visual Foxpro 6. M.: ЗАО «Издательство БИНОМ». 1999.

96. Карпова Т. Базы данных: модели, разработка, реализация. СПб.: Питер, 2001.

97. Каталог программного обеспечения «SoftLine direct» май 2002 — сентябрь 2002. № 2.

98. Когаловский М.Р. Технология баз данных на персональных ЭВМ. М.: Финансы и статистика, 1992.

99. Когаловский М.Р. Энциклопедия технологий баз данных: эволюция технологий. Технологии и стандарты. Инфраструктура. Терминология. М.: Финансы и статистика, 2002.

100. Когаловский М.Р., Абстракции и модели в системах баз данных, журнал «Системы управления базами данных», №4-5, 1998, lntp:/Avw\v.osp.ru/dbms/1998/04-05/07.htm.

101. Козлик Г.А. Оптимизация обработки информации в системах управления. Киев: Тэхника, 1989.

102. Колесников Д.Г. Оптимизация распределения информационных файлов в сетях ЭВМ с параллельной обработкой. Диссертация на соискание ученой степени к.т.н. Ростов-на-Дону. 1999.

103. Колобашкин С.М., Коваленко А.П., Смирнов С.Н. Методы дискретной оптимизации. М.: Изд. в/ч 33965, 1990.

104. Комитет по развитию функциональных возможностей СУБД, Системы баз данных третьего поколения: Манифест, журнал «Системы управления базами данных», №2, 1995, http://www.osp.ru/dbms/1995/02/23 .htm.

105. Корнеев B.B. Параллельные вычислительные системы. М.: Нолидж. 1999.

106. Корнеев В.В., Гареев А.Ф., Васютин C.B. Базы данных. Интеллектуальная обработка информации. М.: Нолидж. 2000.

107. ПЗ.КофманА. Введение в прикладную комбинаторику. М.: Наука, 1975.

108. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.

109. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. 2-е издание, переработанное и дополненное. М.: Энергоатомиздат, 1988.

110. Кузнецов С. SQL: язык реляционных баз данных. М.: Майор, 2001.

111. Кузнецов С. СУБД и файловые системы. М.: Майор, 2001.

112. Кузнецов С. Тенденции в мире систем управления базами данных. http://vvw\v.citforum.kcn.ru/datübüse/articles/art 25.shtml.

113. Кузнецов С.Д. Основы современных баз данных, информационно-аналитические материалы Центра информационных технологий. http://www.cittTmu.ru.

114. Линекер Р., ЛрчерТ. Программирование для Windows 98. Библия разработчика. Перевод с английского. М.: Диалектика, 1999.

115. Львовский E.H. Статистические методы построения эмпирических формул. М.: Высшая школа. 1982.

116. Люри Дж., Мансур LLL, Преодоление иерархий, журнал «SQL Magazine OnLine», №5, 2001.

117. Магрупов Т.М. Графы, сети, алгоритмы и их приложения. Под ред. Ф.Б. Абуталиева. АН УзССР, институт кибернетики с ВЦ УзНПО «Кибернетика». Ташкент: Фан, 1990.

118. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981.

119. Макаров И.П. Дополнительные главы математического анализа. М.: Просвещение. 1968.

120. Маликов A.B. Исследование и организация эффективных вычислений в параллельных системах баз данных на основе сетей ЭВМ. Диссертация на соискание ученой степени к.т.н. Ставрополь. 2001.

121. Маликов A.B. К вопросу нормализации реляционных баз данных / On the problem of relational database normalization. Сборник «Кибернетика и технологии XXI века» по материалам IV Международной научно-технической конференции. Воронеж: ВГУ, 2003.

122. Маликов A.B. О некоторых задачах, решаемых параллельными алгоритмами. Депонировано ВИНИТИ, № 753-В2001, 2001.

123. Маликов A.B. Организация параллельных вычислительных систем на базе ЛВС для обработки баз данных большого объема. Депонировано ВИНИТИ, № 754-В2001, 2001.

124. Маликов A.B. Параллельные машины и структура алгоритмов. Сборник «Материалы XXX научно-технической конференции по результатам работы ППС, аспирантов и студентов СевКавГТУ за 1999 год». Ставрополь: СевКавГТУ, 2000.

125. Маликов A.B. Проектирование реляционных баз данных на основе операций выборки и соединения. Исследование их свойств, монография/ под редакцией д.т.н., проф. Чефранова А.Г. Ставрополь: СевКавГТУ, 2002.

126. Маликов A.B. Разработка надстроек SQL для доступа к данным БД на основе выборочно-соединительной модели. Сборник «Материалы VI научно-технической конференции «Вузовская наука-Северо-Кавказскому региону»», часть II. Ставрополь: СевКавГТУ, 2002.

127. Маликов A.B. Способы организации вычислений в параллельных машинах баз данных. Сборник «V Всероссийская научная конференция студентов и аспирантов. Техническая кибернетика, радиоэлектроника и системы управления». Таганрог: ТРТУ, 2000.

128. Маликов A.B. Человек в информационном обществе (данные по России). Сборник «Профессиональная коммуникация и деятельность в личности специалиста». Ставрополь: СевКавГТУ, 1999.

129. Маликов A.B., Кириченко В.И., Евдокимов A.A. Автоматизация учебного процесса. Сборник «Проблемы создания автоматизированных обучающих и тестирующих систем». Новочеркасск: ЮРГТУ, 2001.

130. Маликов A.B., Лидовской К.В. Алгоритм поиска информации в реляционных базах данных, нормализованных на основе операций выборки и соединения. Журнал «Современные наукоемкие технологии», №2, 2004.

131. Маликов A.B., Маликова Е.В. Дополнительные возможности нормализации в реляционных базах данных. / Материалы V научно-технической конференции // Вузовская наука-Северо-Кавказскому региону. Ставрополь: СевКавГТУ. 2001. часть И.

132. Маликов A.B., Маликова Е.В. О динамическом разграничении полномочий пользователей баз данных. Сборник «Материалы VI научно-технической конференции «Вузовская наука-Северо-Кавказскому региону»», часть II. Ставрополь: СевКавГТУ, 2002.

133. Маликов A.B., Цвиринько H.A., Прокопенко В.И., Евдокимов A.A., Кириченко В.И. Интегрированная автоматизированная система управленияучебным процессом «Декамаг». Учебно-методическое пособие. Ставрополь: СевКавГТУ, 2004.

134. Маликов A.B., Чефранов А.Г. Аналитическая зависимость производительности параллельных вычислительных систем от числа процессоров. Журнал «Известия вузов. Северо-Кавказский регион. Технические науки», №2, 2003.

135. Маликов A.B., Чефранов А.Г., Лебедев В.И. Анализ функционирования реальных параллельных систем. Сборник «Известия ТРТУ. Специальный выпуск, материалы научной конференции». Таганрог: ТРТУ, 2001.

136. Мамаев Е. Microsoft SQL Server 2000. СПб.: БХВ-Петербург. 2002.

137. Мамиконов А.Г. Основы построения АСУ. М.: Высшая школа, 1981.

138. Мамиконов А.Г., Кульба В.В., Косяченко И.В. и др. Оптимизация структур распределенных баз данных в АСУ. М.: Наука, 1990.

139. МанделТ. Разработка пользовательского интерфейса. М.: ДМК, 2001.

140. Мантуров О.В. Курс высшей математики. М.: Высшая школа, 1991.

141. Математическое и программное обеспечение задач дискретной оптимизации. Сборник научных трудов. Отв. ред. И.В. Сергиенко. Киев: ИК, 1989.

142. МейерД. Теория реляционных баз данных. Пер. с англ. М.: Мир, 1987.

143. Менахем Базиян и др. Использование Visual FoxPro 6. Специальное издание. Перевод с англ. М.: Вильяме, 1999.

144. Методы дискретного анализа в изучении булевых функций и графов. Отв. ред. Ю.Л. Васильев. Новосибирск: ИМ, 1989.

145. Методы дискретного анализа в оптимизации управляющих систем. Редколлегия: Ю.Л. Васильев и др. Новосибирск: ИМ, 1989.

146. Методы дискретного анализа в теории графов и сложности. Гл. ред. А.Д. Каршунов. Новосибирск: ИМ, 1992.

147. Методы и алгоритмы анализа эмпирических данных. Сборник трудов/ Институт проблем управления. М.: ИЛУ, 1988.

148. Методы сбора и анализа сложноорганизованных данных. Сборник трудов/ АН СССР, Институт проблем управления, М.: ИЛУ, 1991.

149. Наац И.Э., Музенитов Ш.А. Дискретная математика. Ставрополь: Ставропольская краевая типография. 2001.

150. Нечепуренко М.И., Попков В.К., Майнагашев и др. Алгоритмы и программы решения задач на графах и сетях. Отв. ред. М.И. Нечепуренко. АН СССР, Сибирское отделение. Новосибирск: Наука. Сибирское отделение, 1990.

151. Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2000.

152. Озкарахан Э. Машины баз данных и управление базами данных. Пер. с англ. Под ред. Я.И. Фета. М.: Мир, 1989.

153. Ope О. Теория графов. М.: Наука, 1980.

154. Палей Д., Моделирование квазиструктурированных данных, журнал «Открытые системы», №9, 2002, http://vwvw.osp.ni/os/2002/09/057.htm.

155. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985.

156. Подбельский В.В. Язык С++. М.: Финансы и статистика, 2003.

157. Полищук Ю.М.,Хон В.Б. Теория автоматизированных банков информации. М.: Высшая школа, 1989.

158. Попов А.А. Программирование в среде СУБД FoxPro 2.0.

159. Построение систем обработки данных. М.: Март. 1996.

160. Пушников А.Ю. Введение в системы управления базами данных. Башкирский государственный университет. 1999.

161. Риордан, Ребекка М. Программирование в Microsoft SQL Server 2000. Шаг за шагом: практическое пособие. М.: ЭКОМ, 2002.

162. Рубан В.Я., Дрогаль Т.Г. Интеграция АСУ на основе баз данных. Киев: Тэхника, 1988.

163. Седжвик Р. Фундаментальные алгоритмы на С++. Анализ. Структуры данных. Сортировка. Поиск. СПб.: ДиасофтЮП, 2002.

164. Сигнор Р., Стегман М.О. Использование ODBC для доступа к базам данных. Пер. с англ. Под общ. ред. С.А. Каратыгина. М.: Бином: Научная книга, 1995.

165. Смирнов С.Н., Задворьев И.С. Работаем с ORACLE. М.: Гелиос АРВ, 2002.

166. Стулов А., Особенности построения информационных хранилищ, журнал «Открытые системы», №4, 2003.

167. Суслов А., Языки запросов для XML-данных, журнал «Открытые системы», №2, 2001, http://www.osp.ru/os/2001/02/065.htm

168. Тамер Оззу М., Валдуриз П. Распределенные и параллельные системы баз данных. Журнал «СУБД» // Открытые системы. 1996. №4.

169. Тербер К.Дж. Архитектура высокопроизводительных вычислительных систем. Перевод с англ. М.: Наука, 1985.

170. Тихомиров Ю.В. Microsoft SQL Server 2000. Разработка приложений. СПб.: БХВ-Петербург. 2000.

171. Фаронов В.В. Delphi 6: учебный курс. М.: Издатель Молга-чев С.В., 2001.

172. Фаронов В.В. Delphi. Программирование на языке высокого уровня. СПб.: Питер, 2004.

173. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. М.:Мир, 1984.

174. Хансен Г., Хансен Д. Базы данных: разработка и управление. М.: ЗАО «Издательство БИНОМ». 2000.

175. Харазишвили А.Б. Приложения теории множеств. Тбилиси: Издательство Тбилиского университета. 1989.

176. Харари Ф., Палмер Э. Перечисление графов. Перевод с английского. М.: Мир, 1977.

177. Харрингтон Джен JT. Проектирование реляционных баз данных. М.: Лори. 2000.

178. ХокниР., Джессхоуп К. Параллельные ЭВМ. Архитектура, программирование и алгоритмы. Перевод с английского Д.И. Абашкина / Под редакцией Е.П. Курочкина. М.: Радио и связь. 1986.

179. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974.

180. Цегелик Г.Г. Системы распределенных баз данных. Львов: Свит, 1990.

181. Шиянов E.H., Каргин Н.И., СербинаЛ.И., Чеботарев Е.А. Требования к организации учебного процесса и научной работы в Ставропольском государственном техническом университете. Ставрополь, 1998.

182. Шураков В.В. Обеспечение сохранности информации в системах обработки данных. М.: Финансы и статистика, 1985.-O1. Role Relation

183. J. IDr IDo nRole uroven ™-»-™----— IDo nRelation description