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

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

00505451»

Громов Алексей Юрьевич

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

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

- 8 НОЯ 2012

Рязань 2012

005054519

Работа выполнена в ФГБОУ ВПО «Рязанский государственный радиотехнический университет»

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

кандидат технических наук, доцент Баранчиков Алексей Иванович

Скворцов Сергей Владимирович, доктор технических наук, профессор, ФГБОУ ВПО «Рязанский

государственный радиотехнический университет», профессор кафедры САПР вычислительных средств.

Миловзоров Александр Владимирович, кандидат технических наук, доцент, ОГБОУ ДПО «Рязанский институт развития образования», проректор по научно-методической работе.

ФГБОУ ВПО «Владимирский государственный университет имени Александра Григорьевича и Николая Григорьевича Столетовых»

Защита состоится « 21 » ноября в 12 часов на заседании диссертационного совета Д 212.211.01 в ФГБОУ ВПО «Рязанский государственный радиотехнический университет» по адресу: 390005, г. Рязань, ул. Гагарина, 59/1.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Рязанский государственный радиотехнический университет»

Автореферат разослан «02.».

Ученый секретарь диссертационного совета к.т.н., доц. В.Н. Пржегорлинский

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

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

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

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

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

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

Пусть множество А = {Аь А2, ..., Ag} атрибутов, выявленных при семантическом анализе предметной области, можно разделить на группы по некоторым признакам Y = {Yl5 Y2, ... , Yn}, тогда входное множество А можно разделить на подмножества ^y,' AY^, ..., Aтакие, что А = А у и Ay U...U A Y^ ■ Множество А будем называть множеством ранжируемых атрибутов по множеству признаков Y.

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

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

Таким образом, необходимо разработать алгоритм, позволяющий строить корректные схемы РБД R = {Ri, R2, ..., Rm} на основе выявленных в предметной области множеств ранжируемых атрибутов А и семантических зависимостей U=FuMVuJ [функциональных зависимостей (F), многозначных зависимостей (MV) и зависимостей соединения (J)].

Для решения поставленной задачи необходимо:

а) выявить атрибуты и семантические зависимости предметной области;

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

в) выделить множество признаков Y атрибутов А, основанных на сформулированных ограничениях. Разработчик логической структуры РБД, на основе сформулированных ограничений выделяет признаки атрибутов Y = {Yi, Y2, ... ,Y„}, по которым последние можно разделить на группы

г) построить корректную схему РБД R = {RbR2, ...,Rk, ...,Rm}, в которой отношения Rk (k=l,m) не должны содержать атрибуты разных признаков, с сохранением согласованности данных.

Степень разработанности темы. Разработке подходов и алгоритмов построения схем РБД, а также всем аспектам данных процессов посвящено достаточно большое количество трудов. Основные теоретические положения данного направления были заложены в 70-80-е годы 20-го века. Наиболее известными авторами данной тематики являются Э. Кодд, К. Дейт, Д. Мейер, X. Дарвен, Д. Ульман, Д. Уидом, А. Ахо, И. Хит, Р. Фейгин, Ф. Бернпггейн, Ж. Риссанен, М. Стоунбрейкер и другие.

Из отечественных авторов можно выделить Кузнецова С.Д., Пушникова А.Ю, Грушо A.A., Новосельского В.Б.

В работе Грушо A.A. приведен метод декомпозиции отношений БД в стандартные базовые отношения реляционной модели с использованием классификационных ограничений. В работах Новосельского В.Б. рассматривается генетический подход к проектированию распределённых БД.

В работах Ф. Бернштейна предложен алгоритм синтеза схем РБД. В работах Д. Мейера решаются недостатки алгоритма синтеза, касающиеся

2

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

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

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

- провести теоретические исследования в области построения схем РБД с учетом ранжируемых атрибутов;

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

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

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

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

Публикации. По теме диссертации опубликовано 10 работ, в том числе 6 статей, 5 из которых в журналах, рекомендованных ВАК, и 3 тезиса доклада в материалах всероссийских и международных научно-технических конференций. В Федеральной службе по интеллектуальной собственности, патентам и товарным маркам зарегистрирована одна программа для ЭВМ (свидетельство № 2012614219).

Апробация работы. Результаты диссертационной работы докладывались на 4 конференциях: 13-й всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и в образовании» (Рязань, 2008, 1 доклад), 15-й научно-технической конференции студентов.

молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и в образовании» (Рязань, 2010, 1 доклад), II международной научно-технической конференции "Технологии разработки информационных систем ТРИС-2011" (Таганрог, 2011, 1 доклад), всероссийской научно-технической конференции с международным участием «Компьютерные и информационные технологии в науке, инженерии и управлении» (КомТех- 2011) (Таганрог, ТГИ ЮФУ 2011, 1 доклад).

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

Достоверность научных положений подтверждается:

- корректным использованием математического аппарата реляционной алгебры, теории вероятностей, теории множеств, теории информации и теории планирования эксперимента;

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

Практическая ценность работы:

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

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

- на основе предложенных алгоритмов разработана программа для ЭВМ, позволяющая: строить схемы РБД с учетом ранжируемых атрибутов; автоматизировать процесс исследования алгоритмов построения схем РБД.

Основные положения, выносимые на защиту:

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

- алгоритмы построения схем РБД на основе синтеза отношений, удовлетворяющих нормальной форме Бойса - Кодда (НФБК), отличающиеся от классического алгоритма синтеза возможностью учета ранжируемых атрибутов;

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

многозначных зависимостей, зависимостей соединения и ранжируемых атрибутов.

Реализация и внедрение результатов работы

Результаты работы внедрены:

- в ООО «Эконом» при проектировании РБД, используемой несколькими территориально распределенными офисами;

