Реляційне літочислення

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-поставщики, кожен постачальник має унікальний номер (P.S#); ім'я (SNAME); значення рейтингу чи статусу (STATUS); місце розташування (CITY). Передбачається, кожен постачальник знаходиться лише щодо одного місті. > P-детали, в кожного виду деталі є унікальний номер (P#); назва деталі (PNAME); колір (COLOR); вагу (WEIGHT); місто, де зберігається цей вид деталей (CITY). Кожен до окремого виду деталі має сенс тільки один колір і зберігається складі тільки одного місті. > SP-поставки, служить в організацію логічного зв’язку двох інших відносин. Наприклад, перший рядок відносини SP пов’язує постачальника з номером ‘S1' зі ставлення P. S із відповідною деталлю, має номер ‘P1' щодо P, тобто. представляє факт поставки деталей типу ‘P1' постачальником з номером ‘S1' (і навіть вказує кількість деталей-300 штук). Отже, кожна постачання характеризується номером постачальника (P.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'». Алгебраїчна версія цього запиту виглядає приблизно так:. Спочатку виконати з'єднання відносини постачальників P. S й стосунку поставок SP по атрибута P. S#.. Далі вибрати з результату цього сполуки кортежі з номером деталі ‘P2'.. І, нарешті, виконати для результату цієї вибірки операцію проекції по атрибутам P. S# і CITY. Той самий запит в термінах реляционного обчислення формулюється приблизно так:. Одержати атрибути P. 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, котру змінюють на відношенні, представляє собою поточне значення перемінної - відносини P. S (оператор RANGE — оператор визначення цієї перемінної). Оператор RETRIEVE означає таке: «До кожного можливого значення перемінної SX вибирати компонент P. 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 у значенні параметра V. A є вільною не більше цього параметра.. Якщо посилання зміну V є вільною у певній вираженні exp, ця посилання буде також вільної у кожному вираженні exp', безпосередньо що містить вираз exp як подвыражение, за умови що у натуральному вираженні exp' не вводиться квантор, зв’язуючий зміну V. Наведемо кілька прикладів формул WFF, містять перемінні кортежів.. Прості порівняння SX. S# = P. S# (‘S1') SX. S# = SPX. S# SPX. P#? PX. P#.

Тут усе посилання перемінні SX, PX і SPX є свободными.

. Логічні висловлювання з простих порівнянь PX. WEIGHT < WEIGHT (15.5) OR PX. CITY = ‘Rome' 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), такий, котрій значення атрибута P. 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™.

Зокрема, зверніть увагу, що й ставлення R порожній (тобто. m=0), то результатом обчислення даного висловлювання буде значення ложь.

Розглянемо за приклад ставлення r, що містить такі кортежи.

(1, 2, 3).

(1, 2, 4).

(1, 3, 4).

Для простоти припустимо, що три атрибута, які йдуть за порядку зліва направо, мають імена A, B і З й кожен із атрибутів має тип INTEGER. Тоді приведені нижче висловлювання матимуть зазначені значения.

EXISTS V (V.C>1): true.

EXISTS V (V.B>3): false.

EXISTS V (V.A>1 OR V. C = 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™.

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

Як приклад розглянемо ставлення R, що містить самі кортежі, що у попередньому прикладі. Тоді приведені нижче висловлювання будуть мати зазначені значения.

FORALL V (V.A>1): false.

FORALL V (V.B>1): true.

FORALL V (V.A = 1 and V. C>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')).

Зверніть увагу до використання імені перемінної кортежу в прототипі кортежу. Цей приклад є сокращённой записом наступного висловлювання. (SX.S#, SX.NAME, SX. STATUS, SX. CITY) WHERE EXISTS SPX (SPX.S# = SX. S# AND.

SPX.P# = P# (‘P2')) Той самий приклад вирішений засобами реляційної алгебри така ((SP JOIN P. 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) {P.S#} JOIN P. 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 — перемінні кортежів, отримують свої значення з відносин P. 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 (J.J#, 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) > Визначити загальна кількість поставлених деталей SUM (SPX, QTY) AS GRANDTOTAL) > Визначити номери і ваги в грамах всіх типів деталей, вагу яких перевищує 10 000 г (PX.P#, PX. WEIGHT * 454 AS GMWT).

WHERE PX. WEIGHT * 454 > WEIGHT (10 000) Зверніть увагу, що специфікація AS GMWT в прототипі кортежу дає ім'я відповідному атрибута результату. Тому таке ім'я недоступно від використання у пропозиції WHERE і вираз PX. WEIGHT * 454 має бути вказано у двох местах.

5. Літочислення доменов.

Як зазначалося в «Запровадження», реляционное літочислення, орієнтоване на домени (чи літочислення доменів), відрізняється від обчислення кортежів тим, що у ньому замість змінних кортежів використовується перемінні доменів, тобто. перемінні, приймаючі свої значення межах домену, а чи не відносини. З практичного погляду більшість очевидних різниці між версіями обчислення доменів і обчислення кортежів грунтується у тому, що версія для доменів підтримує форму параметра, який ми називати умовою приналежності. Загалом вигляді умова приналежності можна записати так.

R (пара, пара, …).

Тут Rім'я відносини, а кожен параметр пара має вигляд A: v, де A — атрибут відносини R, а v — ім'я перемінної домену чи буквальний. Перевірка умови дає значення істина тоді й тільки тоді, як у поточному значенні відносини R існує кортеж, має зазначені значення для зазначених атрибутів. Наприклад, розглянемо результат обчислення наступного выражения.

SP (P.S#: P. S# (‘S1'), P#: P# (‘P1')).

Він мати значення істина тоді й тільки тоді, як у відношенні SP існуватиме кортеж багатозначно атрибута P. S#, рівним ‘S1', і значенням атрибута P#, рівним ‘P1'. Аналогічно умова принадлежности.

SP (P.S#: SX, P#: PX) приймає значення істина тоді й тільки тоді, як у відношенні SP існує кортеж багатозначно атрибута P. S#, еквівалентним поточному значенням перемінної домену PX (знов-таки, якій ні было).

Далі матимемо на увазі існування наступних змінних доменов.

Домен.

Змінна домену P. 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 P. S (P.S#: SX).

SX WHERE P. S (P.S#: SX, CITY: ‘London') (SX, CITYX) WHERE P. S (P.S#: SX, CITY: ‘London').

AND SP (P.S#: SX, P#: P# (‘P2')).

(SX, PX) WHERE P. S (P.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.

(P.S (P.S#: SX, CITY: CITYZ) AND.

P.S (P.S#: SY, CITY: CITYZ) AND.

SX < SY) > Визначити імена постачальників по крайнього заходу однієї червоною деталі NAMEX WHERE EXISTS SX EXISTS PX.

(P.S (P.S#: SX, SNAME: NAMEX).

AND SP (P.S#: SX, P#: PX).

AND P (P#: PX, COLOR: COLOR (‘Red'))) > Вибрати імена постачальників всіх типів деталей NAMEX WHERE EXISTS SX (P.S (P.S#: SX, SNAME: NAMEX).

AND FORALL PX (IF P (P#: PX).

THEN SP (P.S#: SX, P#: PX).

END IF).

6. Кошти мови SQL.

Як мовилося раніше розділ «Порівняльний аналіз реляционного обчислення і реляційної алгебри», основою реляционного мови може бути покладено як реляційна алгебра, і реляционное літочислення. Що й казати належить основою мови SQL? Відповіддю буде №частково і те, й те, а частково ні те, ні інше…". Коли мову SQL лише розроблявся, передбачалося що він відрізнятися як від реляційної алгебри, і від реляционного обчислення. Справді, саме цим мотивувалося запровадження у мову конструкції IN. Однак згодом з’ясувалося, що мова SQL потребує певних засобах як реляційної алгебри, і обчислення, й тому він було розширено для включення цих функцій. На сьогодні ситуацію складається в такий спосіб, що мова SQL щось нагадує реляционную алгебру, щось на реляционное літочислення, а ніжто відрізняється від нього обоих.

Запити у мові SQL формулюється як табличных висловів, котрі потенційно може мати дуже дорогу ступінь сложности.

6.1. Примеры.

> Всім деталей вказати номер і ваги в грамах SELECT P. P#, P. WEIGHT * 454 AS GMWT FROM P; Специфікація AS GMWT вводить відповідне ім'я результуючого шпальти. Отже, два шпальти результуючої таблиці називатимуться P# і GMWT. Якби специфікація AS GMWT була опущене, то відповідний стовпець було б фактично безіменним. Зазначимо, хоча у випадках правила мови SQL насправді не вимагає від користувача вказівки імені результуючого шпальти. > Вибрати інформацію про парах постачальників і деталей, що у одному місті У мові SQL є кілька способів формулювання цього запиту. Наведемо три найпростіших. 1. SELECT P. S.*, P. P#, P.NAME, P. COLOR, P.WEIGHT.

FROM P. S, P.

WHERE S. CITY =P.CITY; 2. P. S JOIN P USING CITY; 3. P. S NATURAL JOIN P; Результатом у разі буде природне з'єднання таблиць P. S і P (по атрибута міста CITY). Перша формулювання заслуговує докладнішого обговорення. Саме одне з трьох запропонованих варіантів є припустимою в початкової версії мови SQL (явна операція JOIN була додана в стандарт SQL/92). Концептуально так можна трактувати реалізацію версії запиту наступним образом.

. По-перше, після виконання пропозиції FROM ми маємо декартово твір P. S TIMES P. (У принципі, перед обчисленням твори було б дбатиме про перейменування шпальт. Для простоти ми сьогодні цього не делаем.).

. По-друге, після виконання пропозиції WHERE ми маємо вибірку з твору, у якій два значення атрибута CITY у кожному рядку рівні (інакше кажучи, виконано з'єднання таблиць постачальників і деталей по еквівалентності їх атрибутів городов).

. По-третє, після виконання пропозиції SELECT ми маємо проекцію вибірки по столбцам, зазначених у пропозиції SELECT. Кінцевим результатом буде природне з'єднання зазначених таблиць. Отже, пропозицію FROM у мові SQL відповідає декартову твору, пропозицію WHERE — операції вибірки, а спільне застосування пропозицій SELECT-FROM-WHERE — проекції вибірки произведения.

7.

Заключение

.

Ми розглянули реляционное літочислення, альтернативне реляційної алгебрі. Зовні два підходу дуже різні: літочислення має описовий характер, тоді як характер алгебри — який наказував би, але нижчому рівні, вони є одним і те, оскільки будь-які висловлювання обчислення може бути перетворені на семантично еквівалентні висловлювання алгебри і наоборот.

Реляционное літочислення існує у двох версіях: літочислення кортежів і літочислення доменів. Основне різницю між ними у тому, що перемінні обчислення кортежів змінюються на відносинах, а перемінні обчислення доменів змінюються на доменах.

Вислів обчислення кортежів складається з прототипу кортежу і необов’язкового пропозиції WHERE, що містить логічне вираз чи формулу WFF («правильно побудовану формулу»). Така формула WFF може включати кванторы (EXISTS і FORALL), що вільні та пов’язані посилання перемінні, логічні (булевы) оператори (AND, OR, NOTи ін.) тощо. Кожна вільна змінна, що зустрічається у формулі WFF, повинен бути згадана в прототипі кортежа.

Зауваження. Тут це запитання року порушувалося, але висловлювання реляционного обчислення призначені, сутнісно, тим ж цілей, як і висловлювання реляційної алгебры.

Приклад було показано[1], як алгоритм редукції Кодда може використовуватися для перетворення довільного висловлювання реляционного обчислення в еквівалентну вираз реляційної алгебри, в такий спосіб готуючи грунт вибору можливої стратегії реалізації обчислення. Знову звернувшись стосовно питання про реляційної повноти, ми коротко обговорили, яким чином можна довести, що деякий мову L є повним у тому смысле.

З іншого боку, тут обговорювалося, як і розширити літочислення кортежів з підтримки певних обчислювальних можливостей (аналогічні можливості у реляційної алгебрі забезпечуються операціями EXTEND і SUMMARIZE). Потім нас було представлено стисле введення у літочислення доменів відзначено (щоправда, без спроби довести це), що його є також реляционно повним. Отже, літочислення кортежів, літочислення доменів і реляційна алгебра эквивалентны.

І, насамкінець, нашому увазі було представлено огляд відповідних коштів мови SQL. Мова SQL є своєрідним сумішшю реляційної алгебри і обчислення (кортежей.

). Наприклад, у ньому є прямий підтримка таких операцій реляційної алгебри, як з'єднання й «об'єднання, але водночас із цим використовуються перемінні кортежів і квантор існування з реляционного обчислення. SQL — запит є табличное вираз. Зазвичай цю конструкцію містить єдине вираз вибірки, проте підтримуються й різні типи явних висловів операцій сполуки (JOIN), причому висловлювання з'єднання та вибірки можуть комбінуватися довільним чином із допомогою операторів UNION, INTERSECT і EXCEPT. Також згадувалося про можливість використання пропозиції ORDER BY визначення упорядкованості рядків таблиці, що є результатом обчислення даного табличного висловлювання (будь-якого вида).

Зокрема, були описані такі компоненти висловів вибірки.. Базове пропозицію SELECT, зокрема використання ключового слова DISTINCT, скалярних висловів, запровадження імен результирующих шпальт і пропозиції SELECT *. Пропозиція FROM, включаючи використання змінних кортежів. Пропозиція WHERE, включаючи використання оператора EXISTS. Пропозиція GROUP BY і HAVING, включаючи використання узагальнюючих функцій COUNT, SUM, AVG, MAX і MIN. Використання подзапросов у пропозиціях SELECT, FROM і WHERE.

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

8.

Список литературы

.

1) «Введення у системи баз даних» К.Дж.Дейт, видавництво «Пітер», СПб.

2002 г.

2) «Бази даних: моделі, розробка, реалізація» підручник під редакцией.

Т.Карповой, видавництво «Пітер», СПб 2001 г.

3) «Системи баз даних» Г. Гаремо-Малино, Москва 2003 г.

8.

Список литературы

.

4) «Введення у системи баз даних» К.Дж.Дейт, видавництво «Пітер», СПб.

2002 г.

5) «Бази даних: моделі, розробка, реалізація» підручник під редакцией.

Т.Карповой, видавництво «Пітер», СПб 2001 г.

6) «Системи баз даних» Г. Гаремо-Малино, Москва 2003 г.

———————————- [1] Порівняльний аналіз реляционного обчислення і реляційної алгебры.