НОУ ІНТУІТ, Лекція, Базисні засоби маніпулювання реляційними даними реляційне обчислення

Квантори, вільні та пов'язані змінні

При побудові WFF допускається використання кванторів існування (EXISTS) та загальності (FORALL). Якщо form – це WFF , у якій бере участь змінна var , то конструкції EXISTS var (form) і FORALL var (form) є WFF . За визначенням, формула EXISTS var (form) приймає значення true в тому і тільки в тому випадку, якщо в області визначення змінної var знайдеться хоча б одне значення (кортеж), для якого WFF form набуває значення true . Формула FORALL var (form) приймає значення true якщо для всіх значень змінної var з її області визначення WFF form приймає значення true .

Змінні, що входять до WFF, можуть бути вільними або пов'язаними. За визначенням, всі змінні, що входять до WFF, при побудові якої не використовувалися квантори, є вільними. Фактично це означає, що якщо для якогось набору значень вільних кортежних змінних при обчисленні WFF отримано значення true , то ці значення кортежних змінних можуть входити в результуюче відношення. Якщо ж ім'я змінної використано відразу після квантора при побудові WFF виду EXISTS var (form) або FORALL var (form) , то в цій WFF і у всіх WFF побудованих за її участю var є пов'язаною змінною . Це означає, що така змінна не видно за межами мінімальної WFF, що зв'язала цю змінну. При обчисленні значення такої WFF використовується не одне значення пов'язаної змінної, а вся область визначення.

Нехай тут і далі в цьому розділі СЛУ1 і СЛУ2 є дві кортежні змінні , визначені щодо СЛУЖАЮЧІ . Тоді WFF

EXISTS СЛУ2 (СЛУ1.СЛУ_ЗАРП >СЛУ2.СЛУ_ЗАРП)

для поточного кортежу змінної СЛУ1 приймає значення true в тому і тільки в тому випадку, якщо в усьому відношенні СЛУЖАЮЧІ знайдеться такий кортеж (асоційований зі змінною СЛУ2 ), щоб значення його атрибуту СЛУ_ЗАРП задовольняло внутрішній умові порівняння. Легко бачити, що ця формула набуває значення true тільки для тих значень кортежної змінної СЛУ1, які відповідають службовцям, які не одержують мінімальної зарплати. Відповідна множина кортежів показано на рис. 5.2a (для тіла відносини СЛУЖАЮЧІ з рис. 5.1).

базисні

Правильно побудована формула

FORALL СЛУ2 (СЛУ1.СЛУ_ЗАРП >= СЛУ2.СЛУ_ЗАРП)

для поточного кортежу змінної СЛУ1 приймає значення true в тому і тільки в тому випадку, якщо для всіх кортежів відношення СЛУЖАЮЧІ (пов'язані зі змінною СЛУ2) значення атрибуту СЛУ_ЗАРП задовольняють умові порівняння. Знову легко бачити, що формула набуває значення true лише для тих значень кортежної змінної СЛУ1 , які відповідають службовцям, які отримують максимальну зарплату 3 Вправа для читачів. Чому в першій формулі (з EXISTS) використано умову СЛУ1.СЛУ_ЗАР > СЛУ2.СЛУ_ЗАРП , а другий формулі (з FORALL ) - СЛУ1.СЛУ_ЗАРП = СЛУ2.СЛУ_ЗАРП ? . Відповідна множина кортежів показано на рис. 5.2b.

Насправді, правильніше говорити не про вільні і пов'язані змінні, а про вільні і пов'язані входження змінних. Якщо змінна var є пов'язаною у WFF form , то у всіх WFF , що включають form , поза form може використовуватися входження того ж імені змінної var , яке може бути вільним або пов'язаним, але в будь-якому випадку не має жодного відношення до входження змінної var до WFF form . Ось приклад:

Ця формула набуває значення true тількидля тих значень змінної СЛУ1, які відповідають службовцям, що беруть участь у проектах з більш ніж одним учасником, причому всі учасники проекту отримують одну й ту саму зарплату. Тут ми маємо два пов'язані входження змінної СЛУ2 з зовсім різним змістом. Грубо кажучи, для поточного значення змінної СЛУ1 змінна СЛУ2 двічі "пробігає" свою область визначення - перший раз при обчисленні частини формули з квантором існування, а другий при обчисленні частини з квантором загальності. До речі, до того ж результату наведе формула з одним квантором загальності виду:

Легко помітити, що квантори можна трактувати як булевські функції (функції, що набирають значення true або false ) над безліччю значень пов'язаної кортежної змінної . З тим же успіхом можна ввести в реляційне літочислення числові функції над множинами , такі, як MIN (мінімальне значення), MAX (максимальне значення), AVG (середнє значення) і т.д.

У цьому випадку можна було б написати, наприклад, WFF

СЛУ1.СЛУ_ЗАРП > MIN СЛУ2.СЛУ_ЗАРП (СЛУ1.ПРО_НОМ = СЛУ2.ПРО_НОМ)

у сфері істинності якої містяться всі кортежі відносини СЛУЖАЮЩІ , відповідні тим службовцям, які отримують зарплатню, перевищує мінімальну зарплату службовців, що у тому проекте. Зрозуміло, що для отримання результуючого відношення можна інтерпретувати формулу таким же чином, як у випадку наявності кванторів, що обговорювалося вище.

Цільові списки та висловлювання реляційного обчислення

Отже, WFF забезпечують засоби формулювання умови вибірки із відносин БД. Щоб можна було використовувати літочислення для реальної роботи з БД, потрібен ще один компонент, який визначає набір та імена атрибутів результуючого відношення. Цей компонент називаєтьсяцільовим списком (target list).

Цільовий список будується з цільових елементів, кожен з яких може мати такий вигляд:

  • var.attr , де var – ім'я вільної змінної відповідної WFF , а attr – ім'я атрибута відношення, у якому визначена змінна var ;
  • var , що еквівалентно наявності підписку var.attr1, var.attr2, . var.attrn , де 1, attr2, . attrn> включає імена всіх атрибутів визначального відношення;
  • new_name = var.attr; new_name - нове ім'я відповідного атрибуту результуючого відношення.

Останній варіант потрібен у тих випадках, коли у WFF використовується кілька вільних змінних з однаковою областю визначення. Фактично застосування цільового списку до області істинності WFF еквівалентно дії алгебраїчної операції проекції, а останній з наведених варіантів є деяким різновидом алгебраїчної операції перейменування атрибуту.

Виразом реляційного обчислення кортежів називається конструкція виду target_list WHERE WFF. Значенням висловлювання є ставлення, тіло якого визначається WFF , а безліч атрибутів та його імена – цільовим списком .

Як простий приклад покажемо вираження реляційного обчислення кортежів , результат якого збігається з результатом операції СЛУЖАЮЧІ DIVIDE BY НОМЕРА_ПРОЕКТІВ (рис. 3.11 з лекції 3):

Звичайно, результатом цього виразу є ставлення