- в ООО «ОЛВиД» при проектировании РБД с атрибутами, ранжируемыми с точки зрения конфиденциальности;

- в ООО «АРГО ТУР» при проектировании распределенной РБД;

- в учебный процесс ФГБОУ ВПО «Рязанский государственный радиотехнический университет» при обучении студентов направлений 230100 и 010500 по дисциплинам «Теория проектирования РБД», «Базы данных и СУБД» и «Программирование клиентских приложений БД».

Структура и объем работы

Диссертация состоит из введения, 4 глав, заключения и списка использованных источников из 101 наименования, изложенных на 193 страницах, содержит 35 рисунков и 22 таблицы. В приложении приведены документы о внедрении и практическом использовании результатов диссертации и свидетельство о регистрации программы для ЭВМ.

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

В первой главе «Анализ алгоритмов и подходов к проектированию схем реляционных баз данных» приведён краткий обзор наиболее известных на текущий момент моделей данных: инвертированных таблиц, иерархической модели, сетевой модели, реляционной модели, объектно-ориентированных моделей и модели данных SQL. Для решения задачи фрагментации схем РБД R наиболее предпочтительна реляционная модель данных, основными преимуществами которой, в контексте решаемой задачи, являются мощный аппарат реляционной алгебры и обоснованность фрагментации (вертикальной и горизонтальной) схем РБД.

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

РБД в оперативной аналитической обработке данных OLAP (OnLine Analytical Processing) и глубинном анализе данных (Data mining).

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

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

Во второй главе «Разработка алгоритмов построения схем РБД с ранжируемыми атрибутами» предложен метод построения схем РБД R={Ri, R2, ..Rm} с учетом ранжируемых атрибутов (рисунок 1).

На основе ограничений предметной области, не связанных с целостностью данных, разработчик логической структуры РБД формулирует множество признаков Y={Yi, Y2, ... , Yn} и подмножества атрибутов (i=l,n) с данными признаками, образующие множество А=Ау UAy U...UAy .

Рисунок 1 - Метод построения схем РБД с учетом ранжируемых атрибутов

Разработаны требования к формированию множества признаков У:

- признаки должны быть сформулированы таким образом, чтобы множества атрибутов различных признаков не пересекались: Ау п Ау.=#, щ, 1=Тд1,.¡=йп;

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

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

Входные н выходные данные разработанных алгоритмов

Вход: множество зависимостей и, включающее подмножества Е-зависимостей Г, МУ-зависнмостей МУ и ^зависимостей 3 (1Г=РиМУи.Т); множество ранжируемых атрибутов А={АЬ А2, ..., А8}; множество признаков ранжируемости У={УЬ У2, ..., Уп} и множества атрибутов каждого признака ..., , причем А=Ау и Ау^и.-.иАу^.

Выход: полная схема базы данных К={Я1, Иг, • с учетом

ранж1фуемых атрибутов.

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

Шаг 1. Для каждого входного ключевого атрибута К, схемы Ы вводится избыточность в виде атрибутов К,', таких что К,—>К,' и К;'—>К;, то есть К,е К, К,'е К', где К - множество входных ключевых

атрибутов, К' - множество атрибутов, введённых для однозначного определения ключевых входных атрибутов.

Шаг 2. Обработка входного множества семантических зависимостей II, целью которой является введение новых классов эквивалентности необходимых для построения отношений отвечающих за

согласованность данных при вертикальной фрагментации отношений.

Шаг 3. Построение схемы реляционной базы данных I* = {Я,. Я2, ..., Ик, ..., Кт} по классическим алгоритмам. Схемы отношений (к= 1,111) приводятся к максимально возможной нормальной форме (ЗНФ, НФБК, 4НФ, 5НФ) с учетом найденных в результате анализа предметной области семантических зависимостей: функциональных (Е-зависимостей), многозначных (МУ-зависимостей) и зависимостей соединения (I-зависимостей). Это требуется для сохранения независимости проекций при дальнейшей декомпозиции отношений.

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

отношений Ик.

Шаг 5. Полученная схема базы данных 1*={11ь ..., И™} подвергается обработке, заключающейся в задании соответствия между атрибутами К4 и К,' в отношениях, ключевые атрибуты которых имеют разные признаки У] 0=1,п).

На шаге 4 возможны различные варианты подмножеств ранжируемых атрибутов:

- отношение содержит атрибуты А; одного признака У;;

- отношение Як состоит из двух или более подмножеств атрибутов А!= {А„,А1Ь...,Аи}, А2= {А21,А22,...,А2г}, ... , Ар= {Ар1,Ар2,...,Ар,} 0, г и Ч -

количество атрибутов в соответствующих множествах) разных признаков {Аь А2, ..., Аь, ..., Ар} е 1*к, {Ам,Ам,...,Ам,}е AYj, где — подмножество атрибутов признака У,, Ь - количество атрибутов в множестве Аь, причем

Если отношение содержит атрибуты двух и более признаков, то возможны различные варианты его обработки, в зависимости от вида ключа Кк отношения Як, а также признаков ранжируемости неключевых атрибутов:

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

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

- есть неключевые атрибуты разных признаков; ключи отношения разных признаков.

Введено понятие Б-усиленной нормальной формы. Отношение находится в усиленной с точки зрения конфиденциальности атрибутов третьей нормальной форме ^-усиленной ЗНФ или ЗЗМ7), если оно находится в ЗНФ и все неключевые атрибуты отношения относятся к одному уровню конфиденциальности.

Понятие Б-усиленной нормальной формы может быть определено для других нормальных форм, в том числе для четвертой нормальной формы (4НФ), нормальной формы Бойса — Кодда (НФБК) и форм более высоких порядков.

Разработаны алгоритмы, основанные на нормализации отношений:

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

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

