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

Следовательно, без потери общности прототип кортежа можно рассматривать как список, состоящий из разделённых запятыми ссылок на атрибуты в виде Vi.Ai AS Bj. Обратите внимание, что ссылки Vi- и Aj-е могут повторяться, тогда как ссылки Bj-е должны быть разными.

• Пусть V1, V2, … ,Vm будут различными переменными кортежей, упоминаемыми в прототипе кортежа, и пусть эти переменные будут определены на отношениях r1, r2, … ,rm соответственно. Примем, что r1’, r2’, … ,rm’ ─ это новые отношения, полученные после переименования атрибутов в предложении AS, и пусть r’ ─ это декартово произведение отношений r1’, r2’, … , rm’.
• Пусть отношение r ─ это выборка из отношения r’, удовлетворяющая формуле WFF в предложении WHERE.                                                                                                                                                                            

Здесь предполагается, что  на предыдущем шаге были также переименованы  атрибуты, упоминающиеся в предложении WHERE; в противном случае функция WFF в предложении WHERE может не иметь смысла.

• Конечное значение реляционной операции, заданной параметром <реляционное выражение>, определяется как проекция отношения r по всем заданным атрибутам Bj.

 

                                                

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.7. Примеры

 

       Представляем несколько примеров использования реляционного исчисления кортежей для формулирования запросов.

• Определить имена поставщиков детали с номером ‘P2’                                                                                      

SX

