Реляционное исчисление

Федеральное агентство  железнодорожного транспорта

Уральский государственный  университет путей сообщения

 

 

 

 

 

Кафедра «Автоматика, телемеханика и связь»

 

 

 

 

 

 

 

Реферат

 по дисциплине: «Управление  данными» 

 на тему «Реляционное  исчисление»

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Екатеринбург 2012

Оглавление

 

 

 

 

Введение

 

Наиболее распространенная трактовка реляционной модели данных, по-видимому, принадлежит Дейту, который  воспроизводит ее (с различными уточнениями) практически во всех своих книгах. Согласно Дейту реляционная модель состоит из трех частей, описывающих разные аспекты реляционного подхода: структурной части, манипуляционной части и целостной части.

В структурной части модели фиксируется, что единственной структурой данных, используемой в реляционных БД, является нормализованное n-арное отношение. В манипуляционной части модели утверждаются два фундаментальных механизма манипулирования реляционными БД - реляционная алгебра и реляционное исчисление. Первый механизм базируется в основном на классической теории множеств (с некоторыми уточнениями), а второй - на классическом логическом аппарате исчисления предикатов первого порядка. В данной работе мы подробно рассмотрим механизм реляционного исчисления.

 

      

 

1.Реляционное исчисление

 

 Часть реляционной модели, которая связана с операторами манипулирования данными, основывается на использовании реляционной алгебры. Однако с тем же основанием можно сказать, что она построена на базе реляционного исчисления. Другими словами, реляционная алгебра и реляционное исчисление представляют собой два альтернативных подхода. Принципиальное различие между ними следующее. Реляционная алгебра в явном виде представляет набор операций (соединение, объединение, проекция и т.д.), которые можно использовать, чтобы сообщить системе, как в базе данных из определённых отношений построить некоторое требуемое отношение, а реляционное исчисление просто представляет систему обозначений для определения требуемого отношения в терминах данных отношений. Например, рассмотрим три отношения:

• S-поставщики, каждый поставщик имеет уникальный номер (S#); имя (SNAME); значение рейтинга или статуса (STATUS); место расположения (CITY). Предполагается, что каждый поставщик находится только в одном городе.
• P-детали, у каждого вида детали есть уникальный номер (P#); название детали (PNAME); цвет (COLOR); вес (WEIGHT); город, где хранится этот вид деталей (CITY). Каждый отдельный вид детали имеет только один цвет и хранится на складе только в одном городе.
• SP-поставки, служит для организации логической связи двух других отношений. Например, первая строка отношения SP связывает поставщика с номером ‘S1’ из отношения S с соответствующей деталью, имеющей номер ‘P1’ в отношении P, т.е. представляет факт поставки деталей типа ‘P1’ поставщиком с номером ‘S1’ (а также указывает количество деталей-300 штук). Таким образом, каждая поставка характеризуется номером поставщика (S#), номером детали (P#) и количеством (QTY). Предполагается, что в одно и то же время может быть не более одной поставки  для одного поставщика и одной детали.

S#	P#	QTY
S1	P1	300
S1	P2	200
S1	P3	400
S1	P4	200
S1	P5	100
S1	P6	100
S2	P1	300
S2	P2	400
S3	P2	200
S4	P2	200
S4	P4	300
S4	P5	400

                                                                                                                                                                                                                                                                                     

S#	SNAME	STATUS	CITY
S1	Smith	20	London
S2	Jones	10	Paris
S3	Black	30	Paris
S4	Clark	20	London
S5	Adams	30	Athens

P#	PNAME	COLOR	WEIGHT	CITY
P1	Nut	Red	12.0	London
P2	Bolt	Green	17.0	Paris
P3	Screw	Blue	17.0	Rome
P4	Screw	Red	14.0	London
P5	Cam	Blue	12.0	Paris
P6	Cog	Red	19.0	London

 

      

        

 

 

 

 

 

   Рассмотрим запрос «Выбрать номера поставщиков и названия городов, в которых находятся поставщики детали с номером ‘P2’». Алгебраическая версия этого запроса выглядит приблизительно так:

• Сначала выполнить соединение отношения поставщиков S и отношения поставок SP по атрибуту S#.
• Далее выбрать из результата этого соединения кортежи с номером детали ‘P2’.
• И, наконец, выполнить для результата этой выборки операцию проекции по атрибутам S# и CITY.

Этот же запрос в терминах реляционного исчисления формулируется  приблизительно так:

• Получить атрибуты S# и CITY для таких поставщиков, для которых в отношении SP существует запись о поставке с тем же значением атрибута P#, равным ‘P2’.

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

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

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

         Реляционное исчисление основано на разделе математической  логики, который называется исчислением  предикатов. Идея использования исчисления предикатов в качестве основы языка баз данных впервые была высказана в статье Кунса . Понятие реляционного исчисления, т.е. специального применения исчисления предикатов, в реляционных базах данных, впервые было предложено Коддом в 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.Исчисление кортежей

 

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

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

 

    

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

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

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

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

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

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

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

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

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

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

• перед точкой  и последующим уточнением в параметре < ссылка на атрибут кортежа >;
• сразу после квантора в параметре < логическое выражение с квантором>;
• как операнд в параметре  < логическое выражение >;
• как параметр < прототип кортежа > или как (операнд) подпараметр < выражение> в параметре < прототип кортежа >.

                 < ссылка на  атрибут кортежа  >

                          :: =     <имя переменной кортежа>.<ссылка на атрибут>[ AS <имя атрибута>]

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

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

             < логическое выражение >

                           :: =    …  все обычные   возможности вместе с:

                                        | < логическое выражение с квантором>

       Ссылки на  переменные кортежей в значении параметра < логическое выражение > могут быть свободными в пределах  этого параметра тогда и только тогда, когда выполнено два следующих условия.

• Параметр  < логическое выражение> расположен непосредственно после параметра < реляционная операция> (т.е. параметр  < логическое выражение > следует сразу  за ключевым словом  WHERE.).
• Ссылка (обязательно свободная) именно на эту переменную кортежа непосредственно присутствуют в значении параметра <прототип кортежа>, непосредственно содержащегося в том же выражении <реляционная операция>(т.е. параметр <прототип кортежа> располагается непосредственно перед ключевым словом  WHERE).

       В контексте реляционного исчисления (в версии исчисления доменов или исчисления кортежей) логические выражения часто называют  правильно построенными формулами (well-formed formulas – WFF, что произносится как « вэфф»). Далее мы также будем часто пользоваться этой терминологией.

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

                      :: =        EXISTS  < имя переменной  кортежа >(< логическое выражение >)

                                 | FORALL  <имя переменной кортежа > (< логическое выражение >)

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

                       :: =      < прототип кортежа > [ WHERE  < логическое выражение >]

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

            < прототип кортежа >

                       :: =       < выражение кортежа>

        Все ссылки на переменные кортежа, помещенные непосредственно в значение параметра <прототип кортежа>, должны быть свободными в пределах данного параметра  < прототип кортежа>.