Введено понятие R-усиленной нормальной формы. Отношение г со схемой R удовлетворяет R-усиленной нормальной форме, если в R содержаться атрибуты одного признака Yj. Если отношение R нормализовано, то оно удовлетворяет соответствующей R-усиленной нормальной форме (R-усиленной ЗНФ, R-усиленной 4НФ и т. д.).

Схема РБД R={Rb R2, ..., Rk..., Rm} удовлетворяет R-усиленной нормальной форме, если все схемы отношений Rk удовлетворяют R-усиленной нормальной форме.

Разработаны алгоритмы, основанные на синтезе отношений:

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

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

- алгоритм построения схем РБД R на основе синтеза отношений Rk, удовлетворяющих нормальной форме Бойса - Кодда, отличающийся от классического алгоритма синтеза возможностью учета ранжируемых атрибутов. Алгоритм приведён в виде псевдокода, основанного на языке «Pascal»:

begin

Поиск неизбыточного редуцированного покрытия G для F; Поиск классов эквивалентности EF для G; for каждая F-зависимость Gi вида U —> V из EF(U) do for каждая F-зависимость Gj ^ Gi вида W —> Z из EF(U) do if U прямо определяет W then

begin G = G - {U —»V}; G = G - {W —> Z} + {W —» VZ}; end; for каждый класс эквивалентности EF do

CF=CF+ {(UbU2,..„Uf)-*V}; for каждая CF-зависимость CF, вида (Ui, U2, ..., Uh,..., Uf) V do if Uhj — перемещаемый атрибут в CF, then begin Uh = Uh — ич; V = V + Uhj; end; if Vj — посторонний атрибут в CF; then V = V - Vj; Построение схемы базы данных R = {Rb R2, ..., Rk, ..., R,„}; Обработка ранжируемых атрибутов каждой схемы Rk из R; end.

Где U, V, W и Z — подмножества входного множества атрибутов;

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

Поиск неизбыточного редуцированного покрытия G для F; Поиск классов эквивалентности EF для G; Минимизация покрытия G; Построение множества CF-зависимостей CF; Редуцирование множества CF-зависимостей CF; Построение схемы базы данных R = {Ri, R2, ..., Rk, ..., Rm}; for каждая схема Rk из R do for каждая MV-зависимость MV, вида U —1• V|Z из MV do if MVi применима к Rk then R = R — Rk + {UV, TJZ}; for каждая схема Rk из R do for каждая J-зависимость Ji вида *(U, V,..., Z) из J do if Ji применима к Rt then R = R — Rk + {U, V, ..., Z}; Обработка ранжируемых атрибутов каждой схемы Rk из R; end.

Предложенные алгоритмы, основанные на синтезе отношений, обладают полиномиальной временной сложностью.

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

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

предметных областей:

- сгенерированный набор данных должен включать множество атрибутов А = {Аь А2, ..., Ag}; множество семантических зависимостей U, включающих данные атрибуты, состоящее из подмножеств F-зависимостей F, MV-зависимостей MV и J-зависимостей J, причём U=FuMVuJ; множество признаков ранжируемости Y = {Yb Y2, ... , Yn} и соответствующие множества атрибутов каждого признака Av AYj, ..., Ау__ , причем A=AYiUAY2U...UAYn;

- допускается наличие атрибутов, не входящих в какие-либо

зависимости;

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

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

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

где XI - реализация псевдослучайной величины, Я -— параметр показательного распределения, п - реализация случайной величины, распределённой равномерно на интервале (0,1);

где п - параметр генерирования случайных чисел, а - параметр масштаба.

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

Входные и выходные данные алгоритма генерации предметных областей

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

Выход:

- множество атрибутов А ={АЬ А2, ...,Аг};

- множество признаков ранжируемо ста У = { У1, У2> ... , У„} и соответствующие множества атрибутов каждого признака

(1)

(2) (3)

х, = а\/—21иг, ,

Ау>, АУг, ..., АУ|1, причем А = АУ1иАУги...иАУ|1;

- множество семантических зависимостей Б, состоящее из подмножеств Б-зависимостей Р, МУ-зависимостей МУ и ^зависимостей J, причём 1Т=РиМУи1 (Р, МУ, Л — непересекающиеся множества семантических зависимостей).

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

Временная сложность предложенного алгоритма генерации является полиномиальной.

В четвертой главе «Экспериментальные исследования разработанных алгоритмов» с использованием основных принципов теории планирования эксперимента формулируются цели исследований:

- оценка корректности синтезированных схем реляционных баз данных, включающая:

- проверку синтезированной схемы РБД на удовлетворение

условиям нормализации;

- проверку синтезированной схемы РБД на удовлетворение

условиям наличия ранжируемых атрибутов;

- оценка временных характеристик исследуемых алгоритмов в зависимости от различных характеристик входных данных;

- сравнение разработанных алгоритмов, основанных на синтезе отношений, с классическим алгоритмом синтеза с точит зрения временных затрат;

- сравнение длительности обработки запросов к спроектированным схемам РБД с учётом ранжируемых атрибутов и без него.

Исходя из поставленных целей формулируются отклики экспериментов, которые можно разделить на качественные и количественные.

Планируются и проводятся эксперименты, направленные на получение оценок вероятностных характеристик временных затрат разработанных алгоритмов в зависимости от вида распределения количественных параметров входных предметных областей. Число опытов К необходимых для соблюдения доверительной вероятности /?=0.95 (!/.= 1.960), рассчитывается по формуле (4):

где

О

оценка дисперсии временных характеристик алгоритмов.

которая рассчитывается по формуле (5):

■V)

о--

N-1 ' (5)

Погрешность е выбирается равной 5 % от значения оценки математического ожидания и количественных откликов эксперимента, рассчитываемого по формуле (6):

N

Г' (6)

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

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

