Зміст.
1. Введення.
2. Обчислення кортежів.
2.1. Синтаксис.
2.2. Змінні кортежів.
2.3. Вільні і зв'язані змінні кортежів.
2.4. Квантори.
2.5. Ще раз про зведених і пов'язаних змінних.
2.6. Реляційні операції.
2.7. Приклади
3. Порівняльний аналіз реляційного обчислення і реляційної алгебри.
4. Обчислювальні можливості.
4.1. Приклади
5. Обчислення доменів.
5.1. Приклади
6. Засоби мови SQL.
6.1. Приклади
7. Висновок.
8. Список літератури.
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 # | 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 # | 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 |
| 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'.
У цьому формулюванні користувач лише вказує певніхарактеристики необхідного результату, залишаючи системі вирішувати, що саме ів якій послідовності з'єднувати, проектувати і т.д., щоб отриматинеобхідний результат.
Отже, можна сказати, що, принаймні, зовні формулюваннязапиту в термінах реляційного обчислення носить описовий характер, а втермінах реляційної алгебри - наказує. У реляційному численніпросто описується, в чому полягає проблема, тоді як реляційноїалгебри задається процедура вирішення цієї проблеми. Або, кажучи дуженеформально, алгебра має процедурний характер (хай на високому рівні,але все ж таки процедурний, оскільки задає необхідні для виконанняпроцедури), а обчислення - непроцедурного.
Підкреслимо, однак, що згадані відмінності існують тількизовні. Насправді реляційна алгебра і реляційне численнялогічно еквівалентні. Кожному висловом в алгебрі відповідаєеквівалентне вираз в обчисленні, і точно так кожному вираз навирахуванні відповідає еквівалентний вираз в алгебрі. Це означає,що між ними існує взаімнооднозначное відповідність, а відмінностіпов'язані лише з різними стилями вирази; числення ближче до природногомови, а алгебра - до мови програмування; Але повторимо ще раз, цівідмінності тільки здаються, а не реальні. Зокрема, жоден з підходівне можна назвати «більшенепроцедурного «порівняно з іншим.
Реляційне обчислення засноване на розділі математичної логіки,який називається обчисленням предикатів. Ідея використання обчисленняпредикатів як основи мови баз даних вперше була висловлена встатті Кунса (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.Ісчісленіе кортежів.
Спочатку введемо для реляційного обчислення конкретний синтаксис,взявши за зразок (хоча навмисне не зовсім точно) версію обчислення мови
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.
Для повноти потрібно додати наступні зауваження.
. Єдина посилання на змінну V в значенні параметра є вільною у межах цього параметра.
. Єдина посилання на змінну V в значенні параметра VA є вільною у межах цього параметра.
. Якщо посилання на змінну V є вільною у деякому виразі exp, то це посилання буде також вільною в будь-якому вираженні exp ', безпосередньо містить вираз exp як подвираженіе, якщо тільки у виразі exp' не вводиться квантор, що зв'язує змінну V.
Наведемо кілька прикладів формул WFF, що містять зміннікортежів.
. Прості порівняння
SX.S # = S # ( 'S1')
SX.S # = SPX.S #
SPX.P #? PX.P #
Тут всі посилання на змінні SX, PX і SPX є вільними.
. Логічні вирази з простих порівнянь
PX.WEIGHT NOT (SX.CITY = 'London')
SX.S # = SPX.S # AND SPX.P #? PX.P #
PX.COLOR = COLOR ( 'Red') OR PX.CITY = 'London' Тут також всі посилання на змінні SX, PX і SPX є вільними.
. Формули WFF з квантора
EXISTS SPX (SPX.S # = SX.S # AND SPX.P # = P # ( 'P2'))
FORALL PX (PX.COLOR = COLOR ( 'Red'))
У цих прикладах посилання на змінні SPX і PX є пов'язаними, а посилання на змінну SX є вільною. Подробнее дані приклади пояснюються нижче.
2.4. Квантори.
Існують два квантора: EXISTS і FORALL. Квантор EXISTS єквантором існування, а FORALL-квантором загальності. По суті, якщовираз p - формула WFF, в якій мінлива V вільна, то вираження
EXISTS V (p)і
FORALL V (p) також є допустимими формулами WFF, але мінлива V в них обохбуде пов'язаної. Перша формула означає наступне: «Існує по крайнеймірою одне значення змінної V, таке, що обчислення формули p дає длянього значення істина ». Друга формула означає наступне: «Для всіхзначень змінної V обчислення формули p дає значення істина ».
Припустимо, наприклад, що змінна V змінюється на безлічі «Членисенату США в 1999 році », і припустимо також, що вираз p - наступнаформула WFF: «V - жінка» (зрозуміло, тут не намагаємося використовуватиформальний синтаксис). Тоді вираз EXISTS V (p) буде допустимоїформулою WFF, що має значення істина (true); вираз FORALL V (p) такожбуде допустимої формулою WFF, але обчислення його значення буде даватизначення ложь (false).
Тепер розглянемо квантор існування EXISTS уважніше. Щераз звернемося до прикладу з попереднього розділу.
EXISTS SPX (SPX.S # = SX.S # AND SPX.P # = P # ( 'P2'))
З наведених раніше міркувань випливає, що ця формула WFF можебути прочитана в такий спосіб.
У поточному значенні відносини SP існує кортеж (скажімо, SPX), такий,для якого значення атрибуту S # в цьому кортежі дорівнює значенню атрибута
SX.S # (яке б воно не було), а значення атрибуту P # в кортежі SPX одно
'P2'.
Кожне посилання на змінну SPX в цьому прикладі є пов'язаною.
Єдина посилання на змінну SX вільна.
Формально квантор існування EXISTS визначається як повторенняоперації OR (АБО). Іншими словами, якщо r - це відношення з кортежами t1,t2, ..., tm, V - це мінлива кортежу, зміни, що на даному відношенні, іp (V) - це формула WFF, в якій мінлива V використовується як вільназмінна, то формула WFF виду
EXISTS V (p (V))рівносильна такою формулою WFF. false OR p (t1) OR ... OR p (tm)
Зокрема, зверніть увагу, що якщо відношення R пусте (тобтоm = 0), то результатом обчислення цього виразу буде значення брехня.
Розглянемо як приклад ставлення r, що містить наступнікортежі.
(1, 2, 3)
(1, 2, 4)
(1, 3, 4)
Для простоти припустимо, що три атрибута, що йдуть по порядку зліванаправо, мають імена A, B і C відповідно і кожен з цих атрибутівмає тип INTEGER. Тоді наведені нижче вирази будуть мати зазначенізначення.
EXISTS V (VC> 1): true
EXISTS V (VB> 3): false
EXISTS V (VA> 1 OR VC = 4): true
Тепер розглянемо квантор спільності FORALL, для чого повернемося довідповідному прикладу з попереднього розділу.
FORALL PX (PX.COLOR = COLOR ( 'Red'))
Ця формула WFF може бути прочитана в такий спосіб.
У поточному значенні відносини P для всіх кортежів (скажімо, PX) значення їхатрибута COLOR одно 'Red'.
Обидві посилання на змінну PX в цьому прикладі пов'язані.
Подібно до того, як квантор EXISTS був визначений як повторенняоперації OR, квантор існування FORALL визначається як повторюєтьсяоперація AND (І). Іншими словами, якщо позначення r, V і p (V) мають тойж значення, що і в наведеному вище визначенні квантора EXISTS, то формула
WFF виду
FORALL V (p (V)) рівносильна такою формулою WFF. true AND p (t1) AND ... AND p (tm)
Зокрема, зверніть увагу, що якщо відношення r пусте, торезультатом обчислення цього виразу буде значення істина.
В якості прикладу розглянемо відношення R, що містить ті жкортежі, що і в попередньому прикладі. Тоді наведені нижче вислови будутьмати вказані значення.
FORALL V (VA> 1): false
FORALL V (VB> 1): true
FORALL V (VA = 1 and VC> 2): true
Зауваження. Квантор FORALL включено до реляційне числення простодля зручності. Він не є необхідним, тому що наведене нижчетотожність показує, що будь-яка формула WFF, що використовує квантор FORALL,завжди може бути замінена еквівалентною формулою WFF, що використовує квантор
EXISTS.
FORALL V (p)? NOT EXISTS V (NOT p)
(Простіше кажучи, вислів «всі значення V, що задовольняють формулоюp »- це те ж саме, що і вираз« немає таких значень V, які б незадовольняли формулою p ».)
Наприклад, затвердження (дійсне)
Для будь-якого цілого x існує ціле y, таке, що y> xрівносильно твердженням
Не існує цілого x, такого, що не існує цілого y, такого,що y> x.
(Інакше кажучи, не існує найбільшого цілого числа.) Але зазвичайлегше виразити подібне твердження в термінах квантора FORALL, ніж утермінах квантора EXISTS, з використанням подвійного заперечення. Іншимисловами, на практиці набагато зручніше використовувати обидва квантора.
2.5. Ще раз про вільні і пов'язаних змінних.
Припустимо, що змінна x змінюється на множині всіх цілихчисел, і розглянемо наступну формулу WFF.
EXISTS x (x> 3)
Зв'язана мінлива x в цій формулі WFF є свого родуфіктивної змінної. Вона служить лише для зв'язку внутрішніх параметріввислову з зовнішнім квантором. У формулі WFF просто стверджується, щоіснує ціле число (скажімо, x), яке більше 3. Отже,значення цієї формули WFF залишилося б повністю незмінним, якщо б всіекземпляри x були замінені примірниками деякої іншої змінної
(скажімо, y). Іншими словами, формула WFF EXISTS y (y> 3) семантичноідентична формулою, наведеною раніше.
Тепер розглянемо іншу формулу WFF.
EXISTS x (x> 3) AND x3) AND x3) AND y Визначити імена постачальників деталі з номером 'P2'
SX
WHERE EXISTS SPX (SPX.S # = SX.S # AND
SPX.P # = P # ( 'P2')) < p> Зверніть увагу на використання імені змінної кортежу в прототипі кортежу. Цей приклад є скороченою записом наступного виразу.
(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 | Displa | Rome |
| | Y | |
| J3 | OCR | Athens |
| J4 | Consol | Athens |
| | E | |
| 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. Будуємо декартовій твір діапазонів, обраних напершому етапі. Ось результат.
| S5 | Adams | 30 | Athens | J4 | Console | Athens |
(Тепер у нас є місце, щоб показати ставлення повністю, безскорочень.)
1. (EXISTS JX) проектуємо, виключаючи атрибути відносини J (JJ #, J. NAME і
J. CITY). В результаті отримуємо наступне.
| S # | SN | STATUS | CITY |
| S5 | Adams | 30 | Athens |
Етап 5. Проектуємо результат етапу 4 у відповідності зі специфікаціямив прототипі кортежу. У нашому прикладі має такий вигляд.
(SX.SNAME, SX.CITY)
Отже, кінцевий результат обчислень буде такий.
| SNAME | CITY |
| Adams | Athens |
Зі сказаного вище випливає, що початкова вираз обчисленнясемантично еквівалентно певного вкладеному алгебраїчномувиразу, і, якщо бути більш точним, це проекція від проекції результатуподілу проекції вибірки з твору чотирьох вибірок (!).
І хоча багато подробиць в поясненнях були втрачені, цей прикладцілком адекватно відображає загальну ідею роботи алгоритму редукції.
Тепер моно пояснити одну з причин (і не тільки одну)визначення Коддом рівно восьми алгебраїчних операторів. Ці вісімреляційних операторів утворюють зручний цільової мова як засіб можливоїреалізації реляційного числення. Іншими словами, для заданого мови,побудованого на основі реляційного обчислення (подібно до мови QUEL), одинз можливих підходів реалізації полягає в тому, що організуєтьсяпро замовлений в тому вигляді, в якому він є користувачем. Засуті, він буде просто вираженням реляційного обчислення, доякому потім можна буде застосувати певний алгоритм редукції, щоботримати еквівалентну алгебраїчне вираз. Це алгебраїчневираз, звичайно, буде включати набір алгебраїчних операцій, якіза визначенням бути реалізовані за самою своєю природою.
Також слід зазначити, що вісім алгебраїчних операторів Коддає критерієм оцінки виразної сили будь-якої мови баз даних.
Деякий мову прийнято називати реляційної повним, якщо він посвоїми можливостями принаймні не поступається реляційному обчисленню.
Інакше кажучи, будь-яке відношення, яке можна визначити за допомогоюреляційного обчислення, можна визначити і за допомогою деякого виразурозглянутого мови. ( «Реляційне повний» означає «не поступається заможливостям реляційної алгебри », а не вирахуванню, але це одне і те ж,як ми незабаром переконаємося. По суті, з самого існування алгоритму редукції
Кодда негайно випливає, що реляційна алгебра має реляційноїповнотою.)
реляційну повноту можна як основну міру виразної силимов баз даних у загальному випадку. Зокрема, так як реляційнечислення та реляційна алгебра мають реляційної повнотою, вони можутьслужити основою для проектування не поступаються їм за виразністюмов без необхідності виконувати пересортіровку для організації циклів.
Це зауваження особливо важливо, якщо мова призначається для кінцевихкористувачів, хоча воно також істотно, якщо мова призначається длявикористання прикладними програмістами.
Далі, оскільки алгебра має реляційної повнотою, длядокази того, що деякий мова L також володіє реляційноїповнотою, досить показати, що в мові L є аналогією всіх восьмиалгебраїчних операцій (насправді досить показати, що в ньому єаналоги п'яти примітивних операцій) і що операндами будь-якої операції мови Lможуть бути будь-які вираження цієї мови. Мова SQL - це приклад мови,реляційну повноту якого можна довести зазначеним способом. Мова QUEL --ще один приклад подібного мови. У дійсності на практиці часто простішепоказати те, що в мові є еквіваленти операцій реляційної алгебри, ніжте, що в ньому існують еквіваленти виразів реляційного числення.
Саме тому реляційна повнота звичайно визначається в термінахалгебраїчних виразів, а не в термінах виразів реляційногообчислення.
При цьому важливо розуміти, що реляційна повнота необов'язковотягне за собою повноту будь-якого іншого роду. Наприклад, бажано,щоб мову також забезпечував «обчислювальну повноту», тобто дозволявобчислювати результати всіх вичіслімих функцій. Зауважимо, що відповідно до нашоговизначення числення не володіє повнотою такого роду, хоча на практиціподібна повнота для мови баз даних дуже бажана. Обчислювальнаповнота - це один з факторів, що спонукали ввести в реляційну алгебруоперації EXTEND і SUMMARIZE. У наступному розділі описано, як можнарозширити реляційне перелічені, щоб забезпечити в ньому наявність аналогівцих операцій.
Повернемося до питання еквівалентності алгебри та обчислення. Ми наприкладі показали, що будь-який вираз обчислення можна перетворити в йогодеякий алгебраїчний еквівалент, а значить, алгебра принаймні непоступається за своєю потужністю обчисленню. Можна показати протилежне: кожневираз реляційної алгебри можна перетворити на еквівалентне виразреляційного обчислення, а отже, обчислення принаймні не поступаєтьсяза своєю потужністю реляційної алгебри. Звідси випливає, що реляційнаалгебра і реляційне числення еквівалентні.
4. Обчислювальні можливості.
Незважаючи на те що раніше про це не згадувалося, у певномунами реляційному численні вже є аналоги алгебраїчних операторів
EXTEND і SUMMARIZE, і ось чому.
. Однією з допустимих форм прототипу кортежу є параметр, компонентами якого можуть бути довільні подпараметри.
. У параметрах порівнюють елементами можуть бути довільні подпараметри.
. Першим або єдиним аргументом в параметрі є подпараметр.
4.1. Приклади.
> Для кожної деталі вибрати номер і загальний обсяг поставки в штуках
(PX.P #, SUM (SPX WHERE SPX.P # = PX.P #, QTY) AS TOTQTY) < br>> Визначити загальна кількість що поставляються деталей
SUM (SPX, QTY) AS GRANDTOTAL)
> Визначити номери та вага в грамах всіх типів деталей, вага яких перевищує 10000г
(PX.P #, PX.WEIGHT * 454 AS GMWT)
WHERE PX.WEIGHT * 454> WEIGHT
(10000)
Зверніть увагу, що специфікація AS GMWT в прототипі кортежу дає ім'я відповідного атрибуту результату. Тому таке ім'я недоступне для використання в пропозиції WHERE і вираз PX.WEIGHT * 454 має бути зазначено в двох місцях.
5. Обчислення доменів.
Як зазначалося в «Вступ», реляційне числення,орієнтоване на домени (або числення доменів), відрізняється відобчислення кортежів тим, що в ньому замість змінних кортежів використовуєтьсязмінні доменів, тобто змінні, що приймають свої значення в межахдомену, а не відносини. З практичної точки зору більшість очевиднихвідмінностей між версіями обчислення доменів та обчислення кортежів заснованена тому, що версія для доменів підтримує форму параметра, який ми будемо називати умовою приналежності. У загальному виглядіумова приналежності можна записати так.
R (пара, пара, ...)
Тут R-ім'я відносини, а кожен параметр пара має вигляд A: v, де
A - атрибут відношення R, а v - ім'я змінної домену або літерал. Перевіркаумови дає значення істина тоді і тільки тоді, коли в поточному значеннівідносини R існує кортеж, що має вказані значення для зазначенихатрибутів. Наприклад, розглянемо результат обчислення наступного виразу.
SP (S #: S # ( 'S1'), P #: P # ( 'P1'))
Він буде мати значення істина тоді і тільки тоді, коли ввідношенні SP буде існувати кортеж із значенням атрибута S #, рівним
'S1', і значенням атрибута P #, рівним 'P1'. Аналогічно умоваприналежності
SP (S #: SX, P #: PX)приймає значення істина тоді й тільки тоді, коли у відношенні SPіснує кортеж із значенням атрибута S #, еквівалентним поточним значеннямзмінної домену PX (знову ж таки, якому б не було).
Далі будемо мати на увазі існування наступних зміннихдоменів.
Домен
Змінна домену
S #
SX, SY, ...
P #
PX, PY, ...
NAME
NAMEX, NAMEY, ...
COLOR
COLORX, COLORY, ...
WEIGHT
WEIGHTX, WEIGHTY, ...
QTY
QTYX, QTYY, ...
CHAR
CITYX, CITYY, ...
INTEGER
STATUSX, STATUSY, ...
Нижче наведено кілька прикладів виразів обчислення доменів.
SX
SX WHERE S (S #: SX)
SX WHERE S (S #: SX, CITY: 'London')
(SX, CITYX) WHERE S (S #: SX, CITY: 'London')
AND SP (S #: SX, P #: P # ( 'P2')) < p> (SX, PX) WHERE S (S #: SX, CITY: CITYX)
AND P (P #: PX, CITY: CITYY)
AND CITYX? CITYY
Якщо говорити Нестра, перший вираз означає безліч всіхномерів постачальників, другий - безліч всіх номерів постачальників з
Лондона. Наступний вираз - це виражений в термінах обчислення доменівзапит «Визначити номери постачальників і назви міст, в якихзнаходяться постачальники деталі з номером 'P2' »(згадаймо, що в цьому запиті,вираженому в термінах обчислення кортежів, використовувався кванторіснування). І останній вираз - це представлений в термінахобчислення доменів запит «Знайти всі такі пари номерів постачальників іномерів деталей, для яких постачальник і деталь знаходяться в одному місті ».
5.1. Приклади.
> Знайти всі такі пари номерів постачальників, в яких два постачальники знаходяться в одному місті
(SX AS SA, SY AS SB) WHERE EXISTS CITYZ
(S ( S #: SX, CITY:
CITYZ) AND
S (S #: SY, CITY:
CITYZ) AND
SX > Визначити імена постачальників принаймні однією червоною деталі
NAMEX WHERE EXISTS SX EXISTS PX (S (S #: SX, SNAME: NAMEX)
AND SP (S # : SX, P #: PX)
AND P (P #: PX, COLOR: COLOR ( 'Red')))
> Вибрати імена постачальників всіх типів деталей
NAMEX WHERE EXISTS SX (S (S #: SX, SNAME: NAMEX)
AND FORALL PX (IF P (P #: PX) < p> THEN SP
(S #: SX, P #: PX)
END IF)
6. Засоби мови SQL.
Як вже говорилося в розділі «Порівняльний аналіз реляційногообчислення і реляційної алгебри », в основу реляційного мови можуть бутипокладені як реляційна алгебра, так і реляційне числення. Що жпокладено в основу мови SQL? Відповіддю буде № частково і те, і інше, ачастково ні те, ні інше ... ». Коли мова SQL тільки розроблявся,передбачалося що він буде відрізнятися як від реляційної алгебри, так і відреляційного числення. Дійсно, саме цим мотивувалося введенняв мову конструкції IN. Однак згодом з'ясувалося, що мова
SQL потребує певних засобах як реляційної алгебри, так іобчислення, тому він був розширений для включення цих функцій. Насьогоднішній день ситуація складається таким чином, що мова SQL в чомусьсхожий на реляційну алгебру, в чем-то на реляційне числення, а в чем -то відрізняється від них обох.
Запити в мові SQL формулюється у вигляді табличних виразів,які потенційно можуть мати дуже високий ступінь складності.
6.1.
Приклади.
> Для всіх деталей вказати номер і вага в грамах
SELECT PP #, P. WEIGHT * 454 AS GMWT
FROM P;
Специфікація AS GMWT вводить відповідне ім'я резул?? тірующего стовпця.
Таким чином, дві колонки результуючої таблиці будуть називатися P # і
GMWT. Якби специфікація AS GMWT була опущена, то відповідний стовпець був би фактично безіменним. Відзначимо, що хоча в подібних випадках правила мови SQL насправді не вимагають від користувача зазначення імені результуючого стовпця.
> Вибрати інформацію про всіх парах постачальників і деталей, що знаходяться в одному місті
У мові SQL існує кілька способів формулювання цього запиту.
Наведемо три найпростіших.
1. SELECT S. *, PP #, P. NAME, P. COLOR, P. WEIGHT
FROM S, P
WHERE S. CITY = P. CITY;
2 . S JOIN P USING CITY;
3. S NATURAL JOIN P;
Результатом в кожному випадку буде природне з'єднання таблиць S і P (по атрибуту міста CITY).
Перша формулювання заслуговує більш докладного обговорення. Саме один із трьох запропонованих варіантів є допустимою в первісній версії мови SQL (явна операція JOIN була додана в стандарт SQL/92).
Концептуально можна розглядати реалізацію цієї версії запиту в такий спосіб.
. По-перше, після виконання пропозиції FROM ми отримуємо декартовій твір S TIMES P. (Строго кажучи, перед обчисленням твори слід було б подбати про перейменування стовпців. Для простоти ми цього не робимо.)
. По-друге, після виконання пропозиції WHERE ми отримуємо вибірку з цього твору, в якій два значення атрибуту CITY в кожному рядку рівні (інакше кажучи, виконано підключення таблиць постачальників і деталей по еквівалентності їх атрибутів міст).
. По-третє, після виконання пропозиції SELECT ми отримуємо проекцію вибірки по стовпцях, зазначеним у реченні SELECT. Кінцевим результатом буде природне з'єднання зазначених таблиць.
Отже, пропозиція FROM у мові SQL відповідає декартову твору, пропозиція WHERE - операції вибірки, а спільне застосування пропозицій SELECT-FROM-WHERE - проекції вибірки твори.
7 . Висновок.
Ми розглянули реляційне числення, альтернативне реляційноїалгебри.
Зовні два підходи дуже відрізняються: числення має описовийхарактер, тоді як характер алгебри - що пропонує, але на більш низькомурівні вони є одне і те ж, оскільки будь-які висловиобчислення можуть бути перетворені в семантично еквівалентні виразиалгебри і навпаки.
Реляційне числення існує у двох версіях: численнякортежів та обчислення доменів. Основна відмінність між ними полягає в тому,що змінні обчислення кортежів змінюються на відносинах, а змінніобчислення доменів змінюються на доменах.
Вираз обчислення кортежів складається з прототипу кортежу інеобов'язкового пропозиції WHERE, що містить логічне вираження абоформулу WFF ( «правильно побудовану формулу»). Подібна формула WFF можевключати квантори (EXISTS і FORALL), вільні і пов'язані посилання назмінні, логічні (булеві) оператори (AND, OR, NOTі ін) і т.д. Кожнавільна змінна, яка зустрічається у формулі WFF, також повинна бутизгадана в прототипі кортежу.
Зауваження. Тут це питання явно