WHERE EXISTS SPX (SPX.S# = SX.S# AND

                                        SPX.P# = P# (‘P2’) )

         Обратите внимание на использование  имени переменной кортежа в  прототипе кортежа. Этот пример  является сокращённой записью  следующего выражения.

(SX.S#, SX.NAME, SX.STATUS, SX.CITY)

WHERE EXISTS SPX (SPX.S# = SX.S# AND

                                        SPX.P# = P# (‘P2’) )

Этот же пример решённый средствами реляционной алгебры  выглядит так

( (SP JOIN S) WHERE P# =’P2’) {SNAME}

• Определить имена поставщиков по крайней мере одной красной детали

SX.SNAME

WHERE EXISTS SPX (SX.S# = SPX.S# AND

                                        EXISTS PX (PX.P# = SPX.P# AND

                                                              PX.COLOR = COLOR (‘Red’) ) )

Этот же пример решённый средствами реляционной алгебры  выглядит так

( ( ( P WHERE COLOR = COLOR (‘Red’) )

                                            JOIN SP) {S#} JOIN S) {SNAME}

3. Сравнительный анализ реляционного  исчисления и           реляционной алгебры

 

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

 

                                                                                                          

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

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

S#	P#	J#	QTY
S1	P1	J1	200
S1	P1	J4	700
S2	P3	J1	400
S2	P3	J2	200
S2	P3	J3	200
S2	P3	J4	500
S2	P3	J5	600
S2	P3	J6	400
S2	P3	J7	800
S2	P5	J2	100
S3	P3	J1	200
S3	P4	J2	500
S4	P6	J3	300
S4	P6	J7	300
S5	P2	J2	200
S5	P2	J4	100
S5	P5	J5	500
S5	P5	J7	100
S5	P6	J2	200
S5	P1	J4	100
S5	P3	J4	200
S5	P4	J4	800
S5	P5	J4	400
S5	P6	J4	500

 

    

J#	JNAME	CITY
J1	Sorter	Paris
J2	Display	Rome
J3	OCR	Athens
J4	Console	Athens
J5	RAID	London
J6	EDS	Oslo
J7	Tape	London

 
 

S-детали, P- поставщики, J- проекты, SPJ- поставки.

        Рассмотрим теперь следующий запрос: «Получить имена поставщиков и названия городов, в которых находятся поставщики деталей по крайней мере для одного проекта в Афинах, поставляющих по крайней мере 50 штук каждой детали». Выражение реляционного исчисления для этого запроса следующее.

        (SX.SNAME, SX.CITY) WHERE EXISTS JX FORALL PX EXISTS SPJX

                                                                             ( JX.CITY = ‘Athens’ AND

                                                                                JX.J# = SPJX.J# AND

                                                                                PX.P# = SPJX.P# AND

                                                                                SX.S# = SPJX.S# AND

                                                                                SPJX.QTY ≥ QTY (50) )

        Здесь SX, PX, JX и SPJX ─ переменные кортежей, получающие свои значения из отношений S, P, J и SPJ соответственно. Теперь покажем, как можно вычислить это выражение, чтобы достичь требуемого результата.

        Этап 1. Для каждой переменной кортежа выбираем её область значений (т.е. набор всех значений для переменной), если это возможно. Выражение «выбираем, если возможно» подразумевает, что существует условие выборки, встроенное в фразу WHERE, которую можно использовать, чтобы сразу исключить из рассмотрения некоторые кортежи. В нашем случае выбираются следующие наборы кортежей.

          SX         :  Все кортежи отношения S                                                  5 кортежей

          PX         : Все кортежи отношения P                                                  6 кортежей

          JX         :   Кортежи отношения J, в которых CITY = ‘Athens’         2 кортежа

          SPJX     :  Кортежи отношения SPJ, в которых CITY ≥ 50               24 кортежа

        Этап 2. Строим декартово произведение диапазонов, выбранных на первом этапе. Вот результат.

 

 

S#

SN

STA TUS

CITY

P#

PN

CO-LOR

WEIGHT

CITY

J#

JN

CITY

S#

P#

J#

QTY

S1

Sm

20

Lon

P1

Nt

Red

12.0

Lon

J3

OR

Ath

S1

P1

J1

200

S2

Sm

20

Lon

P1

Nt

Red

12.0

Lon

J3

OR

Ath

S1

P1

J4

700

..

..

..

…

..

..

…

…

…

..

..

…

..

..

..

…

                  

        (И т.д.) Всё произведение содержит 5*6*2*24=1440 кортежей.

        Для экономии места здесь это отношение полностью не приводится. Мы также не переименовывали атрибуты (хотя это следовало бы сделать во избежание двусмысленности), просто расположили их в таком порядке, чтобы было видно, какой атрибут S# относится, например, к отношению S, а какой ─ к отношению SPJ. Это также сделано для сокращения изложения.

        Этап 3. Осуществляем выборку из построенного на этапе 2 произведения в соответствии с частью «условие соединения» фразы WHERE. В нашем примере эта часть выглядит следующим образом.

        JX.J# = SPJX.J# AND PX.P# = SPJX.P# AND SX.S# = SPJX.S#

        Поэтому из произведения исключаются  кортежи, для которых значение  атрибута S# из отношения поставщиков не равно значению атрибута S# из отношения поставок, значение атрибута P# из отношения деталей не равно значению атрибута P# из отношения поставок, значение атрибута J# из отношения проектов не равно значению атрибута J# из отношения поставок. Затем получаем подмножество декартова произведения, состоящее (как оказалось) только из десяти кортежей.

 

S#

SN

STA TUS

CI-TY

P#

PN

CO-LOR

WEIGHT

CITY

J#

JN

CI-TY

S#

P#

J#

QTY

S1

Sm

20

Lon

P1

Nt

Red

12.0

Lon

J4

Cn

Ath

S1

P1

J4

700

S2

Jo

10

Par

P3

Sc

Blue

17.0

Rom

J3

OR

Ath

S2

P3

J3

200

S2

Jo

10

Par

P3

Sc

Blue

17.0

Rom

J4

Cn

Ath

S2

P3

J4

200

S4

Cl

20

Lon

P6

Cg

Red

19.0

Lon

J3

OR

Ath

S4

P6

J3

300

S5

Ad

30

Ath

P2

Bt

Green

17.0

Par

J4

Cn

Ath

S5

P2

J4

100

S5

Ad

30

Ath

P1

Nt

Red

12.0

Lon

J4

Cn

Ath

S5

P1

J4

100

S5

Ad

30

Ath

P3

Sc

Blue

17.0

Rom

J4

Cn

Ath

S5

P3

J4

200

S5

Ad

30

Ath

P4

Sc

Red

14.0

Lon

J4

Cn

Ath

S5

P4

J4

800

S5

Ad

30

Ath

P5

Cm

Blue

12.0

Par

J4

Cn

Ath

S5

P5

J4

400

S5

Ad

30

Ath

P6

Cg

Red

19.0

Lon

J4

Cn

Ath

S5

P6

J4

500

  

       

        Этап 4. Применяем кванторы в порядке справа налево следующим образом.

• Для квантора EXISTS RX (где RX ─ переменная кортежа, принимающая значение на некотором отношении r) проецируем текущий промежуточный результат, чтобы исключить все атрибуты отношения r.
• Для квантора FORALL RX делим текущий промежуточный результат на отношение «выбранной области значений», соответствующее RX, которое было получено выше. При выполнении этой операции также будут исключены все атрибуты отношения r.

Под делением здесь подразумевается  оригинальная операция деления Кодда.

В нашем примере имеем  следующие кванторы.

EXISTS JX FORALL PX EXISTS SPJX

Значит, выполняются следующие операции.

1. (EXISTS SPJX) Проецируем, исключая атрибуты отношения SPJ (SPJ.S#,     

  SPJ.P#, SPJ.J#  и SPJ.QTY). В результате получаем следующее.

S#	SN	STA TUS	CI-TY	P#	PN	CO-LOR	WEIGHT	CITY	J#	JN	CI-TY
S1	Sm	20	Lon	P1	Nt	Red	12.0	Lon	J4	Cn	Ath
S2	Jo	10	Par	P3	Sc	Blue	17.0	Rom	J3	OR	Ath
S2	Jo	10	Par	P3	Sc	Blue	17.0	Rom	J4	Cn	Ath
S4	Cl	20	Lon	P6	Cg	Red	19.0	Lon	J3	OR	Ath
S5	Ad	30	Ath	P2	Bt	Green	17.0	Par	J4	Cn	Ath
S5	Ad	30	Ath	P1	Nt	Red	12.0	Lon	J4	Cn	Ath
S5	Ad	30	Ath	P3	Sc	Blue	17.0	Rom	J4	Cn	Ath
S5	Ad	30	Ath	P4	Sc	Red	14.0	Lon	J4	Cn	Ath
S5	Ad	30	Ath	P5	Cm	Blue	12.0	Par	J4	Cn	Ath
S5	Ad	30	Ath	P6	Cg	Red	19.0	Lon	J4	Cn	Ath

 

2.(FORALL PX) Делим полученный результат на отношение P. В результате имеем следующее.