123456789 10 Количество уровней ранжируемоспі

15 25 35 45 55 65 75 85 Количество атрибутов в ПрО

123456789 Количество ]' -'!аш!СИМОете[! в ПрО Ц - временные затраты на генерацию предметной области и - временные затраты на синтез схемы РБД Ш - временные затраты на обработку ранжируемых атрибутов

23456789 10 Среднее количество атрибутов в каждой р-зависимэсти

Рисунок 2 — Результаты эксперимента с равномерным распределением

уровней факторов 13

По результатам проведённых экспериментов сделаны выводы:

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

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

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

Для проведения эксперимента, направленного на исследования временных затрат на запросы к спроектированным схемам РБД. генерируются тестовые предметные области, на основе которых проектируются схемы РБД по классическим и разработанным алгоритмам, содержащие 1000, 5000, 25000, 50000 и 100000 кортежей. Из результатов эксперимента на выборку видно, что с ростом количества хранимых кортежей время, затрачиваемое на соединение таблиц в случае более сильной фрагментации схемы БД, растёт медленнее времени, затрачиваемого на выборку данных (рисунок 3).

о

5 10000

о о

& 1000

§< 1000 2500 4900 10000 25000 50000100000

Количество кортежей в полной выборке ■ - схема РБД без учета ранжируемых атрибутов И - схема РБД с учетом ранжируемых атрибутов

100

10

Рисунок 3 — Временные затраты на полную выборку данных из РБД

14

В заключении подведены итоги проведённой работы и сформулированы основные научные и практические результаты.

Прилагаются копии актов о внедрении результатов работы и данные о регистрации программы для ЭВМ.

Основные результаты работы

— Проведён анализ алгоритмов и подходов построения схем РБД с учетом ранжируемых атрибутов.

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

— Разработаны алгоритмы, основанные на нормализации отношений, учитывающие наличие ранжируемых атрибутов в предметной области.

— Разработаны алгоритмы, основанные на синтезе отношений, учитывающие наличие ранжируемых атрибутов в предметной области.

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

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

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

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

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

1. Баранчиков А.И., Громов А.Ю. Построение схем реляционных баз данных в четвертой нормальной форме для информационных систем с конфиденциальной информацией // Известия ЮФУ. Технические науки. Тематический выпуск «Компьютерные и информационные технологии в науке, инженерии и управлении». №5(118). 2011 г. С. 65-69.

2. Баранчиков А. И., Громов А. Ю. Алгоритм синтеза реляционной базы данных, учитывающий атрибуты различной степени секретности // Системы управления и информационные технологии: науч.-техн. журн. N3(37). Москва - Воронеж, 2009. С. 25 - 27.

3. Баранчиков А. И., Громов А. Ю. Алгоритм построения схемы реляционной базы данных на основе множества многозначных и функциональных зависимостей, учитывающий атрибуты различной

степени секретности // Системы управления и информационные технологии: науч.-техн. журн. N1(43). Москва - Воронеж, 2011. С. 53 - 56.

4. Баранчиков А.И., Громов А.Ю. Построение схем реляционных баз данных с п-ранжируемыми атрибутами // Системы управления и информационные технологии: науч.-техн. журн. N2.1(48). Москва - Воронеж, 2012. С. 114-117.

5. Баранчиков А.И., Громов А.Ю. Алгоритм генерации формализованной модели предметной области // Вестник РГРТУ: науч.-техн. журн. №3 (выпуск 33). Рязань, 2010. С. 45-49.

Работы, опубликованные в межвузовских сборниках научных трудов

6. Баранчиков А.И, Громов А.Ю. Алгоритм построения схемы реляционной базы данных, содержащей атрибуты различной степени секретности // Информатика и прикладная математика. Рязан. гос. ун-т им. С.А. Есенина, 2008. С. 7-12.

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

7. Баранчиков А.И., Громов А.Ю. Алгоритм синтеза схемы реляционной базы данных, содержащей атрибуты различной степени секретности // Новые информационные технологии в научных исследованиях и в образовании: тез. докл. 13-й Всеросс. науч.-техн. конф. Рязан. гос. радиотехн. ун-т. Рязань, 2008. С. 125-126.

8. Баранчиков А.И., Громов А.Ю. Алгоритм построения формализованной модели предметной области // Новые информационные технологии в научных исследованиях и в образовании: тез. докл. 15-й науч.-техн. конф. Рязан. гос. радиотехн. ун-т. Рязань, 2010. С. 66-67.

9. Баранчиков А.И., Громов А.Ю. Алгоритм построения схем реляционных баз данных на основе многозначных и функциональных зависимостей с п-ранжируемой конфиденциальностью атрибутов // Технологии разработки информационных систем ТРИС-2011: тез. докл. II Междунар. науч.-техн. конф. Таганрог, 2011. С. 113.

Регистрация программы для ЭВМ

Ю.Громов А.Ю., Баранчиков А.И. Свидетельство о государственной регистрации программы для ЭВМ «ЗупЙ^Бт» №2012614219 // Федеральная служба по интеллектуальной собственности, патентам и товарным маркам. Зарегистрировано в Реестре программ для ЭВМ 12 мая 2012 г.

Громов Алексей Юрьевич

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

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

Подписано в печать 03.10.12. Формат бумаги 60x84 1/16. Бумага офсетная. Печать трафаретная. Усл. печ. л. 1,0. Тираж 100 экз.

Рязанский государственный радиотехнический университет. 390005, Рязань, ул. Гагарина, 59/1. Редакционно-издательский центр РГРТУ.

ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ.

ВВЕДЕНИЕ.

1 АНАЛИЗ АЛГОРИТМОВ И ПОДХОДОВ К ПРОЕКТИРОВАНИЮ СХЕМ РЕЛЯЦИОННЫХ БАЗ ДАННЫХ.

1.1 Тенденции развития реляционной модели данных.

1.2 Анализ современных подходов и алгоритмов проектирования схем реляционных баз данных.

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

1.4 Анализ подходов к проектированию логической структуры распределенных БД.

1.5 Аналоги.

1.6 Основные результаты.

2 РАЗРАБОТКА АЛГОРИТМОВ ПОСТРОЕНИЯ СХЕМ РБД С РАНЖИРУЕМЫМИ АТРИБУТАМИ.

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

2.1.1 Алгоритмы построения схем РБД, основанные на нормализации отношений до ЗНФ, с учетом двух уровней ранжируемости.

2.1.2 Алгоритм построения схем РБД, основанный на нормализации отношений до 4НФ, с учетом двух уровней ранжируемости.

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

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

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

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

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

2.3 Анализ каналов утечки информации.

2.4 Тенденции развития темы диссертации.

2.5 Основные результаты.

3 ГЕНЕРАЦИЯ ФОРМАЛИЗОВАННОЙ ПРЕДМЕТНОЙ ОБЛАСТИ.

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

3.2 Алгоритм генерации формализованной предметной области.

3.3 Основные результаты.

4 ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ РАЗРАБОТАННЫХ АЛГОРИТМОВ.

4.1 Реализация алгоритмов.

4.2 Планирование экспериментов.

4.3 Сбор и обработка данных экспериментов.

4.4 Основные результаты.

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

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

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

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

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

Пусть множество А = {Аь А2, ., Ag} атрибутов, выявленных при семантическом анализе предметной области, можно разделить на группы по некоторым признакам У = {У|, У 2, . , У»}, тогда входное множество А можно

разделить на подмножества , Ау ., такие, что

А = Ау^иАу и.иАуМножество А будем называть множеством ранжируемых атрибутов по множеству признаков У.

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

Таким образом, необходимо разработать алгоритм, позволяющий строить корректные схемы РБД I* = ., Я,,,} на основе выявленных в предметной области множеств ранжируемых атрибутов А и семантических зависимостей и=ЕиМ\\л1 [функциональных зависимостей (Г), многозначных зависимостей (МУ) и зависимостей соединения (Л)].

