Курс «Базы данных»

КУРС «Базы данных» *** Тема «Реляционное исчисление»

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

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

Рассмотрим запрос: "Выбрать номера поставщиков и названия городов, в которых находятся поставщики детали с номером Р2".

Алгебраическая версия ■ Выполнить соединение отношений поставщиков и поставок SP по атрибуту S#. ■ С помощью операции сокращения выделить из результатов этого соединения кортежи, которые относятся к детали с номером Р2. ■ Сформировать проекцию результатов этой операции сокращения по атрибутам S# И CITY. Этот же запрос в терминах реляционного исчисления формулируется приблизительно следующим образом. ■ Получить атрибуты S# и CITY для таких поставщиков, для которых в отношении SP существует запись о поставке с тем же значением атрибута S# и со значением атрибута Р#. равным Р2.

Запрос в терминах реляционного исчисления ■ Получить атрибуты S# и CITY для таких поставщиков, для которых в отношении SP существует запись о поставке с тем же значением атрибута S# и со значением атрибута Р#, равным Р2.

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

Реляционное исчисление основано на разделе математической логики, который на­зывается исчислением предикатов.

Язык, основанный на реляционном исчислении QUEL, был реализован и некоторое время серьезно конкурировал с языком SQL.

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

Запрос "Получить номера поставщиков, находящихся в Лондоне" может быть представлен на языке QUEL следующим образом. Переменной области значений здесь является переменная SX, которая принимает значения из отношения S (RANGE — оператор определения переменной области значений). retrieve означает следующее: "Для каждого возможного значе­ния переменной SX выбирать компонент S# этого значения тогда и только тогда, когда компонентом CITY этого значения является London

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

Впоследствии предложили апьтернативную версию исчисления, называемую исчислением доменов, в которой переменные области значений принимают значения из доменов, т. е. являются переменными, изменяемыми на доменах, а не на отношениях. Наиболее языком, является QBE (Query-By-Example — язык запросов по образцу). (QBE является смешанным, поскольку в нем присутствуют и эле­менты исчисления кортежей).

Кванторы Термин "квантор" происходит от латинского слова "quantum", которое, вообще говоря, означает "количество". Вместо ключевых слов EXISTS и FORALL, соответственно, часто используются символы ("обратное Е") и ("перевернутое А").

Квантор EXISTS является квантором существования, a forall — квантором всеобщности.

EXISTS V ( р ) Существует по меньшей мере одно значение переменной V, при котором формула р становится истинной. FORALL V ( р ) Формула р является истинной при всех значениях переменной V.

В текущем значении переменной отношения SP существует кортеж SPX, такой, что значение атрибута S# в этом кортеже равно значению атрибута SX.S#, а значение атрибута Р# в кортеже SPX равно Р2.

Каждая ссылка на переменную области значений является либо свободной, либо связанной. Каждая ссылка на переменную SPX в этом примере является связанной. Единствен­ная ссылка на переменную SX свободна.

Для всех кортежей РХ в текущем значении переменной отношения Р, значение атрибута COLOR в кортеже РХ равно Red. Обе ссылки на переменную РХ в этом примере связаны.

Правильно построенная формула, в которой все пере­менные связаны, называется закрытой правильно построенной формулой. Открытая пра­вильно построенная формула— это такая формула, которая содержит по крайней мере одну ссылку на свободную переменную.

Реляционные операции Получить имена поставщиков детали с номером Р2: Здесь все ссылки на переменную SX являются свободными, тогда как все ссылки на переменную SPX (в конструкции WHERE) являются связанными, как и должно быть, по­скольку на них нет ссылок в кортеже-прототипе.

Определить номера поставщиков из Парижа со статусом, большим 20

Найти все пары номеров таких поставщиков, которые находятся в одном городе (повторение примера 7.5.5) Конструкции AS в кортеже-прототипе используются для при­сваивания имен атрибутам результата. Следовательно, эти имена недоступны для ис­пользования в конструкции WHERE, и потому вторая операция сравнения в конструкции where записана как sx. s# < SY. S#. а не в виде SA < SB.

Реляционный язык может быть основан как на реля­ционной алгебре, так и на реляционном исчислении. Что же лежит в основе языка SQL? Ответом будет "частично и то. и другое, а частично ни тo, ни другое...".

ИСЧИСЛЕНИЕ ДОМЕНОВ Исчисление доменов отличается от исчисления кор­тежей тем, что в нем переменные области значений определены на доменах (типах), а не на отношениях.

Это выражение является условием принадлежности, которое принимает значение true тогда и только тогда, когда обнаруживается, что существует кор­теж с данными о поставке, в котором значение S# равно S1, а значение Р# равно Р1. Условие принадлежности принимает значение true тогда и только тогда, когда обнаруживается, что в настоящее время существует кортеж с данными о поставке, в котором значение атрибута S# равно текущему значению переменной области значений SX, а значе­ние атрибута P# равно текущему значению переменной домена РХ.

Определить номера поставщиков из Парижа со статусом больше 20

Найти все такие пары номеров поставщиков, в которых два поставщика находятся в одном городе

Одним из наиболее широко известных примеров языка, основанного на исчислении доменов, является язык запросов по образцу (Query-By-Example — QBE)

Синтаксис QBE является очень привлекательным и простым для интуитивного восприятия: он основан на идее внесения записей в пустые таб­лицы.

Определить имена поставщиков, которые поставляют, по меньшей мере, одну деталь, поставляемую поставщиком S2, может выглядеть примерно следующим образом.

Пользователь запрашивает систему предоставить ему ("Р." — сокращение от present) имена поставщиков ( _NX ), такие, что если постав­щик имеет номер _SX, то поставщик _SX поставляет некоторую деталь _РХ, а эта деталь _РХ, в свою очередь, поставляется поставщиком S2.

Возможно также ввести запись "Р." применительно ко всей строке, например, как показано ниже. Этот пример эквивалентен следующему, в котором запись "Р." присутствует в каж­дой позиции столбца в строке. Из данного примера следует еще один вывод: в системе должны быть предусмотрены средства, позволяющие редактировать на экране пустые таблицы, добавляя и удаляя столбцы и строки, а также расширяя и сужая столбцы.