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

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

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

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

{S|Р(S)}

Здесь предикат Р называется формулой (в математической логике, правильно построенной формулой — We11-Formed Fоrmula, или сокращенно WFF). Напри­мер, запрос "выбрать атрибуты staffNo,fName,lName, роsition, sex, Sа1агу и BranchNo для всех сотрудников, которые получают зарплату больше 10 000 фунтов стерлингов" можно записать следующим образом:

{S|Staff(S) and S.salary > 10000}

Здесь выражение S.sа1аry означает значение атрибута salary для кортежа S. Для выборки одного определенного атрибута (например, salary), можно. сформулировать этот запрос иначе:

{S.sа1аrу|Staff(S) Ù S.sаlагу > 10000}

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

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

Staff(S) Ù ($В) (Вгаnch(В) Ù (В.branchNo=S.branchNo) Ù B.city='London|)

Это выражение означает, что в отношении Вгаnch существует кортеж, кото- рый имеет такое же значение атрибута branchNo, что и значение атрибута branchNo в текущем кортеже S из отношения Staff, а атрибут city из кортежа S имеет значение 'London'. Квантор общности ("), или так называемый символ "для всех", используется в выражениях, которые относятся ко всем экземп-лярам, например:

("В) (В.city#'Раris')

Это выражение означает, что ни в одном кортеже отношения Вгаnch значе-

ние атрибута city не равно 'Раris'.

Приведенную выше формулу можно представить следующим образом:

~($В) (В.city ='Раris')

В таком виде она означает, что в Париже нет отделений компании. Переменные кортежа называются свободными переменными, если они не ква- нтифицируются кванторами " или $; в противном случае они называются связанными переменными. В выражении, составленном по правилам реляционного исчисления, свободные переменные могут находиться только слева от знака верти­кальной черты (|). Например, в следующем запросе единственной свободной пере­менной является S и в процессе вычисления этого выражения последовательно происходит связывание переменной S с каждым кортежем отношения Staff.

{S.fName, S.lName | Staff (S) Ù ($В) (Вгаnch(В) Ù (В.branchNo =S.branchNo) Ù B.city='London|) }

Выражения и формулы

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

{S₁.а₁, S₂.а₂,..., S_п.а_п | F (S_1/ S₂,..., S_m) }; m ³ n

Здесь S₁ S₂,..., S_m— переменные кортежа, a_i— атрибуты отношения, в котором определено значение переменной S1, а F — формула

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

• R (Si), где Si — переменная кортежа, а R — отношение.

• S_i.а₁ q S_j.а₂, где S_i и S_j — переменные кортежа, а1 — атрибут отношения, в котором определено значение переменной S_i., а2 — атрибут отношения, в кото­ром определено значение переменной S_j, и q — одна из операций сравнения (<, <, >, >, =, #); атрибуты а₁и а2 должны иметь области определения, для сравне­ния элементов которых применение знака операции q является допустимым.

• S_i.а₁ q с, где S_i — переменная кортежа, а₁ — атрибут отношения, в кото­ром определено значение переменной 3;, с — константа из области опреде­ления атрибута а₁ и q — одна из операций сравнения.

Формулы рекурсивно строятся из элементарных выражений на основе сле­дующих правил.

• Любое элементарное выражение рассматривается как формула.

• Если выражения F1 и F2 являются формулами, то выражения, полученные в результате их конъюнкции (F1 Ù F2), дизъюнкции (F1 Ú F2) и отрицания (~F1), также являются формулами.

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

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

А. Создайте список всех менеджеров, зарплата которых превышает 25000 фунтов стерлингов.

{S.fName, S.lName | Staff(S) Ù S.position= ' Маnаger ' Ù S.sа1аrу>25000}

Б. Создайте список всех сотрудников, которые отвечают за работу с объектами недвижимости в Глазго,

{S |Staff(S)Ù($Р) (РrорегtyForRent (Р) Ù (Р.staffNo=S.staffNo) Ù Р. city= 'G1аsgow') }

Атрибут staffNo в отношении РгорегtуForRent содержит табельный номер cотрудника, который отвечает за работу с данным объектом недвижимости, запрос можно сформулировать иначе: "Для всех сотрудников, данные о ко-нужно привести в списке, в отношении РrорегtуForRent имеются кортежи, соответствующие этим сотрудникам, причем значение атрибута city в каждом таком кортеже равно “ G1аsgow".

В такой формулировке запроса нет никакого указания на стратегию выполнения запроса — СУБД предоставляется свобода выбора операций для выполнения данного задания, а также порядка выполнения этих операций. Эквивалентная формулировка данного запроса в реляционной алгебре бу-выглядеть так: "Выбрать такие кортежи отношения PropertyForRent, в которых значение атрибута city равно 'G1аsgow', и выполнить их объединение с отношением Staff ". Как видите, здесь порядок выполнения операций задается шо, но вполне однозначно.

 

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

Для представления этого запроса средствами реляционной алгебры применялась операция объединения. Но, к сожалению, данный запрос не может представлен в той версии реляционного исчисления, которая рассматривается в настоящем разделе. Например, если бы было создано выражение реляци­онного исчисления кортежей с двумя свободными переменными, то каждый кор­теж результата должен был бы соответствовать одному из кортежей и в отноше­нии Вrапсh, и в отношении РгорегtyFогRent (а при использовании операции объединения достаточно присутствие кортежа только в одном из отношений). К тому же, если бы применялась лишь одна свободная переменная, то она отно­силась бы только к одному отношению, и поэтому кортежи второго отношения были бы исключены из рассмотрения. Операции разности и пересечения вполне могут быть представлены в данной версии реляционного исчисления кортежей.

Безопасность выражений

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

{S|~Staff (S) }

Выражения такого рода принято называть опасными. Для того чтобы избе­жать возникновения этой проблемы, необходимо ввести ограничение, согласно которому все значения, присутствующие в полученных результатах, должны принадлежать к области определения исходного выражения E; для этого служит обозначение dom(Е). Областью определения выражения Е являются все значе­ния, явно присутствующие в Е или в одном или нескольких отношениях, имена которых упоминаются в выражении Е. В данном примере областью определения выражения являются все значения, представленные в отношении Staff.

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