Для решения поставленной задачи необходимо: а) выявить атрибуты и семантические зависимости предметной области; б) сформулировать ограничения предметной области. Здесь под ограничениями понимаются правила храпения информации конкретной предметной области (например, бизнес-правила, правила, связанные с конфиденциальностью информации, или хранением информации в распределённой РБД), которые не могут быть выражены ограничениями целостности, привычными для разработчиков РБД; в) выделить множество признаков У атрибутов А, основанных на сформулированных ограничениях. Разработчик логической структуры РБД, на основе сформулированных ограничений выделяет признаки атрибутов Y = {Yb Y2, . , Yn}, по которым последние можно разделить на группы А А А • r1 т2 тп г) построить корректную схему РБД R = {Rb R2, ., Rk, ., Rm}, в которой отношения Rk (k=l,m) не должны содержать атрибуты разных признаков, с сохранением согласованности данных.

Степень разработанности темы. Разработке подходов и алгоритмов построения схем РБД, а также всем аспектам данных процессов посвящено достаточно большое количество трудов. Основные теоретические положения данного направления были заложены в 70-80-е годы 20-го века. Наиболее известными авторами данной тематики являются Э. Кодд, К. Дейт, Д. Мейер, X. Дарвен, Д. Ульман, Д. Уидом, А. Ахо, И. Хит, Р. Фейгин, Ф. Бернштейн, Ж. Риссанен, М. Стоунбрейкер и другие.

Из отечественных авторов можно выделить Кузнецова С.Д., Пушникова А.Ю, Грушо A.A., Новосельского В.Б.

В работе Грушо A.A. приведен метод декомпозиции отношений БД в стандартные базовые отношения реляционной модели с использованием классификационных ограничений. В работах Новосельского В.Б. рассматривается генетический подход к проектированию распределённых БД.

В работах Ф. Берншгейна предложен алгоритм синтеза схем РБД. В работах Д. Мейера решаются недостатки алгоритма синтеза, касающиеся необходимости наличия отношения в результирующей схеме РБД R, содержащего универсальный ключ отношений, а также учета атрибутов, не использующихся в семантических зависимостях U,eU предметной области. В работах И. Хита и Р. Фейгина рассмотрены вопросы, связанные с декомпозицией отношений без потерь информации. Ж. Риссанен в своих трудах рассматривает проблемы, связанные с потерей зависимостей при декомпозиции без потерь отношений Як, и предлагает вариант решения данной задачи. К. Дейт на основе результатов Риссанена приводит методику декомпозиции отношений на независимые проекции.

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

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

- провести теоретические исследования в области построения схем РБД с учетом ранжируемых атрибутов;

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

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

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

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

Публикации. По теме диссертации опубликовано 10 работ, в том числе 6 статей, 5 из которых в журналах, рекомендованных ВАК, и 3 тезиса доклада в материалах всероссийских и международных научно-технических конференций. В Федеральной службе по интеллектуальной собственности, патентам и товарным маркам зарегистрирована одна программа для ЭВМ (свидетельство № 2012614219).

Апробация работы. Результаты диссертационной работы докладывались на 4 конференциях: 13-й всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и в образовании» (Рязань, 2008, 1 доклад), 15-й научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и в образовании» (Рязань, 2010, 1 доклад), II международной научно-технической конференции "Технологии разработки информационных систем ТРИС-20П" (Таганрог, 2011, 1 доклад), всероссийской научно-технической конференции с международным участием «Компьютерные и информационные технологии в науке, инженерии и управлении» (КомТех- 2011) (Таганрог, ТТИ ЮФУ 2011, 1 доклад).

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

