Реферат: Реляционное исчисление
Замечание. Здесь предполагается, что на предыдущем шаге были также переименованы атрибуты, упоминающиеся в предложении 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. Сравнительный анализ реляционного исчисления и реляционной алгебры.
В начале утверждалось, что реляционная алгебра и реляционное исчисление в своей основе эквивалентны. Осудим это утверждение более подробно. Вначале Кодд показал, что алгебра по крайней мере мощнее исчисления. Он сделал это, придумав алгоритм, называемый алгоритмом редукции Кодда, с помощью которого любое выражение исчисления можно преобразовать в семантически эквивалентное выражение алгебры. Мы не станем приводить здесь этот алгоритм полностью, а ограничимся довольно сложным примером, иллюстрирующим в общих чертах, как он функционирует.
| 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 |
| 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 |
| 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 |
