ЛЕКЦИЯ 5. 6.Реляционное исчисление
В выражениях реляционной алгебры всегда явно задается некий порядок, а также подразумевается некая стратегия вычисления запроса. В реляционном исчислении не существует никакого описания процедуры вычисления запроса, поскольку в запросе реляционного исчисления указывается, что, а не какследует извлечь.
Реляционное исчисление связано с той частью символьной логики, которая называется исчислениемпредикатов. В контексте баз данных оно существует в двух формах: в форме предложенного Коддом реляционногоисчислениякортежейи в форме предложенного Лакруа и Пиро реляционногоисчислениядоменов.
В логике первого порядка (или теории исчисления предикатов) под предикатомподразумевается истинностная функция с параметрами. После подстановки значений вместо параметров функция становится выражением, называемым суждением, которое может быть истинным или ложным. Например, предложения "Иванов является сотрудником данной организации" и "Иванов имеет более высокую зарплату, чем Петрова" являются суждениями, поскольку можно определить их истинность или ложность. В первом случае функция "является сотрудником данной организации" имеет один параметр ("Иванов"), а во втором случае функция "имеет более высокую зарплату, чем" имеет два параметра ("Иванов" и "Петрова").
Если предикат содержит переменную, например в виде "х является сотрудником этой организации", то у этой переменной должна быть соответствующая область определения. При подстановке вместо переменной х одних значений из ее области определения данное суждение может оказаться истинным, а при подстановке других — ложным. Например, если областью определения являются все люди и мы подставим вместо переменной х значение "Иванов", то суждение "Иванов является сотрудником данной организации" будет истинным. Если же вместо переменной х подставить имя другого человека, который не является сотрудником данной организации, то суждение станет ложным.
Если Р — предикат, то множество всех значений переменной х, при которых суждение Р становится истинным, можно символически записать следующим образом:
{х|Р(х)}
Предикаты могут соединяться с помощью логических операций AND), v (OR) и
(NOT) с образованием составных предикатов.
6.1.Реляционное исчисление кортежей
В реляционном исчислении кортежей задача состоит в нахождении таких кортежей, для которых предикат является истинным. Это исчисление основано на переменныхкортежа. Переменными кортежа являются такие переменные, областью определения которых служит указанное отношение. Таковыми являются переменные, для которых допустимыми значениями могут быть только кортежи данного отношения. (Понятие "область определения" в данном случае относится не к используемому диапазону значений, а к домену, в котором определены эти значения.)
Например, для указания отношения 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}
6.1.1.Кванторы существования и общности
Для указания количества экземпляров, к которым должен быть применен предикат, в формулах могут использоваться два типа кванторов. Кванторсуще- ствования(, или так называемый символ "существует", используется в фор-муле, которая должна быть истинной хотя бы для одного экземпляра, например:
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| ) }
6.1.2.Выражения и формулы
Аналогично тому, как не все возможные последовательности букв алфавита образуют правильно построенные слова, так и в реляционном исчислении не каждая последовательность формул является допустимой. Допустимыми формулами могут быть только недвусмысленные и небессмысленные последовательности. Выражение в реляционном исчислении кортежей имеет следующую общую форму:
{S1.а1, S2.а2, . . . , Sп.ап | F (S1/ S2, . . . , Sm) } ; m n
Здесь S1 S2, . . . , Sm— переменные кортежа, ai— атрибуты отношения, в котором определено значение переменной S1, а F — формула
Формула (таковой считается только правильно построенная формула) состоит из одного или нескольких элементарных выражений, которые могут иметь одну из следующих форм.
• R (Si), где Si — переменная кортежа, а R — отношение.
• Si.а1 Sj.а2, где Si и Sj — переменные кортежа, а1 — атрибут отношения, в котором определено значение переменной Si., а2 — атрибут отношения, в котором определено значение переменной Sj, и — одна из операций сравнения (<, <, >, >, =, #); атрибуты а1и а2 должны иметь области определения, для сравнения элементов которых применение знака операции является допустимым.
• Si.а1 с, где Si — переменная кортежа, а1 — атрибут отношения, в котором определено значение переменной 3;, с — константа из области определения атрибута а1 и — одна из операций сравнения.
Формулы рекурсивно строятся из элементарных выражений на основе следующих правил.
• Любое элементарное выражение рассматривается как формула.
• Если выражения 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 (а при использовании операции объединения достаточно присутствие кортежа только в одном из отношений). К тому же, если бы применялась лишь одна свободная переменная, то она относилась бы только к одному отношению, и поэтому кортежи второго отношения были бы исключены из рассмотрения. Операции разности и пересечения вполне могут быть представлены в данной версии реляционного исчисления кортежей.
6.1.3.Безопасность выражений
Прежде чем завершить этот раздел, отметим, что выражение реляционного исчисления может генерировать бесконечную последовательность кортежей. Например, таковым является следующее выражение, которое обозначает все кортежи, не принадлежащие к отношению Staff:
{S|
Staff (S) }
Выражения такого рода принято называть опасными. Для того чтобы избежать возникновения этой проблемы, необходимо ввести ограничение, согласно которому все значения, присутствующие в полученных результатах, должны принадлежать к области определения исходного выражения E; для этого служит обозначение dom(Е). Областью определения выражения Е являются все значения, явно присутствующие в Е или в одном или нескольких отношениях, имена которых упоминаются в выражении Е. В данном примере областью определения выражения являются все значения, представленные в отношении Staff.
Выражение является безопасным, если все значения, присутствующие в полученных результатах, принадлежат к области определения самого выражения. Приведенное выше выражение является опасным, поскольку в нем предусмотрено получение кортежей, не принадлежащих к отношению Staff (т.е. кортежей, находящихся за пределами области определения отношения). Все прочие примеры выражений реляционного исчисления кортежей, приведенные в настоящей главе, являются безопасными. Для предотвращения возникновения этой проблемы можно применить переменные области определения, заданные с помощью отдельной операции RANGE.
6.2. Реляционное исчисление доменов
В реляционном исчислении кортежей используются переменные, областью определения которых являются кортежи в отношении. С другой стороны, в реляционном исчислении доменов также используются переменные, но их значения берутся из области определения атрибутов, а не из кортежей отношения, Любое выражение в реляционном исчислении имеет следующую общую форму:
{d1 , d2 , ..... , dm | F( d1, d2, . . . , dm) }; m n
Здесь d1 , d2 , ..... , dm — переменные области определения (домена), а F( d1, d2, . . . , dm) — формула.
Формула состоит из одного или нескольких элементарных выражений, которые могут иметь одну из следующих форм.
R( d1, d2, . . . , dn) , где R — отношение степени пи dn — переменная домена.
d1 d2 где d1 и d2 — переменные домена и — одна из операций сравнения (<, <, >, >, =, #); переменные d1 и d2 должны иметь области определения, для сравнения элементов которых применение операции является допустимым.
d1 с, где d1 — переменная домена, с — константа из области определения переменной домена d1 и — одна из операций сравнения.
Формулы рекурсивно строятся из элементарных выражений на основе сле-дующих правил.
• Любое элементарное выражение рассматривается как формула.
• Если выражения F1 и F2 являются формулами, то выражения, полученные в результате их конъюнкции (F1 F2), дизъюнкции (F1 F2) и отрицания (
F1), также являются формулами.
• Если выражение F является формулой со свободной переменной X, то выражения (Х) (F) и (Х) (F) также являются формулами.
Выбрать именавсехменеджеров, зарплатакоторыхпревышает 25000 фунтовстерлингов.
{fn,ln | (sn, роsn, seх, sal, bN) (Staff(sn, fn, ln, posn, sal, bN) posn = 'Маnager' sal > 25000)}
Можно увидеть, что каждому атрибуту присвоено имя (переменной). Условие Staff(sn, fn, ln, posn, sal, bN) гарантирует, что переменные домена будут ограничены атрибутами того же самого кортежа. Поэтому мы можем использовать формулу posn = 'Маnager' вместо формулы Staff.position = 'Маnager'. В реляционном исчислении доменов переменная posn ссылается на одно из значений в домене и на нее не налагаются ограничения до тех пор, пока она не появится в субформуле, такой как Staff(sn, fn, ln, posn, sal, bN), после чего ее значения ограничиваются значениями position, которые присутствуют в отношении Staff.
Реляционное исчисление доменов является основой большинства языков запросов, основанных на использовании форм. В частности, на этом исчислении базировался известный язык Query-by-Example, который был первым (и наиболее интересным) языком в семействе языков, основанных на табличных формах.
|
Скачать 1.07 Mb.