Достоверность научных положений подтверждается:

- корректным использованием математического аппарата реляционной алгебры, теории вероятностей, теории множеств, теории информации и теории планирования эксперимента;

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

Практическая ценность работы:

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

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

- на основе предложенных алгоритмов разработана программа для ЭВМ, позволяющая: строить схемы РБД с учетом ранжируемых атрибутов; автоматизировать процесс исследования алгоритмов построения схем РБД.

Основные положения, выносимые на защиту:

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

- алгоритмы построения схем РБД на основе синтеза отношений, удовлетворяющих нормальной форме Бойса - Кодда (НФБК), отличающиеся от классического алгоритма синтеза возможностью учета ранжируемых атрибутов;

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

Реализация и внедрение результатов работы

Результаты работы внедрены:

- в ООО «Эконом» при проектировании РБД, используемой несколькими территориально распределенными офисами;

- в ООО «ОЛВиД» при проектировании РБД с атрибутами, ранжируемыми с точки зрения конфиденциальности;

- в ООО «АРГО ТУР» при проектировании распределенной РБД;

- в учебный процесс ФГБОУ ВПО «Рязанский государственный радиотехнический университет» при обучении студентов направлений 230100 и 010500 по дисциплинам «Теория проектирования РБД», «Базы данных и СУБД» и «Программирование клиентских приложений БД».

Структура и объем работы

Диссертация состоит из введения, 4 глав, заключения и списка использованных источников из 101 наименования, изложенных на 193 страницах, содержит 35 рисунков и 22 таблицы. В приложении приведены документы о внедрении и практическом использовании результатов диссертации и свидетельство о регистрации программы для ЭВМ.

Основные результаты работы состоят в следующем:

- проведён анализ алгоритмов и подходов построения схем реляционных баз данных с учетом ранжируемых атрибутов;

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

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

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

- разработаны алгоритмы, основанные на нормализации отношений, учитывающие наличие ранжируемых атрибутов в предметной области;

- разработаны алгоритмы, основанные на синтезе отношений, учитывающие наличие ранжируемых атрибутов в предметной области;

- проведена оценка временной сложности разработанных алгоритмов и доказана их сходимость;

- проведён анализ задачи генерирования формализованных предметных областей, необходимых для экспериментальных исследований алгоритмов построения схем РБД;

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

- на основе предложенных алгоритмов разработана программа для ЭВМ, позволяющая строить схемы РБД с учетом наличия ранжируемых атрибутов в предметной области. Алгоритмы реализованы на языке Java с использованием СУБД PostgreSQL 9.1.2.

ЗАКЛЮЧЕНИЕ

1. Гектор Гарсиа-Молина, Джеффри Ульман, Дженифер Уидом Системы баз данных. Полный курс // Москва, Санкт-Петербург, Киев: Вильяме, 2003. 1088 с.

2. Кузнецов С. Д. Основы баз данных // 2-е изд. М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2007. 484 с. ISBN 978-5-94774-736-2.

3. Коннолли, Томас, Бегг, Каролин. Базы данных. Проектирование, реализация и сопровождение. Теория и практика // 3-е издание. Пер. с англ. М. : Издательский дом "Вильяме", 2003. 1440 с. ISBN 5-8459-0527-3.

4. Дейт К. Дж. Введение в системы баз данных // 8-е изд. Пер. с англ. М: Вильяме, 2005. 1328 с.

5. Когаловский М. Р. Энциклопедия технологий баз данных // М.: Финансы и статистика, 2002. 800 с.

6. Когаловский М. Р. Перспективные технологии информационных систем // М.: ДМК Пресс, 2003. 288 с.

7. Бойко В.В., Савинков В.М. Проектирование баз данных информационных систем // М.: Финансы и статистика, 1989. 351 с.

8. Чертовской В.Д. Базы и банки данных: Учебное пособие // СПб: Изд-во МГУП, 2001.220 с.

9. Codd, E.F. Derivability, Redundancy, and Consistency of Relations Stored in Large Data Banks // IBM Research Report RJ599, August 19, 1969.

10. Bleier, R.E. Treating hierarchial data structures in the SDC time-shared data management system (TDMS) // Proc. ACM 22nd Nat. Conf., 1967, MDI

11. Publications, Wayne, pa., pp. 41-49.

12. C.J. Date. The Birth of the Relational Model (Part 3 of 3) // Intelligent Enterprise, Vol. 1, No 3, December 1998.

13. Martin, James. Semantic Disintegrity in Relational Operations // Fourth-Generation Languages Volume I: Principles . Prentice-Hall, 1985.

14. Bell, Colin J. A Relational Model for Information Retrieval and the Processing of Linguistic Data // IBM Research Report RC1705, November 3, 1996.

15. Haderle D.J., Jackson R.D. IBM Database 2 Overview // IBM Syst. J. 1984. 23, N2. C. 112-125.

16. Дейт К. Руководство по реляционной системе DB2 // М.: Финансы и статистика. 1988. 320 с.

17. Blazdell R.K. The IBM SQL / DS System // Relational Databases. Oxford e.a., 1986. C. 39-46.

18. Линдсей Б.Дж. Опыт создания системы управления распределенными базами данных R* //ТИИЭР. 1987. 75, N 5. С. 165-172.

19. Lorie R.A., Plouffe W. Relational Databases for Engineering Data // Proc. 2nd Int. Conf. Found. Comput. Aided Process Des., New York, Aug. 1983. New York, 1983. pp. 132-139.

20. X. Дарвен, К. Дейт Третий манифест // СУБД, No. 1, 1996.

21. С. J. Date and Hugh Darwen Databases, Types, and the Relational Model. The Third Manifesto //Addison Wesley / 3th edition. 2006.

