5.2. Реляційне літочислення
Припустимо, що ми працюємо з базою даних, що володіє схемою СПІВРОБІТНИКИ (СОТР_НОМ, СОТР_ІМ'Я, СОТР_ЗАРП, ОТД_НОМ) і ВІДДІЛИ (ОТД_НОМ, ОТД_КОЛ, ОТД_НАЧ), і хочемо дізнатися імена та номери співробітників, 0 співробітників.
Якби для формулювання такого запиту використовувалася реляційна алгебра, то ми отримали б вираз алгебри, який читався б, наприклад, наступним чином:
виконати поєднання відносин СПІВРОБІТНИКИ та ВІДДІЛИ за умовою СОТР_НОМ = ОТД_НАЧ;
обмежити отримане ставлення за умовою ОТД_КОЛ > 50;
спроектувати результат попередньої операції на атрибут СОТР_ІМ'Я, СОТР_НОМ.
Ми чітко сформулювали послідовність кроків виконання запиту, кожен із яких відповідає однієї реляційної операції. Якщо ж сформулювати той самий запит з використанням реляційного обчислення, якому присвячується цей розділ, то ми отримали б формулу, яку можна було б прочитати, наприклад, таким чином: Видати СОТР_ІМ'Я та СОТР_НОМ для співробітників таких, що існує відділ з таким самим значенням ВІД_НАЧ і значенням ОТД_КОЛ великим 50.
У другому формулюванні ми вказали лише характеристики результуючого відношення, але нічого не сказали про спосіб його формування. У цьому випадку система має сама вирішити, які операції та в якому порядку потрібно виконати над відносинами СПІВРОБІТНИКИ та ВІДДІЛИ. Зазвичай кажуть, що формулювання алгебри є процедурною, тобто. що задає правила виконання запиту, а логічна - описової (або декларативної), оскільки вона лише описує властивості бажаного результату. Як ми вказували на початку лекції, насправді ці два механізми еквівалентні та існують не дуже складні правила перетворення одногоформалізму в іншій.
Кортежні змінні та правильно побудовані формули
Реляційне обчислення є прикладною гілкою формального механізму обчислення предикатів першого порядку. Базисними поняттями обчислення є поняття змінної з певною нею областю допустимих значень та поняття правильно побудованої формули, що спирається на змінні, предикати та квантори.
Залежно від того, що є областю визначення змінної, різняться обчислення кортежів та обчислення доменів. У обчисленні кортежів областями визначення змінних є відносини бази даних, тобто. допустимим значенням кожної змінної є кортеж певного відношення. У обчисленні доменів областями визначення змінних є домени, у яких визначено атрибути відносин бази даних, тобто. допустимим значенням кожної змінної є значення певного домену. Ми розглянемо докладніше обчислення кортежів, а кінці глави коротко опишемо особливості обчислення доменів.
На відміну від розділу, присвяченого реляційній алгебрі, у цьому розділі нам не вдасться уникнути використання деякого конкретного синтаксису, який ми формально визначати не будемо. Необхідні синтаксичні конструкції будуть вводитися за необхідності. У сукупності, синтаксис, що використовується близький, але не повністю збігається з синтаксисом мови баз даних QUEL, який довгий час був основною мовою СУБД Ingres.
Для визначення кортежної змінної використовується оператор RANGE. Наприклад, для того, щоб визначити змінну СПІВРОБІТНИК, областю визначення якої є відношення СПІВРОБІТНИКИ, потрібно вжити конструкцію
RANGE СПІВРОБІТНИК IS СПІВРОБІТНИКИ
Як ми вже говорили, з цього визначення випливає, що вБудь-який момент часу змінна СПІВРОБІТНИК представляє деякий кортеж відносини СПІВРОБІТНИКИ. При використанні кортежних змінних у формулах можна посилатися на значення атрибута змінної (це аналогічно тому, як, наприклад, при програмуванні мовою Сі можна послатися значення поля структурної змінної). Наприклад, для того, щоб послатися на значення атрибуту СОТР_ІМ'Я змінної СПІВРОБІТНИК, потрібно вжити конструкцію СПІВПРАЦЬ.СОТР_ІМ'Я.
Правильно побудовані формули (WFF - Well-Formed Formula) служать висловлювання умов, накладених на кортежні змінні. Основою WFF є прості порівняння (comparison), що є операцією порівняння скалярних значень (значень атрибутів змінних або літерально заданих констант). Наприклад, конструкція "СПІВРОБІТНИК. СОТР_НОМ = 140" є простим порівнянням. За визначенням, просте порівняння є WFF, а WFF, укладена у круглі дужки, є простим порівнянням.
Більш складні варіанти WFF будуються за допомогою логічних зв'язок NOT, AND, OR та IF. THEN. Тож якщо form - WFF, а comp - просте порівняння, то NOT form, comp AND form, comp OR form і IF comp THEN form є WFF.
Нарешті, допускається побудова WFF з допомогою кванторов. Якщо form - це WFF, у якій бере участь змінна var, конструкції EXISTS var (form) і FORALL var (form) представляють wff.
Змінні, що входять до 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) такий, що СОТР_ЗАРП задовольняє внутрішній умові порівняння. WFF FORALL СОТР2 (СОТР1.СОТР_ЗАРП > СОТР2.СОТР_ЗАРП) для поточного кортежу змінної СОТР1 приймає значення true в тому і тільки в тому випадку, якщо для всіх кортежів відношення СПІВРОБІТНИКИ (пов'язаних зі змінною СОТР2) значення атрибута .
Насправді, правильніше говорити не про вільні та пов'язані змінні, а про вільні та пов'язані входження змінних. Легко бачити, що якщо змінна var є пов'язаною у WFF form, то у всіх WFF, що включають цю, може використовуватися ім'я змінної var, яка може бути вільною або пов'язаною, але в будь-якому випадку не має жодного відношення до входження змінної var до WFF form. Ось приклад:
EXISTS СОТР2 (СОТР1.СОТР_ОТД_НОМ = СОТР2.СОТР_ОТД_НОМ)
FORALL СОТР2 (СОТР1.СОТР_ЗАРП > СОТР2.СОТР_ЗАРП)
Тут ми маємо два пов'язані входження змінної СОТР2 з зовсім різним змістом.
Розглянемо квантори докладніше. Почнемо зквантораіснуванняEXISTS. Розглянемо приклад:
EXISTSSPX(SPX.S# =SX.S#ANDSPX.P# = ‘P2’)
Існує кортеж відносиниSP, скажімоSPX, для якого значенняS# дорівнює якомусь значеннюSX.S#, а значення Р # дорівнює Р2.
Кожен екземпляр SPXв цьому прикладі пов'язаний. Окремий екземпляр SX вільний.
Квантор існування EXISTS визначається формально як повторюване OR (АБО). Іншими словами, якщо R - це відношення з кортежами Т1, Т2, ..., Тm; Т – це змінна кортежа, яка змінюється цьому плані; аf(T) – це формула WFF, у якій Т використовується як вільна змінна, то формула WFF
EXISTST(f(T) ) визначається рівносильно наступній формулі WFF:
False OR (f(T1)) OR … OR (f(Tm))
Зауважте, зокрема, що результатом обчислення цього виразу буде брехня, якщо відношення R порожнє.
Приклад. Нехай відношення R містить такі кортежі:
Для простоти припустимо, що компоненти кортежу можуть бути ідентифіковані за їх порядковою позицією, тому можна посилатися на них за допомогою індексного посилання T[i]. Тоді наступні вирази матимуть наведені нижче значення:
EXISTST(T[3] > 1) :true
EXISTS T (T[2] > 3) : false
EXISTS T (T[1] > 1 OR T[3] = 4) : true
Тепер розглянемоквантор спільнотиFORALL, навівши такий приклад:
FORALL PX (PX.COLOR = 'red')
Для всіх кортежів відношення Р, скажімо РХ, значення атрибутуCOLORу цих кортежах дорівнюєRed.
Два екземпляри у цьому прикладі пов'язані.
Так само, як EXISTS був визначений як повторюється АБО, квантор спільностіFORALLвизначається якповторюванеAND(І).Іншими словами, якщо R, Tif (T) такі ж, як розглядалися вище, тоформула WFF
FORALLT(f(T) ) визначається рівносильно наступній формулі WFF:
True AND (f(T1)) AND … AND (f(Tm) )
Зауважте, зокрема, що результатом обчислення цього виразу будеістина, якщо відношення Rпорожнє.
Приклад. Якщо відношення R містить ті самі кортежі, що і в попередньому прикладі, то наведені нижче вирази матимуть такі значення:
FORALL T (T[1] > 1) : false
FORALL T (T[2] > 1) : true
FORALL T (T[1] = 1 AND T[3] > 2) : true
Зауваження.Квантор FORALL включений у обчислення просто для зручності, він не є необхідним, тому що наведене нижче тотожність показує, що будь-яка формула WFF, яка використовує квантор FORALL, може бути завжди замінена еквівалентною формулою WFF, яка використовує квантор EXISTS:
FORALL x (f) NOT EXISTS x (NOT f)
(простіше кажучи, вираз «всі х, які задовольняють формулі f» - це те саме, що і «немає таких х, які б не задовольняли формулі f»).
Наприклад, твердження (справжнє)
«Для будь-якого цілого х існує ціле у, таке що у >x»рівносильно утвердженню«Не існує цілого х такого, що не існує цілого у, такого що у > ; х».