Приведем грамматику для исчисления кортежей в форме Б.Н.Ф. квадратные скобки здесь указывают на компоненты, которые по умолчанию могут быть опущены.
Range-variable-definition
::=RANGE OF VARIABLE is range item-commalist
range-item
::= relation | expression
expression
::= (target-item-commalist)[WHERE wff]
target-item
::= variable | variable-attribute [AS attribute]
wff
::= condition
| NOT wff
|condition AND wff
|condition OR wff
|IF condition THEN wff
|EXISTS variable (wff)
|FORALL variable (wff)
|(wff)
Категория condition (условие) представляет или формулу wff заключенную в скобки, или простое скалярное сравнение типа comporant comporant. Здесь обозначает любой скалярный оператор сравнения и каждый comporant это либо скалярная константа, либо значение атрибута представленого с cсылкой на атрибут в форме переменая.атрибут. Категория wff представляет собой правильно построеную формулу (WFF formulated formulate).
Переменные и кортежи.
Переменные кортежи (или области значений) определяются следующим образом:
RANGE OF T IS X1,X2,….,Xn.
Здесь Т определяемая переменная кортежа, а Xi –(i=1…n) либо имя отношения, либо выражение исчисления кортежей. Пусть Xi является отношением Ri (i=1…n). Отношение R1,R2,…Rn. Должны быть совместимы по типу т.е. они должны иметь идентичные заголовки, тогда переменная кортежа изменяется на объединении этих отношений, т.е. её значение в любое заданное время будет некоторым текущим кортежем, по крайней мере одного из этих отношений.
Пр-р.
RANGE OF SX IS S;
RANGE OF SPX IS SP;
RANGE OF SY IS (SX) WHERE SX,CITY = ‘London’
(SX) WHERE (SPX,S# = SX,S# AND SPX,P# = ‘P1’)
Переменная кортежа SY может принимать значения из мн-ва кортежей S для поставщиков которые или размещаются в Лондоне, или поставляют деталь P1,или и то и другое.
Свободные и связанные переменные.
Каждый экземпляр кортежа в формуле WFF является или свободным, или связанным. Под экземпляром переменой кортежа в формуле WFF будем подразумевать наличие имени переменой в формуле WFF: а)в контексте ссылки атрибута Т.А. б)как переменный непосредственно следующий за одним из кванторов существования EXISTS или всеобщности FORALL. Приведем устанавливающее, каким будет данный экземпляр в переменной кортежа, свободным или связанным.
1)в простом сравнении типа Т.А.<U.A. все экземпляры свободны. 2) экземпляры в формулах WFF(f) и (NOT f) свободны или связаны, в зависимости от того свободны или связаны они в “f”. Экземпляры в формулах WFF типа: fandg”; “forg”; “iff THENG”. Свободны или связаны,в зависимости от того свободны или связаны они в “f” и “g” .
3) Экземпляры переменной Т которые свободны в формуле “f” связаны в формулах WFF следующим вида: “EXIXTS T (f) “; “FORALL T (f)”.
Другие экземпляры в формуле f свободны или связаны в таких формулах WFF в соответствии с тем, свободны или связаны в “f”.
SX.S# = “S1”; SX.S# = SPX.S#
Пр-ры логических формул WFF.
PX.WEIGHT<15 OR PX.WEIGHT >25
SX.S# = SPX.S# AND SPX.P# PX.P#
IF PX COLOR = ‘RED’ THEN PX.CITY =’London’.
Кванторы.
Существуют два квантора EXISTS (существует) и FORALL (для всех).Если “f” формула WFF в которой переменная X свободна, то EXISTS x(f) и FORALL x(f) являются допустимыми формулами WFF. Перваяформула означает: существует по крайней мере одно такое значение переменной x что вычисление формулы WFF f дает значение истина. Вторая формула означает: для всех значений переменной x вычисление формулы WFF f дает значение истина.
Пр-р разберем квантор существования EXISTS.
EXISTS SPX (SPX.S# = SX.S# AND SPX.P# = ‘P2’)
Эта формула WFF читается так: существует кортеж EXISTS отношение SP скажем SPX, для которого значение S# равняется какому-нибудь значению SX.S#, а значение P# равняется P2.
Каждый экземпляр SPX в этом примере связан, отдельный экземпляр SX свободен.
Квантор существования EXISTS определяется формально как повторяющийся OR(или). Другими словами если R это отношение с кортежами T1,T2,…Tm где Т переменная кортежа, которая изменяется на этом отношении, а f(T) это формула WFF в которой Т используется как свободная переменная, то формула WFF: EXISTS T (f(T)) определяется равносильно следующей формуле WFF: false OR(false OR(f(T1)OR f(T2)OR…..f(Tm)).
Заметим, что результатом вычисления этого выражения будет ложь если отношение R пусто.
Пр-р теперь разберём квантор общности FORALL
FORALL PX (PX.COLOR = ‘RED’)
Для всех кортежей отношение P скажем PX ,значение атрибута COLOR в этих кортежах равно RED.
Квантор существования FORALL определяется как повторяющееся AND. Другими словами если R,T и f(T), такиеже как рассматривалось раннее, то формула WFF будет следующего вида:
FORALL T (f(T)) равносильна следующей формуле WFF :
True AND (f(T1)ANDf(T2)AND…..ANDf(Tm)).
В частности если отношения R пустое то результатом вычисления этого выражения будет истина.
Выражения
Напомним что выражение исчисления кортежей имеет вид:
(target-item-commalist)[where f]. Остановимся вначале подробнее на первом элементе приведенной конструкции списке целевых элементов. Каждый целевой элемент списка является или именем простой переменной такой как Т или выражением вида T.A[AS X]. Здесь Т это переменная кортежа, А- атрибут сопоставляемого отношения, часть AS X может быть опущена, и тогда атрибут результата будет наследовать имя соответствующего сопоставляемого отношения.
Примеры выражений: SX.S#, SX.S# AS SN0, SX.S#, SX.CITY AS SCITY,PX.P#, PX.CITY AS PCITY.
Рассмотрим в общих чертах что случится при вычислении следующего выражения. Пусть переменные кортежей определенные в указанном списке целевых элементов будут T,U,…,V. Пусть отношения на которых изменяются переменные кортежа будут TR,UR,VR. Пусть результирующие атрибуты имеют имена (явно определенные или наследуемые) X1,X2,…,XR тогда 1) строится расширенное декартово произведение TR TIMES UR TIMES…TIMES VR.
2) кортежи которые не удовлетворяют формуле wff в фразе WHERE (если она есть) исключается из результата шага 1. 3) результат шага 2 проецируется по атрибутам X1,X2,…,XR
Примеры:
(SX.S#)WHERE SX.CITY=’London’ (SX.S#,SX.CITY) WHERE EXISTS SPX (SPX.S#=SX.S# AND SPX.P#=’P2’)
Примеры формулировок запросов:
Рассмотрим несколько примеров реляционного исчисления кортежей при формулировки запросов.
1.Получить все такие пары номеров поставщиков что 2 поставщика размещаются в одном городе
(SX.X# AS FIRSTS#, SY.Y# AS SECONDS#)
WHERE SX.CITY=SY.CITY AND SX.S#<SY.S#