22. К. Дейт, Хыо Дарвен Основы будущих систем баз данных. Третий манифест // М: Янус-К, 2004.

23. Darwen, Hugh Relational-Valued Arributes; or, Will the Real First Normal Form Please Stand Up? // in C.J. Date and Hugh Darwen, Relational Database Writings 1989-1991 / Addison-Weslwy, 1992.

24. M. Аткинсон, Ф. Бансилон, Д. ДеВитт, К. Диттрих, Д. Мейер, С.Здоник Манифест систем объектно-ориентированных баз данных // жур. СУБД № 4 Пер.:М.Р. Когаловский. «Открытые системы», 1995 / Нов. Ред. С.Д. Кузнецов2009.

25. F. Bancilhon Object-oriented database systems // Proceedings of the ACM SIGACT- SIGMOD-SIGART / Conference on the Principles of Database Systems, Austin, Texas, May 1988.

26. B. Nixon Implementation of a Compiler for a Semantic Data Model: Experience with Taxis // ACM SIGMOD, 1987.

27. T. Atwood An object-oriented DBMS for design support applications // Ontologic Inc. Report.

28. Caruso, Sciore The VISION Object-Oriented Database Management System // Proceedings of the Workshop on Database Programming Languages, Roscoff, France, September 1987.

29. Stanley Benjamin Zdonik, David Maier Readings in object-oriented database systems.

30. The Object Data Standard: ODMG 3.0 // Edited by R.G.G. Cattel, Douglas K. Barry. Morgan Kauffmann Publishers, 2000.

31. M. Stonebraker, L. Rowe, B. Lindsay, J. Gray, M. Carey, M. Brodie, Ph. Bernstein, D. Beech Third-Generation Data Base System Manifesto // Proc. IFIP WG 2.6 Conf. on Object-Oriented Databases, July 1990, ACM SIGMOD Record 19, No. 3 (September 1990).

32. C. J. Date, Hugh Darwen Foundation for Object/Relational Databases: The Third Manifesto //Addison-Wesley Pub Co, (June 1998).

33. C.J. Date with Hugh Darwen A Guide to the SQL Standard. Fourth edition // Addison-Wesley Longman, 1997.

34. Jim Melton, Alan R. Symon SQL: 1999. Understanding Relational Language Components // Morgan Kaufmann Publishers, 2002.

35. Jim Melton Advanced SQL: 1999 / Understanding Object-Relational and Other Advanced Features. Morgan Kaufmann Publishers, 2003.

36. Пушников А.Ю. Введение в системы управления базами данных. Часть 1. Реляционная модель данных: Учебное пособие // Изд-е Башкирского ун-та.

37. Уфа, 1999. 108 с. ISBN 5-7477-0350-1

38. Стандарт SQL Электронный ресурс. // Режим доступа: http://www.wiscorp.com/SQLStandards.html, свободный. Загл. с экрана (дата обращения: 14.08.2012).

39. В.В. Кириллов Основы проектирования реляционных баз данных // НИУ ИТМО, Учебное пособие.

40. Codd E.F. Further Normalization оГ the Data Base Relational Model // Rustin R.J.(ed.), Data Base Systems, Courant Computer Science Symposia Series 6. Englewood Cliffs, N.J.: Prentice-I-Iall. 1972.

41. Мейер Д. Теория реляционных баз данных // М.: Мир, 1987. 608 с.

42. Codd E.F. Recent Investigations into Relational Data Base Systems // Proc. IFIP Congress. Stockholm, Sweden, 1974.

43. Heath I.J. Unacceptable File Operations in a Relational Database // Proc. 1971 ACM SIGFIDET Workshop on Data Description, Access, and Control. San Diego, Calif. November 1971.

44. Rissanen J. Independent Components of Relations // ACM TODS. December 1977. 2, №4.

45. Fagin R. Multivalued Dependencies and a New Normal Form for Relational Databases //ACM TODS. September 1977. 2, № 3.

46. Aho A.V., Beeri C, Ullman J. D. The Theory of Joins in Relational Databases // ACM TODS. September 1979. 4, No 3.

47. Fagin R. Normal Forms and Relational Database Operators // Proc. 1979 ACM SIGMOD Intern. Conf. on Management of Data. Boston, Mass. May—June 1979.

48. Hall P., Owlett J., Todd S.J.P. Relations and Entities // G. M. Nijssen (ed.). Modelling in Data Base Management Systems. Amsterdam, Netherlands: North-Holland; NewYork, N.Y.: Elsevier Science, 1975.

49. Smith J.M. A Normal Form for Abstract Syntax // Proc. 4th Intern. Conf. on Very Large Data Bases. Berlin, Federal German Republic. September 1978.

50. Maier D., Ullman J.D. Fragments of Relations // Proc. 1983 SIGMOD Intern.

51. Meaning //ACM TODS. December 1979. 4, № 4.

52. Barker, R. (1990). CASE*Method Entity Relationship Modelling // Wokingham, England, Addison- Wesley.

53. Баранчиков А.И., Асташина E.A. Модифицированный алгоритм реинжиниринга функциональных зависимостей // Вестник РГРТУ: науч.-техн. жур. №4 (выпуск 34). Рязань, 2010.

54. Классификация OLAP-систем вида xOLAP Электронный ресурс. / А.Н.Андреев, 2010. Режим доступа: http://citforum.ru/consulting/BI/xolapclassification/, свободный. - Загл. с экрана (дата обращения: 21.08.2012).

55. Лилия Козленко Информационная безопасность в современных системах управления базами данных // КомпьютерПресс 3'2002.

56. В.Б. Бетелин, В.А. Галатенко, М.Т. Кобзарь, A.A. Сидак, И.А. Трифаленков Профили защиты на основе "Общих критериев" // Аналитический обзор / бюллетень JET INFO.

