Понятия математической логики

Перечислим необходимые для реляционного исчисления понятия математической логики.

1. Символы переменных и констант. В языковых конструкциях реляционного исчисления им соответствуют имена атрибутов и переменных, а также константы.

2. Логические связки "и", "или", "не" и знаки сравнения = # (не равно), >, <, >=, <=.

3. Термы, т. е. любые константы и переменные, а также функции, аргументами которых служат термы.

4. Элементарные формулы - предикаты, аргументами которых являются термы. Предикаты, связанные операциями "и", "или", "не", также являются элементарными формулами Элементарными формулами служат, например, выражения Фамилия = "Мишенин" и Сумма <= Итог.

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

В применяемых ниже языковых конструкциях используется синтаксис языков ALPHA и QUEL. Объявление переменной и ее привязка к определенному отношению производятся с помощью оператора Диапазон (range) следующего вида

range of <переменная> is <отношение><квантор>

Квантор принимает одно из значений:

some, когда переменная обозначает одну из строк отноше­ния (квантор существования);

all, когда переменная обозначает все строки отношения (квантор общности).

Основной формой оператора запроса Получить (get) является выражение

get <отношение> (<целевой список>) where <условие>.

Условие соответствует формуле исчисления кортежей. В условиях можно использовать все знаки сравнения и логические связки "и", "или", "не".

Языковая конструкция для кванторов может быть такой:

range of Z is Перевозка some.

Переменная Z при вычислении означает одну из строк (some -квантор существования) отношения Перевозка.

range of W is Перевозка all.

Переменная W означает все строки (all - квантор общнос­ти) отношения Перевозка.

Реализацией запроса к базе данных из "Получить даты поставок из города Киева" является запись средствами реляционного исчисления:

range of Z is Перевозка some

get W (Дата) where Поставщик.Код_поставщика=г.Код_поставщика

and Поставщик.Город="Киев".

В последнее время наиболее распространенным декларативным языком запросов является SQL (структурированный язык запросов). Центральным средством доступа к БД в SQL являются команда Select и ее параметры - From, Where, Group by, Having, Order by.

В команде Select указываются имена выводимых атрибутов или знак *, если надо выводить все атрибуты. Параметр From является обязательным и содержит имена требуемых для выполнения запроса отношений. Если здесь указано несколько отношений, то они будут преобразованы командами натурального соединения в одно отношение. Параметр Where определяет условия, которым должны удовлетворять выводимые данные. В записи условий применяются знаки сравнения (=,> и т.д.), опции All, Any, Between, Exists, Like, In и логические операторы. Параметр Group by объединяет записи с одинаковым значением некоторого атрибута-ключа. Параметр Having при необходимости проверяет условия внутри группы записей, выделенных с помощью Group by. Параметр Order by определяет имена атрибутов, по которым должен быть отсортирован результат.

Ранее упомянутый запрос "Получить даты поставок из города Киева" выполняется командой

Select Дата

From Перевозка, Поставщик

Where Поставщик.Город="Киев" '

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

Изделие (513,"Динамо",800)

Изделие (155,"Динамо",600)

Изделие (247,"АТЭ",600)

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

Например, запрос "Получить список изделий с ценой 600" реализуется выражением goal (цель)

Goal: Изделие (х,_,600)

Ответ Пролога имеет вид

х=155

х=247.

Сетевая модель данных

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

В сетевой структуре при тех же основных понятиях (уровень, узел, связь) каждый элемент может быть связан с любым другим элементом.

На рис. 3.8 изображена сетевая структура базы данных в виде графа.

Примером сложной сетевой структуры может служить структура базы данных, содержащей сведения о студентах, участвующих в научно-исследовательских работах (НИРС). Возможно участие одного студента в нескольких НИРС, а также участие нескольких студентов в разработке одной НИРС. Графическое изображение описанной в примере сетевой структуры, состоящей только из двух типов записей, показано на рис. 3.9. Единственное отношение представляет собой связь между записями в обоих направлениях.

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

Веерным отношением W(R,S) называется пара отношений, состоящая из одного основного R, одного зависимого отноше­ния S и связи между ними при условии, что каждое значение зависимого отношения связано с единственным значением ос­новного отношения.

Названное условие является ограничением, характерным для сетевой модели данных в целом. Способ реализации этого огра­ничения в памяти ЭВМ неодинаков у различных сетевых СУБД.

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

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

Ограничение двухуровневых сетей состоит в том, что каж­дое отношение может существовать в одной из перечисленных ниже ролей:

• вне каких-либо веерных отношении,

• в качестве основного отношения в любом количестве ве­ерных отношений,

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

Запрещается существование отношения в качестве основ­ного в одном контексте и одновременно в качестве зависимо­го в другом контексте.

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

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

Для двухуровневых сетевых СУБД вводятся еще два огра­ничения (с теоретической точки зрения необязательные):

• первичный ключ основного отношения может быть толь­ко одно-атрибутным,

• веерное отношение существует, если первичный ключ ос­новного отношения является частью первичного ключа зависимого отношения.