Квантор существования

Целевой список и определяющее выражение

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

В предыдущем примере Назв_дет берется из строки и помешается в строку решения, если строка t удовлетворяет условию

t in r and t. Вес = 2.

Система просматривает строки отношения r одну за другой. Первой строке временно присваивается имя t и проверяется истинность определяющего выражения. Поскольку в этом случае t.Вес = 1, определяющее выражение, ложно, поэтому А — значение атрибута t.Hазв_дет в этой строке не помещается в отношение решения. Затем система переходит к следующей строке, дает ей имя t и снова проверяет истинность определяющего выражения. На этот раз выражение истинно, поэтому Д помещается в отношение решения. Процесс повторяется для каждой строки отношения r. В результате получается следующее отношение, идентичное полученному ранее:

Назв_дет

Д В

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

{t.Код_дет, t.Назв_дет, t.Вес ÷ t in r and t.Bec = 2}.

Рассмотрим еще один пример. Пусть даны отношения:

г - ИЗДЕЛИЕ 1 s -ИЗДЕЛИЕ 2

Код_дет	Назв_дет	Вес		Код_дет	Назв_дет	Вес
	А Д В C Е			Д С B K

Согласно алгебраическому выражению p_{Назв_дет}(r Ç s) реляционной алгебры, содержащему операции пересечения и проецирования, получим отношение:

Назв_дет
Д С В

В реляционном же исчислении, если t кортеж r, а у кортеж s, этот запрос может включать в себя следующие компоненты:

t.Назв_дет - целевой список;

t in r and у in s and t.Кoд_дет = у.Код_дет and t.Bec = у.Вес and t.Hазв_дет = у.Назв_дет — определяющее выражение.

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

Несколько иначе выглядят аналоги только двух операций реляционной алгебры — операций соединения и деления. Для построения аналогов этих операций требуются кванторы: квантор существования для соединения и квантор всеобщности для деления.

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

Рассмотрим отношения:

ПОТРЕБНОСТИ СКЛАД

Код_дет	Назв_дет	Количество		Код_дет	Стеллаж	Кол_дет
	А Д В С Е

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

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

t.Назв_дет,

где t— строка из отношения ПОТРЕБНОСТИ.

Пусть s — строка отношения СКЛАД.

Формирование определяющего выражения осуществляется, исходя из следующего. Для того чтобы деталь вошла в отношение решения, должно удовлетворяться условие, что на складе эта деталь имеется в достаточном количестве. Другими словами, если Код_дет встречается в строке отношения СКЛАД с Кол_дет > Количество в строке отношения ПОТРЕБНОСТИ, то эта деталь должна быть включена в решение. Таким образом, условие таково: существует хотя бы одна строка в отношении СКЛАД, содержащая требуемый Код_дет и где s.Кол_дет > t.Количество. Это формируется следующим образом:

exists s in СКЛАД

(s.Код_дет = t.Код_дет and s.Кол дет > t.Количество).

Такое выражение читается: "Существует строка s в отношении СКЛАД такая, что s.Код_дет = t.Код_дет и s. Код_дет > t.Количество".

Приведенное выражение определяет строку t. Если оно истинно, то есть для строки t существует такая строка s, то t.Hазв_дет помещается в результирующее отношение. Если выражение ложно — то есть такой строки s не существует — тогда t.Назв_дет не помещается в результирующее отношение.

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

{t.Назв_дет ÷ t in ПОТРЕБНОСТИ and exists s in СКЛАД (s.Код_дет = t.Код_дет and s.Кол_дет > t.Количество)}.

Оно описывает отношение, состоящее из одного столбца и содержащее названия деталей, взятых из строк отношения ПОТРЕБНОСТИ. Данное название помещается в отношение решения, если его строка t удовлетворяет условию после знака "÷".

Рассмотрим подробнее вышеописанный механизм обработки нескольких строк отношения ПОТРЕБНОСТИ, чтобы понять, как будет применяться условие.

Первая строка отношения ПОТРЕБНОСТИ (которая обозначена t) имеет Назв_дет = А, и оно будет помещено в результирующее отношение, если в отношении СКЛАД существует строка, в которой Код_дет = ‘01’, а Кол_дет > t.Количество. Такая строка действительно существует, и она обозначена как s. Итак, t удовлетворяет определяющему условию, поэтому t.Hазв_дет помещается в отношение решения. Этот процесс должен повториться для каждой строки отношения ПОТРЕБНОСТИ. Когда закончена обработка первой строки, вторая строка обозначена t, и теперь уже для нее ищется соответствующая строка s в отношении СКЛАД. Такой строки не существует, поэтому Д не помещается в результирующее отношение. Продолжая дальше обработку строк отношений по указанному алгоритму, получим множество решения, которое составит новое отношение, и будет выглядеть следующим образом:

Назв_дет

A В

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

Дата добавления: 2014-01-20