57. ГОСТ Р ИСО/МЭК 15408-1-2002. Информационная технология. Методы и средства обеспечения безопасности. Критерии оценки безопасности информационных технологий. Часть 1. Введение и общая модель // М.: ИПК Издательство стандартов, 2002.

58. ГОСТ Р ИСО/МЭК 15408-2-2002. Информационная технология. Методы и средства обеспечения безопасности. Критерии оценки безопасности информационных технологий. Часть 2. Функциональные требования безопасности // М.: ИПК Издательство стандартов, 2002.

59. ГОСТ Р ИСО/МЭК 15408-3-2002. Информационная технология. Методы и средства обеспечения безопасности. Критерии оценки безопасности информационных технологий. Часть 3. Требования доверия к безопасности // М.: ИПК Издательство стандартов, 2002.

60. ГОСТ Р ИСО/МЭК 17799—2005 Национальный стандарт РФ «Информационная технология. Практические правила управленияинформационной безопасностью» // М.: ИПК Издательство стандартов, 2005.

61. ГОСТ Р 50739-95 Средства вычислительной техники. Защита от несанкционированного доступа к информации. Общие технические требования // М.: ИПК Издательство стандартов, 2002.

62. U.S. Department of Defense. Trusted Computer System Evaluation Criteria ("Оранжевая" книга) // Document № DoD 5200-28-STD, DoD National Computer Security Center. December 1985.

63. U.S. National Computer Security Center. Trusted Database Management System Interpretation ("Сиреневая" книга) // Document № NCSC-TG-201, Version 1. April 1991.

64. Сергей Кузнецов Крупные проблемы и текущие задачи исследований в области баз данных // Институт системного программирования РАН, 2005.

65. Гостехкомиссия России. Руководящий документ. Средства вычислительной техники. Защита от несанкционированного доступа к информации. Показатели защищенности от несанкционированного доступа к информации // Москва, 1992

66. Date С. J. What is a Distributed Database System? // Date С. J. Relational Database Writings 1985-1989. Reading, Mass.: Addison- Wesley, 1990.

67. E. F. Codd Is Your DBMS Really Relational? / Does Your DBMS Run by the Rules? // Computerworld. October Hand 21, 1985.

68. Date C.J. Distributed Database: A Closer Look // C.J. Date and Hugh Darwen. Relational Database Writings 1989-1991. Reading, Mass.: Addison-Wesley, 1992.

69. Rothnie J. В., Goodman N. A Survay of Research and Development in Distributed Database Management // Proc. 3rd Int. Conf. on Very Large Data Bases. Tokyo, Japan October 1977.

70. Williams R. et al. R*: An Overview of the Architecture // P. Scheuermann. Improving Database Usability and Responsiveness. New York, N.Y.: Academy Press, 1982.

71. Stonebraker M. R., Neuhold E. J. Distributed Data Base Version of Ingres //

72. Proc. 2Nd Berkley Conf. On Distributed Data Management and Computer Networks. Lowrence Berkley Laboratory, May 1977.

73. Грушо A.A. Тимонина E.E. Теоретические основы защиты информации // Издательство Агентства "Яхтсмен", 1996.

74. Новосельский В.Б, Применение генетических алгоритмов при проектировании расиределйнных баз данных // Науч.-техн. вестник СПбГУ ИТМО, 2008.

75. Новосельский В.Б. Решение задачи распределения реляционной базы данных // Журнал научных публикаций аспирантов и докторантов. 2008. N5. с. 158-160, ISSN 1991-3087.

76. Хореа-Адриан Глебла, Анка Гог Построение оптимального размещения для распределенных баз данных // STUDIA UNIV. BABE.BOLYAI, INFORMATICA, Volume L, Number 1, 2005.

77. Баранчиков А.И, Громов А.Ю. Алгоритм построения схемы реляционной базы данных, содержащей атрибуты различной степени секретности // Информатика и прикладная математика. Рязап. гос. ун-т им. С.А. Есенина, 2008. С. 7-12.

78. Баранчиков А. И., Громов А. 10. Алгоритм синтеза реляционной базы данных, учитывающий атрибуты различной степени секретности // Системы управления и информационные технологии: науч.-техн. журн. N3(37). Москва Воронеж, 2009. С. 25 - 27.

79. Баранчиков А.И., Громов А.Ю. Построение схем реляционных баз данных с п-ранжируемыми атрибутами // Системы управления и информационные технологии: науч.-техн. журн. N2.1(48). Москва Воронеж, 2012. С. 114-117.

80. Вентцель Е.С Теория вероятностей // 4-е изд, 1969. 576с.

81. Ч. Хикс Основные принципы планирования эксперимента // Перевод с английского под редакцией В. В. Налимова. Издательство «Мир», Москва 1967.

82. В. В. Налимов, Т. И. Голикова Логические основания планирования эксперимента // Издание 2-е, «Металлургия», Москва, 1981.

83. Красовский Г.И., Филаретов Г.Ф. Планирование эксперимента // Минск: изд-во БГУ, 1982.302 с.

84. Б. Я. Советов С. А. Яковлев Моделирование систем. Учеб. для вузов // 3-е изд., перераб. и доп. М.: Высш. шк., 2001. 343 с.

85. Вадзинский Р. Н. Справочник по вероятностным распределениям // Издательство «Наука», СПб: 2001. 295 е., ил. 116.

86. Вентцель Е.С., Овчаров Л.А. Теория вероятностей и ее инженерные приложения. Учеб. пособие для вузов // 2-е изд., стер. М.: Высш. шк., 2000. 480 с.

87. Баранчиков А.И., Громов А.Ю. Алгоритм генерации формализованной модели предметной области // Вестник РГРТУ: науч.-техн. журн. №3 (выпуск 33). Рязань, 2010. С. 45-49.