Введение. Исчисление предикатов первого порядка, исчисление кортежей, кортежная переменная, оператор RANGE, правильно построенная формула (Well-Formed Formula

Ключевые слова

Исчисление предикатов первого порядка, исчисление кортежей, кортежная переменная, оператор RANGE, правильно построенная формула (Well-Formed Formula, WFF), операция импликации, метод вложенных циклов (nested loops join), квантор существования (EXISTS), квантор всеобщности (FORALL), свободная переменная, связанная переменная, числовые функции на множествами, целевой список (target list), выражением исчисления кортежей, исчисление доменов, условие членства, предикат членства, выражение исчисления доменов, язык запросов Query-by-Example.

Предположим, что мы работаем с базой данных, которая состоит из отношений СЛУЖАЩИЕ{СЛУ_НОМ, СЛУ_ИМЯ, СЛУ_ЗАРП, ПРО_НОМ} и ПРОЕКТЫ{ПРО_НОМ, ПРОЕКТ_РУК, ПРО_ЗАРП}, и хотим узнать имена и номера служащих, являющихся начальниками отделов со средней заработной платой, большей 11500 руб.

Если бы для формулировки такого запроса использовалась реляционная алгебра, то мы получили бы, например, следующее алгебраическое выражение:

(СЛУЖАЩИЕ JOIN ПРОЕКТЫ
WHERE (СЛУ_НОМ= ПРОЕКТ_РУК AND ПРО_ЗАРП> 11500))
PROJECT (СЛУ_ИМЯ, СЛУ_НОМ).

Это выражение можно было бы прочитать, например, следующим образом:

· выполнить эквисоединение отношений СЛУЖАЩИЕ и ОТДЕЛЫ по условию СЛУ_НОМ = ПРОЕКТ_РУК;

· ограничить полученное отношение по условию ПРО_ЗАРП> 11500;

· спроецировать результат предыдущей операции на атрибут СЛУ_ИМЯ, СЛУ_НОМ.

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

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

RANGE СЛУЖАЩИЙIS СЛУЖАЩИЕ и

RANGE ПРОЕКТ IS ПРОЕКТЫ и

и выражение

СЛУЖАЩИЙ.СЛУ_ИМЯ, СЛУЖАЩИЙ.СЛУ _НОМ
WHERE EXISTS (СЛУЖАЩИЙ.СОТР_НОМ = ПРОЕКТ.ПРОЕКТ_РУК
AND ПРОЕКТ.ПРО_ЗАРП> 11500).

Это выражение можно было бы прочитать, например, следующим образом: выдать значения СЛУ_ИМЯ и СЛУ_НОМ для каждого кортежа сотрудников такого, что существует кортеж проектов со значением ПРОЕКТ_РУК, совпадающим со значением СЛУ_НОМ этого кортежа сотрудников, и значением ПРО_ЗАРП, большим 11500.

Во второй формулировке мы указали лишь характеристики результирующего отношения, но ничего не сказали о способе его формирования. В этом случае система должна сама решить, какие операции, и в каком порядке нужно выполнить над отношениями СЛУЖАЩИЕ и ОТДЕЛЫ. Обычно говорят, что алгебраическая формулировка является процедурной, т.е. задающей последовательность действий для выполнения запроса, а логическая – описательной (или декларативной), поскольку она всего лишь описывает свойства желаемого результата. Как мы указывали в начале Лекции 3, на самом деле эти два механизма эквивалентны, и существуют не очень сложные правила преобразования одного формализма в другой.

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

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

Как и в разделах, посвященных реляционной алгебре, в этом разделе нам не удастся избежать использования некоторого конкретного синтаксиса, который мы, тем не менее, формально определять не будем. Необходимые синтаксические конструкции будут вводиться по мере необходимости. В совокупности, используемый синтаксис близок, но не полностью совпадает с синтаксисом языка баз данных QUEL, который долгое время являлся основным языком известной реляционной СУБД Ingres.

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