Реляционная алгебра

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

Объединением (R1 UNION R2) двух совместимых отношений R1 R2 одинаковой размерности является отношение R, содержащее все элементы исходных отношений (с исключением повторений).

Вычитание (R1 MINUS R2) совместимых отношений R1, R2 одинаковой размерности есть отношение, тело которого состоит из множества кортежей, принадлежащих R1, но не принадлежащих R2.

Пересечение (R1 INTERSECT R2) двух совместимых отношений R1, R2 одинаковой размерности порождает отношение R с телом, включающим в себя кортежи, одновременно принадлежащие обоим исходным отношениям.

Произведение (R1 TIMES R2) отношения R1 степени к1 и отношения R2 степени к2, которые не имеют одинаковых имен атрибутов, есть такое отношение R степени к1+к2, заголовок которого представляет сцепление заголовков отношений R1 и R2, а тело – имеет кортежи такие, что первые к1 элементов кортежей принадлежат множеству R1, а последние к2 элементов – множеству R2.

Выборка (R WHERE f) отношения R по формуле выборки f представляет собой новое отношение с таким же заголовком и телом, состоящим из таких кортежей отношения R, которые удовлетворяют истинности логического выражения, заданного формулой f.

Проекция (A[X, Y, …, Z]) отношения А на атрибуты X, Y, …, Z, где множество {X, Y, …, Z} является подмножеством полного списка атрибутов заголовка отношения А, представляет собой отношение с заголовком X, Y, …, Z и телом, содержащим соответствующие атрибутам X, Y, …, Z части кортежей отношения А, за исключением повторяющихся вновь образованных кортежей. Повторение одинаковых атрибутов в списке X, Y, …, Z запрещается.

Деление (R1 DIVIDEBY R2) отношения R1 с атрибутами А и В на отношение R2 с атрибутами В, где А и В простые или составные атрибуты, причем атрибут В определен на одном и том же домене (множестве доменов составного атрибута), дает отношение R с заголовком А и телом, состоящим из кортежей r таких, что в отношении R1 имеются кортежи (r, s),

 

 

 

Рис.4.3. Семантическая модель отношений " самолета" и " птицы"

 

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

сетей, исключая нереальные или практически бессмысленные ситуации.

С помощью семантической сети легко создать базу знаний, в том числе базу правил. Пример:

1. Если атрибут = клюв, то объект = птица.

2. Если атрибут = крылья,

то объект = птица или объект = самолет.

3. Если атрибут = сокол или атрибут = орел,

то объект = птица.

4. Если атрибут = оперение и атрибут = крылья и

атрибут = клюв, то объект = птица.

5. Если объект = птица, то атрибут = оперение и т. д.

По видам отношений между объектами семантические сети бывают однородные (с единственным типом отношений, например " цвет") и неоднородные (с различными типами отношений), бинарные (отношения связывают два объекта) и N-нарные (отношения связывают более двух объектов).

Наиболее часто в семантических сетях используются следующие отношения (связи):

- " часть-целое" (" класс – подкласс", " элемент – множество" …);

- функциональные (" производит", " влияет" …);

- количественные (больше, меньше…);

- пространственные (далеко, близко…);

- временные (раньше, позже…);

- атрибутивные (иметь свойство, иметь значение…);

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

Индексирование может быть одноуровневым и двухуровневым. При одноуровневой схеме в индексе хранятся короткие записи, имеющие два поля: поле содержимого старшего ключа (возможно, хеш-кода ключа) адресуемого блока и поле адреса начала этого блока. В каждом блоке записи располагаются в порядке возрастания значения ключа или свертки. Старшим ключом каждого блока является ключ последней записи – рис. 8.2.

 

 

Рис. 8.2. Одноуровневая схема индексации

 

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

При двухуровневой схеме ключи (свертки) отделены от содержимого записей – рис. 8.3.

 

Рис.8.3. Двухуровневая схема индексации

 

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

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