Разработка средств и методов анализа реляционных моделей баз данных тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ФУНКЦИОНАЛЬНЫЕ И МНОГОЗНАЧНЫЕ ЗАВИСИМОСТИ

ГИПОТЕЗА СТРУКТУРНОЙ НЕДООПРЕДЕЛЕННОСГИ

1.1. Информационное отношение. Гипотеза о конечности доменов I?

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

1.2. Зависимости в схемах реляционных баз данных 22

1.2.1.Функциональная зависимость 23

1.2.2.Многозначная зависимость 27

1.2.3.Свойства и аксиоматизация многозначных зависимостей 28

1.2.4.Обобщенная многозначная зависимость 29

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

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

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

ДАННЫХ

2.1. Этапы проектирования реляционных баз данных 39

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

2.1.2.Функциональные классы задач проектирования реляционных схем 43

2.2. Нормализация как этап проектирования схемы базы данных 44

2.2Л.Нормальные формы, базирующиеся на функциональных и многозначных зависимостях 47

2.2.2.Предпосылки определения новых типов нормальных форм 54

2.3. Моделирование процессов развития и реструктуризации в схемах реляционных баз данных 58

- 3

ЗАДАЧИ АНАЛИЗА СХЕМ РЕЛЯЦИОННЫХ БАЗ ДАННЫХ

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

3.1.3.Конструирование системы функциональных и многозначных зависимостей 65

3.1.2.Задание и проверка существования функциональной зависимости 66

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

3.2.1.Задача проверки выводимости зависимости из системы 70

3.2.2.Задача проверки ключей схемы реляционной базы данных 72

3.2.3.Задача поиска замыкания системы зависимостей 73

3.2:4.Задача определения системы зависимостей в проекции реляционной схемы 75

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

3.4. Композиция систем зависимостей реляционных схем 83

УЧЕБНАЯ САПР РЕЛЯЦИОННЫХ БАЗ ДАННЫХ

ОСНОВНЫЕ КОНЦЕПЦИИ И АЛГОРИТМЫ

4.1. Цели разработки учебной САПР схем реляционных баз данных 88

4.2. Архитектура и основные принципы проектирования и функционирования учебной САПР 91

4.2.1.Комплексы задач САПР 93

4.2.2.Подсистемы учебной САПР схем реляционных баз данных 95

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

4.3.2.Алгоритм проверки условий выводимости зависимости из системы 104

4.3.3.Алгоритм поиска системы ,зависимостей в проекции реляционной схемы 108

4.3.4.Алгоритм построения замыкания системы зависимостей 110

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

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

4.4.1.Проверка проектных решений схем реляционных баз данных при помощи реляционной СУБД "РЙСС" 123

4.4.2.Требования, предъявляемые к промышленной САПР реляционных баз данных 124

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

ЗАКЛЮЧЕНИЕ 128

СПИСОК ОСНОВНОЙ ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 130

ПРИЛОЖЕНИЕ

ВВЕДЕНИЕ Характеристика этапов развития информационной технологии Проблемы, связанные со сбором, накоплением, переработкой и передачей данных, были актуальны для человечества на протяжении всего периода его развития* Академик В#М.Глутков выделял возникновение письменности, изобретение книгопечатанья, применение ЭВМ, как существенные этапы в совершенствовании информационной деятельности. Первые два практически не касаются области переработки информации и являются характерными для бумажного этапа развития информатики /1 /. Машинный этап совершенствования информационной технологии можно условно разбить на два подэтапа: решение отдельных информационных задач; применение ЭВМ для комплексной автоматизации технологических участков деятельности человека по переработке информации.

Подэтап решения отдельных информационных задач явился необходимым подготовительным фундаментом перехода ко второму подэта-пу совершенствования информационной технологии с использованием ЭВМ.Характерной особенностью этого подэтапа является использование интегрированных информационных баз, которые представляют со» бой не что иное, как информационную модель объекта или системы. База данных в современных вычислительных системах представляет одну из основных компонент.

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

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

