Невыразимость транзитивного замыкания реляционными операторами

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

Пример 5.2. Рассмотрим отношение, описывающее сотрудников некоего предприятия. Отношение содержит данные о табельном номере сотрудника, фамилии, должности и табельном номере руководителя сотрудника – СОТРУДНИКИ (ТАБ_НОМ, ФАМИЛИЯ, ДОЛЖНОСТЬ, ТАБ_НОМ_РУК):

ТАБ_НОМ	ФАМИЛИЯ	ДОЛЖНОСТЬ	ТАБ_НОМ_РУК
	Иванов	Директор
	Петров	Глав.бухгалтер
	Сидоров	Бухгалтер
	Васильев	Начальник цеха
	Сухов	Мастер
	Шарипов	Рабочий

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

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

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

l либо кортеж ,

l либо найдется конечная последовательность элементов , такая, что все кортежи принадлежат отношению .

Очевидно, что .

Кросс-таблицы

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

ЛЕКЦИЯ 5.

Реляционное исчисление

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

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

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

Если предикат содержит переменную, например в виде "х является сотрудни­ком этой организации", то у этой переменной должна быть соответствующая область определения. При подстановке вместо переменной х одних значений из ее области определения данное суждение может оказаться истинным, а при подста­новке других — ложным. Например, если областью определения являются все люди и мы подставим вместо переменной х значение "Иванов", то суждение "Иванов является сотрудником данной организации" будет истинным. Если же вместо переменной х подставить имя другого человека, который не является сотрудником данной организации, то суждение станет ложным.

Если Р — предикат, то множество всех значений переменной х, при которых су­ждение Р становится истинным, можно символически записать следующим образом:

{х|Р(х)}

Предикаты могут соединяться с помощью логических операций Ù (AND), v (OR) и ~ (NOT) с образованием составных предикатов.