Реферат: Реляционное исчисление
Основным средством реляционного исчисления является понятие переменной кортежа (также называемой переменной области значений). Коротко говоря, переменная кортежа – это переменная, «изменяющаяся на» некотором заданном отношении, т.е. переменная, допустимыми значениями которой являются кортежи заданного отношения. Другими словами, если переменная кортежа V изменяется в пределах отношения r , то в любой заданный момент переменная V представляет некоторый кортеж t отношения r. Например, запрос «Получить номера поставщиков из числа тех, которые находятся в Лондоне» может быть выражен на языке QUEL так:
RANGE OF SX IS S;
RETRIEVE (SX.S#) WHERE SX.CITY = “London”;
Переменной кортежа здесь является переменная SX, которая изменяется на отношении, представляющем собой текущее значение переменной – отношения S (оператор RANGE – оператор определения этой переменной). Оператор RETRIEVE означает следующее: «Для каждого возможного значения переменной SX выбирать компонент S# этого значения тогда и только тогда, когда его компонент CITY имеет значение ‘London’».
В связи с тем, что реляционное исчисление основано на переменных кортежа, его первоначальную версию (для отличия от исчисления доменов, речь о котором пойдет ниже) называют также исчислением кортежей.
Замечание. Для удобства примем следующее соглашение: далее в этой книге термины исчисление и реляционное исчисление, приведенные без уточнения «кортежей» или «доменов», будут означать именно исчисление кортежей (там, где это играет какую-то роль).
В статье Лакруа (Lacroix) и Пиротте (Pirotte) предлагается альтернативная версия исчисления, называемая исчислением доменов, в которой переменные кортежа изменяются на доменах, т.е. являются переменными, изменяемыми на доменах, а не на отношениях. В литературе предлагается множество языков исчисления доменов. Наиболее известный из них – пожалуй, Query-By-Example, или QBE (в действительности он является смешанным, так как в языке QBE присутствуют и элементы исчисления кортежей). Существует несколько коммерческих реализаций этого языка.
2.Исчисление кортежей.
Сначала введем для реляционного исчисления конкретный синтаксис, взяв за образец (хотя умышленно не совсем точно) версию исчисления языка Titorial D, а затем перейдём к обсуждению семантики. В следующих ниже подразделах обсуждаются синтаксис и семантика.
2.1.Синтаксис.
Замечание. Многие из приведенных здесь синтаксических правил не будут поняты вам до тех пор, пока вы не изучите семантический материал, следующий далее. Однако мы все же решили собрать все правила вместе для удобства ссылок.
Начнем с повторения синтаксиса параметра <реляционное выражение>. < реляционное выражение>
:: = RELATION {<список выражений кортежей>}
| < имя переменной-отношения>
| < реляционная операция>
| < реляционное выражение>
Иными словами, синтаксис параметра <реляционное выражение > остается прежним, однако из наиболее важных его подпараметров, < реляционная операция >, теперь будет иметь совершенно иное определение.
<определение переменной кортежа>
:: = RANGEVAR <имя переменной кортежа >
RANGES OVER <список реляционных выражений >;
Параметр <имя переменной кортежа> может использоваться как <выражение кортежа>, однако, лишь в определенном контексте, а именно:
- перед точкой и последующим уточнением в параметре < ссылка на атрибут кортежа >;
- сразу после квантора в параметре < логическое выражение с квантором>;
- как операнд в параметре < логическое выражение >;
- как параметр < прототип кортежа > или как (операнд) подпараметр < выражение> в параметре < прототип кортежа >.
< ссылка на атрибут кортежа >
:: = <имя переменной кортежа>.<ссылка на атрибут>[ AS <имя атрибута>]
Параметр <ссылка на атрибут кортежа > может использоваться как параметр < выражение>, но только в определенном контексте, а именно:
- как операнд параметра <логическое выражение >;
- как параметр <прототип кортежа > или как (операнд) подпараметр <выражение> в параметре <прототип кортежа>.
< логическое выражение >
:: = … все обычные возможности вместе с:
| < логическое выражение с квантором>
Ссылки на переменные кортежей в значении параметра < логическое выражение > могут быть свободными в пределах этого параметра тогда и только тогда, когда выполнено два следующих условия.
- Параметр < логическое выражение> расположен непосредственно после параметра < реляционная операция> (т.е. параметр < логическое выражение > следует сразу за ключевым словом WHERE.).
- Ссылка (обязательно свободная) именно на эту переменную кортежа непосредственно присутствуют в значении параметра <прототип кортежа>, непосредственно содержащегося в том же выражении <реляционная операция>(т.е. параметр <прототип кортежа> располагается непосредственно перед ключевым словом WHERE).
Замечание по терминологии. В контексте реляционного исчисления (в версии исчисления доменов или исчисления кортежей) логические выражения часто называют правильно построенными формулами (well-formed formulas – WFF, что произносится как « вэфф»). Далее мы также будем часто пользоваться этой терминологией.
< логическое выражение с квантором>
:: = EXISTS < имя переменной кортежа >(< логическое выражение >)
| FORALL <имя переменной кортежа > (< логическое выражение >)
< реляционная операция >
:: = < прототип кортежа > [ WHERE < логическое выражение >]
В реляционной алгебре параметр < реляционная операция > представлял собой одну из форм параметра <реляционное выражение>, однако здесь он определяется иначе. Другие формы параметра < реляционное выражение > (в основном, имена переменных – отношений и обращение к операторам выбора) допустимы, как и ранее.
< прототип кортежа >
:: = < выражение кортежа>
Все ссылки на переменные кортежа, помещенные непосредственно в значение параметра <прототип кортежа>, должны быть свободными в пределах данного параметра < прототип кортежа>.
Замечание. Прототип кортежа – термин удачный, но не стандартный.
2.2. Переменные кортежей.
Приведём несколько примеров определения переменных кортежей (выраженных в контексте базы данных поставщиков и деталей).
RANGEVAR SX RANGES OVER S;
RANGEVAR SY RANGES OVER S;
RANGEVAR SPX RANGES OVER SP;
RANGEVAR SPY RANGES OVER SP;
RANGEVAR PX RANGES OVER P;
RANGEVAR SU RANGES OVER
(SX WHERE SX.CITY=’London’)
(SX WHERE EXISTS SPX (SPX.S# = SX.S# AND
SPX.P# SPX = P# (‘P1’) ) );
Переменная кортежа SU из последнего примера определена на объединении множества кортежей поставщиков детали с номером ‘P1’. Обратите внимание, что в определении переменной кортежа SU используются переменные кортежей SX и SPX. Также обратите внимание на то, что в подобных определениях переменных, построенных на объединении отношений, объединяемые отношения, безусловно, должны быть совместимы по типу.
Замечание. Переменные кортежей не являются переменными в обычном смысле (как в языках программирования); они являются переменными в логическом смысле.
2.3. Свободные и связанные переменные кортежей.
Каждая ссылка на переменную кортежа (в некотором контексте, в частности в формуле WFF) является или свободной, или связанной. Сначала поясним это утверждение в чисто синтаксических терминах, а затем перейдем к обсуждению его смысла.
Пусть V – переменная кортежа. Тогда имеем следующее.
- Ссылки на переменную V в формулах WFF типа NOT p свободны или связаны в пределах этой формулы в зависимости от того, свободны ли они в формуле p.Ссылки на переменную V в формулах WFF типа (p AND q) и (p OR q) свободны или связаны в зависимости от того, свободны ли они в формулах p и q.
- Ссылки на переменную V, которые свободны в формуле WFF p, связаны в формулах WFF типа EXISTS V(p) и FORALL V(p). Другие ссылки на переменные кортежей в формуле p будут свободны или связаны в формулах WFF типа EXISTS V(p) и FORALL V(p) в соответствии с тем, свободны ли они в формуле p.