- 6

Краткий анализ исследований по реляционным базам данных Публикация работы Э.Кодда /41/ в 1971 г, дала мощный им-* пульс исследованиям по реляционному подходу в области баз и банков данных. Почти пятнадцатилетний термин исследований привел к появлению множества интересных и полезных публикаций, а современное их состояние свидетельствует о все более глубоком проникновении идей реляционного подхода не только в области баз и банков данных, но и в области чисто аппаратных и программных средств вычислительной техники, таких как новые перспективные архитектуры ЭВМ, интеллектуальные интерфейсы, реляционные языки программирования•

Т^кую популярность реляционного подхода можно объяснить с позиций двух сторон: во-первых, со стороны пользователя вычисли** тельных средств, в руки которого предоставляется наглядное и удобовоспринимаемое табличное представление данных, и, во-вторых, со стороны разработчиков и проектантов, для которых реляционный подход дает возможность применять на практике математические аппараты теории структур, ашгебры и логики. Современные представления о реляционном подходе в области баз данных вышли далеко- за пределы тех узких представлений о реляционных моделях, которые характерны для первых работ Э.Кодда /41,42/, К.Делобеля /47/, Р.Фейджина /54/, В.Армстронга /25/.

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

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

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

Диссертация посвящена вопросам разработки средств и методов анализа схем реляционных баз данных с выходом на проблемы их проектирования. Исходя из поставленных задач и целейf исследования проводились в первых пяти из приведенных выше направлений. Причем первое - третье направления анализировались с точки зрения обобщения и анализа полученных в них научных результатов. Обобщенным итогом.этой работы явилось издание обширного обзора А.А.Стогния и В.В.Пасичника "Реляционные модели баз данных" /17/. По четвертому и пятому направлениям были получены новые результаты, которые представляют собой основной итог диссертационных исследований автора, выполненных под руководством члена-корреспондента АН УССР А.А.Стогния.

- 8

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

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

Адекватность и непротиворечивость базы данных по отношению к описываемой ею проблемной области по мнению многих авторов /5,16,39/ является одной из центральных проблем в области баз данных, а схема базы данных, определяющая свойство непротиворечивости, относится к основным понятиям науки о банках данных»

Схема базы данных определяет множество допустимых состояний базы и представляется в терминах языка определения данных /ЯОД/. Переход базы в новое состояние определяется при помощи операторов языка манипулирования данными /ЯМДЛ Пара языков /ЯОД и ЯЩ/ определяет модель данных* .

Способ задания схемы базы данных существенным образом зависит от используемой модели данных. Настоящая работа посвящена вопросам анализа схем реляционных баз данных, поэтому в дальнейшем изложении понятие схемы базы данных и схемы реляционной базы данных будут нами отождествляться.

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

Такое определение схемы реляционной базы данных является более общим по сравнению с определениями, приведенными в большинстве работ по реляционным базам данных /18,3,20/, в которых под схемой подразумевается исключительно совокупность форматов записей (подмножеств имен атрибутов).

Реляционная схема и ее роль в представлении внешнего и концептуального уровней Реляционную схему, как и в К.Делобеля /45/, определим в виде , или что то же самое, с учетом переименования компонент R =<Л, S > , где Л представляет собой агрегат компонент

В наиболее общем случае мы не будем оговаривать "природу" системы зависимостей /предикатов/ 2 , в также соотнесение реляционной схемы к представлению некоторого класса объектов или связи между классами. При этом достигается более глубокий уровень однородности в процессах моделирования реального мира. Выделенный фрагмент реальности.в наиболее общем случае может быть представлен в виде некоторой совокупности классов объектов /"сущностей"/ и отношений /"связей"/ между ними /16,39/.

Пример такого описания в случае двух классов объектов I иЗ приведен на рис.1.

Рис.1. Предсатв л ение описания классов объектов! » vJ » а также связи между ними при помощи реляционных схем.

