Реферат: Реляционное исчисление

В этой формулировке пользователь лишь указывает определённые характеристики требуемого результата, оставляя системе решать, что именно и в какой последовательности соединять, проецировать и т.д., чтобы получить необходимый результат.

Итак, можно сказать, что, по крайней мере, внешне формулировка запроса в терминах реляционного исчисления носит описательный характер, а в терминах реляционной алгебры - предписывающий . В реляционном исчислении просто описывается, в чём заключается проблема, тогда как реляционной алгебре задаётся процедура решения этой проблемы. Или, говоря очень неформально, алгебра имеет процедурный характер (пусть на высоком уровне, но всё же процедурный, поскольку задаёт необходимые для выполнения процедуры), а исчисление – непроцедурный.

Подчеркнём, однако, что упомянутые отличия существуют только внешне. На самом деле реляционная алгебра и реляционное исчисление логически эквивалентны . Каждому выражению в алгебре соответствует эквивалентное выражение в исчислении, и точно так каждому выражению в исчислении соответствует эквивалентное выражение в алгебре. Это означает, что между ними существует взаимнооднозначное соответствие, а различия связаны лишь с разными стилями выражения; исчисление ближе к естественному языку, а алгебра - к языку программирования; Но повторим еще раз, эти различия только кажущиеся, а не реальные. В частности, ни один из подходов нельзя назвать « более непроцедурным « по сравнению с другим.

Реляционное исчисление основано на разделе математической логики, который называется исчислением предикатов . Идея использования исчисления предикатов в качестве основы языка баз данных впервые была высказана в статье Кунса (Kuhns). Понятие реляционного исчисления, т.е. специального применения исчисления предикатов, в реляционных базах данных, впервые было предложено Коддом в 1972, а позже Кодд представил язык, основанный непосредственно на реляционном исчислении и названный « подъязык данных ALPHA». Сам язык ALPHA никогда не был реализован, однако язык QUEL, который действительно был реализован и некоторое время серьезно конкурировал с языком SQL , очень походил на язык ALPHA , оказавший заметное влияние на построение языка QUEL .

Основным средством реляционного исчисления является понятие переменной кортежа (также называемой переменной области значений ). Коротко говоря, переменная кортежа – это переменная, «изменяющаяся на» некотором заданном отношении, т.е. переменная, допустимыми значениями которой являются кортежи заданного отношения. Другими словами, если переменная кортежа 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.Исчисление кортежей.

Сначала введем для реляционного исчисления конкретный синтаксис, взяв за образец (хотя умышленно не совсем точно) версию исчисления языка TitorialD, а затем перейдём к обсуждению семантики. В следующих ниже подразделах обсуждаются синтаксис и семантика.

2.1.Синтаксис.

Замечание . Многие из приведенных здесь синтаксических правил не будут поняты вам до тех пор, пока вы не изучите семантический материал, следующий далее. Однако мы все же решили собрать все правила вместе для удобства ссылок.

Начнем с повторения синтаксиса параметра <реляционное выражение>. < реляционное выражение>

:: = RELATION{<список выражений кортежей>}

| < имя переменной-отношения>

| < реляционная операция>

| < реляционное выражение>

Иными словами, синтаксис параметра <реляционное выражение > остается прежним, однако из наиболее важных его подпараметров, < реляционная операция >, теперь будет иметь совершенно иное определение.

<определение переменной кортежа>

:: = RANGEVAR <имя переменной кортежа >

RANGESOVER <список реляционных выражений >;

Параметр <имя переменной кортежа> может использоваться как <выражение кортежа>, однако, лишь в определенном контексте, а именно:

- перед точкой и последующим уточнением в параметре < ссылка на атрибут кортежа >;

- сразу после квантора в параметре < логическое выражение с квантором>;

- как операнд в параметре < логическое выражение >;

- как параметр < прототип кортежа > или как (операнд) подпараметр < выражение> в параметре < прототип кортежа >.