8.1.2. Реляционное исчисление кортежей.

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

Например, для указания отношения Readers в качестве области определения пере­менной кортежа R используется следующая форма записи:

RANGE OF R IS Readers

Кроме того, запрос "найти множество всех кортежей R, для которых P(R) является истинным" можно записать следующим образом:

(R | P(R))

Здесь предикат Р называется формулой, (в математической логике, правильно по­строенной формулой — well-formed formula, wff). Например, запрос "выбрать атри­буты Code, FamilyNamе, Name, Patronymic, ReaderCardNumber, Position, PasportCode, Job и Post для всех читателей, которые имеют фамилию ‘Иванов’" можно записать следующим образом:

RANGE OF R IS Readers

{R | R.FamilyNamе = ‘Иванов’}

Здесь выражение R.FamilyNamе означает значение атрибута из отношения Readers для кортежа R. Для выборки одного определенного атрибута (например, FamilyNamе), можно сформулировать этот запрос иначе:

RANGE OF R IS Readers

{ R.FamilyNamе | R.FamilyNamе = ‘Иванов’}

Для указания количества экземпляров, к которым должен быть применен преди­кат, в формулах могут использоваться два типа кванторов. Квантор существования ( ), или так называемый символ "существует", используется в формуле, которая должна быть истинной хотя бы для одного экземпляра, например:

RANGE OF PD IS PasportData

PD (PD.Code = R.PasportCode ^ PD.Birthday = ‘13.11.1970')

Эта формула означает, что в отношении PasportData существует кортеж, который имеет такое же значение атрибута Code, что и значение атрибута PasportCode в текущем кортеже R из отношения Readers, и атрибут Birthday из кортежа PD имеет значение '13.11.1970'. Квантор общности ( ), или так называемый символ "для всех", используется в выражениях, которые относятся ко всем экземплярам, например:

R (R.FamilyNamе ~= 'Петров')

Эта формула означает, что во всех кортежах отношения Readers значение атрибута FamilyNamе не равно 'Петров'. Если правила эквивалентности применить в отношении логи­ческих операций, то ее можно переписать следующим образом:

~ R (R.FamilyNamе = 'Петров')

В таком виде она означает, что читатель по фамилии Петров в библиотеке не зарегистрирован.

Переменные кортежа называются свободными переменными, если они не квали­фицируются кванторами или , в противном случае они называются связанными переменными. Аналогично тому, как не все возможные последовательности букв ал­фавита образуют правильно построенные слова, так и в реляционном исчислении не каждая последовательность формул является допустимой. Допустимыми формулами могут быть только недвусмысленные и небессмысленные последовательности. Фор­мула (или правильно построенная формула) в исчислении предикатов определяется следующими правилами.

• Если Р является n-арной формулой (предикатом с п аргументами), а t₁,t₂,...,t_n— это константы или переменные, то выражение P(t_l,t₂,..., t_n) является правильно построенной формулой.

• Если t₁ и t₂ являются константами или переменными из одного домена, а представляет собой один из операторов сравнения (<, <=, >, >=, = или ~=), то выражение t₁ t₂ является правильно построенной формулой.

• Если выражения F₁ и F₂ являются формулами, то их конъюнкция обозна­чается как F₁  F₂, дизъюнкция — как F₁  F₂, а отрицание — как ~F₁.

• Если выражение F₁ является формулой со свободной переменной X, то выражения F(X) и F(X) также являются формулами.

ПРИМЕР

Создайте список всех читателей, у которых номер читательского билета больше 100.

RANGE OF R IS Readers

(R.FamilyNamе, R.Name, R.Patronymic, R.ReaderCardNumber | R.ReaderCardNumber >100)

Создайте список всех сотрудников, которые родились после 1960 года.

RANGE OF L IS Librarians

RANGE OF PD IS PasportData

{L | L(L. PasportCode = PD.Code  PD. Birthday > 31.12.1960)}

Атрибут Code в отношении PasportData содержит код паспорта того сотрудника, который родился после 1960 года. Этот запрос можно сформулировать иначе: "Для всех сотрудников, данные о которых нужно привести в списке, в отношении PaspоrtData имеются кортежи, соответствующие этим сотрудникам, причем значение атрибута Birthday в каждом таком кортеже больше 31.12.1960".

Обратите внимание, что в такой формулировке запроса нет никакого указания стратегии выполнения запроса — СУБД предоставляется свобода выбора операций для выполнения данного задания, а также порядка выполнения этих операций. Эквивалентная формулировка этого запроса в реляционной алгебре будет выглядеть так: "Выбрать такие кортежи отношения PaspоrtData, в которых значение атрибута Birthday больше 31.12.1960, и выполнить их объединение с отношением Librarians". Как видите, здесь порядок выполнения операций задается неявно, но вполне однозначно.

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

{R | ~ (R  Readers)}

Это выражение означает набор кортежей, которые не входят в отношение Readers. Выражения подобного типа называются опасными. Чтобы избежать их возникновения, следует добавить ограничение, требующее, чтобы все результирующие значения входили в область определения формулы. Например, областью определения приведенной выше формулы является множество всех значений, которые представлены в отношении Readers. Более подробную информацию по этому вопросу заинтересованный студент найдет в работе Ульмана (Ullman, 1988).