Каждая из реляционных схем R • , Rr , R; • определяет некоторое множество состояний информационных отношений Г^ , которые удовлетворяют системам зависимостей данных

• • В теоретико-модельных представлениях каждая t <1 t/<J из реляционных схем определяет некоторую модель с областью интерпретации {ВЛ » {Ж-} и ;} соответственно. Состоя

1 "J ние реляционных схем или, что то же самое, представление информационных отношений в определенные моменты времени"fc = {1/±,"t/2j., tn} являются ничем иным, как интерпретациями соответствующих и моделям с системами предикатов и .

В соответствии с предложениями исследовательской группы

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

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

Следуя /5/, концептуальная схема базы данных и реляционной базы в частности рассматривается как некоторая формальная теория. Для реляционного подхода характерной является гипотеза о существовании некоторого универсуума U , пред; тавляющего собой обобщенный (концептуальный/ взгляд на базу данных /универсальное отношение/51,58/. Такой подход следует считать скорее некоторым теоретическим обобщением, нежели практически целесообразным формализмом. Более выгодным, по нашему мнению, является вариант задания не одной, а некоторого множества реляционных схем R. ~ <Aj,Dj ,D0Mj , Sj > , определяющих концептуальную

Sj = {R? = <Aj,Dj,DOMj , 2j > j = I7n} схему реляционной базы данных. При этом необходимо помнить, что рассматриваемые реляционные схемы являются представлениями концептуального уровня. Таким образом, посредством концептуальной схемы задаются: множество имен атрибутов А ; множество доменов D ; множество функций соответствияВОМ ; множество зависимостей данных , определяемых на всем множестве атрибутов А , либо на некоторых его подмножествах. Внешняя схема

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

R. =<А-D- DOM: При этом необходимо отметить различие t V I/ V I в степени детализации и способа агрегации реляционных схем внешнего и концептуального уровней.

Множество внешних схем реляционной базы данных будем определять в форме S R = { 5 RK, К = i, В } , где D0M?\ 2?" >, I = ГТТЙ}.

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

Теоретический аспект

Большая разобщенность и отсутствие единого взгляда на зависимости данных 2 , отсутствие строгообоснованных рекомендаций по областям их применимости; зауженные представления о природе компоненты^ А , D , D0M> как области интерпретации зависимостей данных; слабая теоретическая проработка вопросов связи между динамикой проблемной области и преобразованиями реляционной базы данных и ее схемы; отсутствие концептуально обобщенного взягляда на проблемы нормализации схем реляционных баз данных; отсутствие формализованного аппарата конструирования схем реляционных баз данных, учитывающих процессы развития и реструктуризации схемы базы. Прикладной аспект

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

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

- 13

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

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

Практическая ценность диссертации. Разработанные средства и методы анализа схем реляционных баз данных, а также алгоритмы и программы могут использоваться: при построении обобщенной реляционной методологии проектирования баз данных; в учебном процессе для подготовки специалистов по проектированию схем реляционных баз данных; при разработке промышленных САПР баз данных. Реализация. В плане реализации основных концепций диссертационной работы разработаны основные элементы экспериментальной учебной САПР схем реляционных баз данных. Система используется в учебном процессе во время дипломного и курсового проектирования судентами специальности АСУ Львовского политехнического института. С использованием элементов САПР выполнено более 10 дипломных и 50 курсовых проектов. По результатам исследований и на основе программных реализаций подготовлен к изданию и утвержден, кафедрой цикл лабораторных работ по курсу "Базы и банки данных".

Адаптирована и передана для эксплуатации в ВЦ ЛПИ реляционная СУБД для СМ ЭВМ РИСС.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ I. Разработана и проверена на практике методика конструирования непротиворечивых систем зависимостей в схемах реляционных баз данных.

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

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

4. Сформулированы основные требования к проекту промышленного варианта САПР реляционных баз данных. Предложены концепции построения и разработана структура учебной системы автоматизированного проектирования схем реляционных баз данных.

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

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

7. Доказано: изоморфизм системы функциональных и многозначных зависимостей классу ДНФ булевых функций; возможность булевого задания предиката обобщенной многозначной зависимости; эквивалентность представления многозначной зависимости в виде системы элементарных зависимостей.

8. Разработаны методические материалы к лабораторным работам по курсу "Базы и банки данных". Адаптирована и передана в эксплуатацию в Щ ЛГИ реляционная СУЩ РИСС с библиографическими базами данных по реляционным моделям, ЭШ У-го поколения и алгоритмическому языку АДА, спроектированными с использованием экспериментальной учебной САПР схем реляционных баз данных.

- 128 -ЗАКЛЮЧЕНИЕ

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

1. Исследование новых типов зависимости данных.

2. Разработка новых видов нормальных форм для схем реляционных баз данных/

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

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

5. Постановка новых задач проектирования схем реляционных баз данных и разработка эффективных алгоритмов их решения.

6. Использование предложенного автором подхода структурной недоопределенности в смежных областях /исследованиях по искусственному интеллекту, структурам перспективных ЭВМ, моделирование процессов развития и поведения сложных систем/.

7. Создание полномасштабной промышленной САПР баз данных ориентированной на реляционный подход.

Полученные диссертантом результаты, а также разработанный про-грамный продукт могут найти применение, во-первых, в учебном процессе вузов, ведущих подготовку специалистов по вычислительной технике и АИС, и, во-вторых, в промышленности при проектировании и эксплуатации автоматизированных систем с использованием баз данных,

1. Глушков В.М. Основы безбумажной информатики. К.: Наука,1982.

2. Глушков В.М., Цейтлин Г.Е., Юценко Е.Л. Алгебра. Языки. Программирование. К.: Наукава думка, 1978.

3. Дейт К. Введение в системы баз данных. М.: Наука, 1980.

4. Деметрович Я., Дьепеши Д. Аксиоматизирование обобщенных функциональных зависимостей в реляционных банках данных. М.: Кибернетика, 198I, W 2, с.42-48.

5. Калиниченко Л.А. Методы и средства интеграции неоднородных баз данных. М.: Наука, 1983.

6. Кокорева Л.В., Малашинин И.И. Проектирование банков данных. М.: Наука, 1984.

7. Маклаков А.В. К вопросу определения функциональной зависимости между атрибутами отношений в реляционных базах данных. М.: Программирование, 1978, № I, с.60-63.

8. Мальцев А.И. Алгебраические системы. М.: Наука, 1971.

9. Мартин Дж. Организация баз данных в вычислительных системах. М.: Наука, 1980, изд.2.

10. Мендельсон Э. Введение в математическую логику. М.: Наука, 1971.

11. М.Мелдман, Д.Макгеод, Р.Пелликор, М.Сквайр.RI6S: система управления реляционными базами данных для малых ЭШ. М.: Финансы и статистика, 1982.

12. Пасичник В.В. Некоторые вопросы анализа реляционных моделей баз данных. Контрольно-измерительная техника, № 30, с.143-149, 1981.

13. Пасичник В.В. Методологические основы разработки учебной САПР баз данных. Труды П Всесоюзной конференции "Банки данных", секция 3, с.55-58, К., 1983.

14. Пасичник В.В. Реляционный подход к автоматизированному провотированию АСУ. Труды Всесоюзной конференции "Анализ эффективности и качества проектирования и функционирования АСУ в народном хозяйстве", М., 1983, с.220-221.

15. Пасичник В.В., Проданюк Н.М. Проектирование реляционных баз данных для САПР микроэлектронной аппаратуры. Всесоюзное научно-техническое совещание "Автоматизация проектирования микроэлектронной аппаратуры", Владимир, 1983.

16. Стогний А.А., Элланская JI.B. Описание и анализ информационных запросов при проектировании баз данных. Кибернетика № 3, 1982 г., стр. 45-53.

17. Стогний А.А., Пасичник В.В. Реляционные модели баз данных. ЙК АН УССР, К., 1983.

18. Ульман Д. Основы систем баз данных. М.: Финансы и статистика, 1983.

19. Дк.Хаббард. Автоматизированное проектирование баз данных. М.: Мир, 1984.

20. Цаленко М.Ш. Реляционные модели баз данных. В кн.: Алгоритмы и организация решения экономических задач. - М.: Статистика, 1977, Г- 9, с.18-36.

21. Цаленко М.Ш. Реляционные модели базы данных. В кн.: Алгоритмы и организация решения экономических задач. - М.: Статистики,1977, № 10, с.16-29.

22. Чоговадзе Г.Г., Сургуладзе Г.Г. Об одном алгоритме формирования неизбыточного множества функциональных отношений в реляционных базах данных. Сообщения АН Грузинской ССР. Том 96, № I, 1979, с.61-63.

23. Ако А.У. f Beeri С., Ullman J.D.The theory of joins in relational data bases. Proc. I8th Ann. Symp. on Founds of Compirt. Science, Oct. 197?, p.I0?-II3.

24. Zk. Aho A.V., Beeri C., Ullman J.D. The theory of joins in rela tional data bases. ACM TODS, v. No 3, 1979, p.293-314-.

25. Armstrong W. W. Dependency structure of data, base relationship. IFIP-74, Information Processing 74, North-Holland, Amsterdam, 1974, p.580-583.

26. Arora S.K., Smith K.S. A graphical interpretation of dependency structures in relational data bases. "Int. <T. Comput. and Inf. Sci.", 1981, v.IO, No 3, p. 187-213.

27. Arora S.K., Dumplata S.R. Theta-join and normalization. -"Int. J. Comput. and Inf. Scii\ I98I, v.IO, No 4, p. 261-281.

28. Beeri C., Fagin R., Norward J.H. A complete axiomatization for functional ahd multivalued dependencies in data base relations. Proc. ASM SIGMOD Int. Conf. on Management of Data, Toronto, 1977, p. 47-61.

29. Beeri C., Bernstein P.A., Goodman N. A sophisticate's .introduction to data base normalization theory. 4th Int. Conf. VLDB, 1978, p. II3-124.

30. Beeri C. , Kendelzon A.O., Sagiv Y. , Ullman J".D. Equivalence of relational data base schemas. Proc. Ilth ACM Symp. on Theory of Computing, 1979, p. 319-329.

31. Beeri C. On the membership problem for functional and multivalued dependencies in relational data base. ACM TODS, 1980, v.5. No 3, p.241-259.

32. Bernstein P.A. Synthesizing third normal form relations from functional dependencies. ACM TPDS, 1976, v.I, No 4, p. 277-298.

33. Bernstein P.A., Beeri C. Computational problems releted tothe design of normal form relational schemas. ACM TODS, 1979, v.4, Ко I, p.30-59

34. Brodie M.L. , Schmidt J.W. Final report of the ANSI /хЗ/ SPARL DBS-SG relational data base task group. Sept. I98I, ACM SIGMOD Record, 1982, v.I2, No4.

35. Chen P.P. The entity-relationship model: toward a unifiedview of data. ACM TODS, I976, v.I, No I, p. 9-36.

36. Codd E.F- Recent investigations into relational data base systems. Proc. IFIP Congress 1974, Proc. San Francisco, 1975, p.1017-1021.

37. Date C. Relational data base concepts. Datamation, 1976, v.22, No 4, p. 50-53.

38. Date C. A formal definition of the relational model. ACT.! SIGMOD Record, 1982, v.I3, No I, p. 18-30.

39. Delobel C- An overview of the relational data theory. IFIP-1980, 1980, p.413-426.

40. Delobel C., Casey R. Decomposition of a data base and the theory of boolean switehing functions. IBM J. R. & D. 1973» v.17,1. No 5, p. 374-386.,

41. Delobel C. , Leonard M. The decomposition process in a relational model. Proc. of Int. Workshop on data Structure Models for Information Systems, Namur, 1974, p.57-80.

42. Demetrovics J. Gy epesi Gy. Logical dependencies in relational data base. "MTA Szamitas techn. is automatiz'. kut intez. Ta-nul" r 1982,. No I33.

43. Fagin R„, Mendelzon A.O., Ullman I.D. A simplified universal relation assumption and its properties. "ACM TODS", I982, v.7, No 3, p.343-360.

44. Fadous R. Decomposition of a relation into fourth normal form! C0MPAC-79. Computer software and applications conference IEEE computer society's Svd international. Chicago. Nov. 6-8, 1979.

45. Fagin R. Multivalued depencies and a new normal form for relational data bases. ACM TODS, 1977, v.2, No 3, p.262-278.

46. Fagin R. Functional dependencies in a relational data base and propositional logic. IBM J. Res. & D., 1977, v.21, No 6, p.534-544.

47. Fagin R. Normal firms and relational data base operators, Proc. ACM SIGMOD Conf., 1979, p.I53-l60.

48. Fagin R. A normal form for relational data bases that is based on domains and keys. ACM Trans. Data base syst. (Sept. I98I), v. 6, No 3 (Sept. I98I), p. 387-415.

49. Fischer P.C., Tsou Don-Min. Decomposition of a relation scheme into Boyce-Codd normal form. "ACM 80s Proc. Annu Conf. Nashville Tenn. Oct. 27-29 I980"r 1980, p. 411-417.

50. Isloor S.S. An algorithm with logical simplicity for designing third normal form relations! data base schema for functional dependencies. Proc. of Int. Conf. on DBMS (ICMOD 78), Fast Milano, Italy, 1978, p. 31-50.

51. Kanellakis P.C. On the computational complexity of cardinality constraints in relational data bases. Information processing Letters, I980, v. II, No 2, p. 98-IOI.

52. Maier D. Minimum covers in the relational data base model.-"Journal of the ACM", 1980, v. 2?, No 4, p.664-675.

53. McLeod D.J. High level definition of abstract domains in a relational data base system. Computer Language, I977, v.2, No 3»p.61-73.

54. Mendelгтоп A.-0. On axiomatizing multivalued dependencies in relational data bases. "J. ACM", 1979, v.26, No I, p.37-44.

55. Nambiar K.K. Some fundamental concepts of relational data base. "Journal of the Computer Seciety of India", 1978, v.8, No 2, p.41-48.

56. Nambiar K.K. Some analytic tools for the design of relational data base systems. Proc. of the 6 Int. Conf. YLDB, I98O, p.4l?-428.

57. Rissanen J. Theory of relations for data bases a tutorial survey. Proc. 7th Symp. of Mathematical Foundations of Computer

58. Science, Lecture Notes on Computer Science, 1978, v.64, p.536-551.

59. Rissanen J. Independent components of relations. ACM TODS, 1977, v.2, No 4, p.317-325.

60. Sagiv Y. An algorithm for inferring multivalued dependencies with an application to propositional logic. "Journal of the ACM", 1980, v.27, No 2, p.250-263.

61. Sagiv Y., Delobel C., Parker D.S., Fagin R. An equivalence between relational data base dependencies and a subclass of propositional logic. "Journal of the ACN", I98I, No 3, P-435

62. Smith J.M. A normal form for abstract syntaxis. Proc. 4th Int. VLDB, 1978, p.156-162.

63. Tanaka Y. Logical design of a relational schoma and integrity of a data base. Proc. of the IFIP Working Conf. on Data Base Architecture, 1979, p.297-316.

64. Varoli M.Y. The decision problem for data base dependencies. Int. Proc. Lett., v.I2, No 5, Oct. 1981,- p.251-254.

65. Zaniolo C., Kelkanoff A.M. On the design of relational data base scheme. ACM TODS, I98I, v.6, No I, p.1-47.