Вільні і зв’язані змінні області значень

Кожне посилання на змінну області значень (в певному контексті, зокрема в деякій правильно побудованої формулі) є або вільної, або повязаної Спочатку пояснимо це твердження в чисто синтаксичних термінах в даному підрозділі, потім продовжимо обговорення його семантичного значення в наступних підрозділах

Нехай v – мінлива області значень, а р і q – правильно побудовані формули

Тоді маємо наступне

■ Посилання на змінну v в правильно побудованої формулі типу NOT p свобод ни або повязані в залежності від того, чи вільні або повязані вони у формулі р Посилання на змінну V в правильно побудованої формулою типу (р AND q) і (р OR q) вільні або повязані, відповідно, в залежності від того, свобод ни або повязані вони в формулахр і q

■ Посилання на змінну V, які є вільними в правильно побудований ної формулою р, повязані в правильно побудованих формулах типу EXISTS V (p) І FORALL V (p) Інші посилання на змінні області значень у формулі р яв ляють вільними або звязаними в правильно побудованих формулах типу EXISTS V (p) і FORALL v (p) відповідно з тим, вільні або повязані вони у формулі р

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

■ Єдина посилання на змінну V в значенні параметра &ltrange    var name&gt V є вільною в межах цього параметра &ltrange var name&gt.

■ Єдина посилання на змінну V в значенні параметра &ltrange  attribute ref&gt V А є вільною в межах цього параметра &ltrange a t tribu te ref&gt.

■ Якщо посилання на змінну V є вільною в деякому виразі ехр,

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

Наведемо кілька прикладів правильно побудованих формул, які містять посилання на змінні області значень

■&nbsp&nbsp&nbsp Прості порівняння

SXS# = S# {S1) SXS# = SPXS# SPXP# PXP#

Тут всі посилання на змінні SX, РХ і SPX є вільними

■&nbsp&nbsp&nbsp&nbsp Прості операції порівняння, обєднані за допомогою логічних виразів

РХWEIGHT < WEIGHT (15.5) AND PX.CITY = 'Oslo' NOT (SX.CITY = 'London')

SXS# = SPXS# AND SPXP# ≠ PXP#

PXCOLOR = COLOR (Red) OR PXCITY = London

Тут також всі посилання на змінні sx, РХ і SPX є вільними

■&nbsp&nbsp&nbsp&nbsp Правильно побудовані формули з кванторами

EXISTS   SPX   (   SPXS#   =   SXS#   AND   SPXP#   =

P#    (P2)    ) FORALL   PX   (   PXCOLOR   =   COLOR (Red)    )

У цих прикладах посилання на змінні SPX і РХ є повязаними, а посилання на змінну SX залишається вільною Детальніше дані приклади описані нижче, в підрозділі Квантори.

Квантори

Існує два квантора2: EXISTS і FORALL Квантор EXISTS є квантором існування, a FORALL – квантором загальності По суті, якщо вираз р – правильно побудована формула, в якій змінна v вільна, то вираження

EXISTS V (р

) І

FORALL V (р)

також є допустимими правильно побудованими формулами, але мінлива V в них обох повязана Перша формула означає наступне: Існує щонайменше одне значення змінної V, при якому формула р стає істинної . Друга формула означає наступне: Формула р єістинної при всіх значеннях змінної V . Припустимо, наприклад, що змінна V приймає значення з безлічі Члени

2 Термін квантор походить від латинського слова quantum, яке, взагалі кажучи, означає кількість. Замість ключових слів EXISTS і FORALL, відповідно, часто використовуються символи 3 (зворотне Е) і V (перевернуте А)

сенату США у 2003 році , і припустимо також, що вираз р – наступна правильно побудована формула: V-жінка (Зрозуміло, ми не намагаємося використовувати тут формальний синтаксис) Тоді вираз EXISTS V (p) буде допустимої правильно побудованої формулою, що має значення TRUE {Істина) вираз FORALL v (p) також буде допустимої правильно побудованої формулою, але її значення дорівнюватиме FALSE {Брехня), оскільки не всі члени сенату-жінки

Тепер розглянемо квантор існування EXISTS уважніше Ще раз звернемося до прикладу, наведеному в кінці попереднього розділу

EXISTS SPX ( SPXS# = SXS# AND SPXP# = P# (P2) )

З наведених вище міркувань випливає, що ця правильно побудована формула може бути прочитана наступним чином

У поточному значенні змінної відносини SP існує кортеж (скажімо, SPX), такий, що значення атрибута S# в цьому кортежі дорівнює значенню атрибута SX S # (яким би воно не було), а значення атрибута Р # в кортежі SPX одно Р2

Кожне посилання на змінну SPX в цьому прикладі є повязаною Єдина посилання на змінну SX вільна

Формально квантор існування EXISTS визначається як повторно застосовувана операція OR (АБО) Іншими словами, якщо, по-перше, r – це відношення з кортежами tl, t2, ., Tm, по-друге, V-це змінна області значень, що приймає значення з даного відношення, і, в третіх, p (V) – це правильно побудована формула, в якій змінна V використовується як вільна змінна, то правильно побудована формула виду

EXISTS V (р (V))

еквівалентна наступній правильно побудованої формулі

FALSE OR р (tl} OR .. OR p ™

Зокрема, слід зазначити, що якщо відношення R пусте (тобто т = 0), то дане вираження приймає значення FALSE

Розглянемо як приклад ставлення r, що містить тільки наступні кортежі (для спрощення тут не дотримуються наші звичайні вимоги до синтаксису)

(     1,     2 ,

3   )   (   1 ,

2,   4   )   (

1,     3,     4

)

Припустимо, що три атрибута, що йдуть по порядку зліва направо, як показано вище, мають імена, відповідно, А, в і з і кожен з цих атрибутів має тип INTEGER Тоді наведені нижче правильно побудовані формули будуть мати зазначені значення

EXISTS V ( VC &gt 1 )                                           : TRUE EXISTS V ( VB &gt 3 )                                           : FALSE EXISTS V ( VA &gt 1 OR VC = 4 ) : TRUE

Тепер розглянемо квантор загальності FORALL, ДЛЯ чого повернемося до відповідного прикладом, наведеним у кінці попереднього розділу

FORALL РХ (РХCOLOR = COLOR (Red))

Ця правильно побудована формула може бути прочитана наступним чином

Для всіх кортежів РХ, скажімо, в поточному значенні змінної відносини Р,

значення атрибута COLOR у кортежі РХ одно Red

Обидві посилання на змінну РХ в цьому прикладі повязані

Подібно до того, що квантор EXISTS був визначений як результат багаторазового застосування операції OR, квантор існування FORALL визначається як результат багаторазового застосування операції AND (І) Іншими словами, якщо позначення r, V і р (V) мають той же зміст, що і в наведеному вище визначенні квантора EXISTS, TO правильно побудована формула виду

FORALL V (р (V))

рівносильна наступній правильно побудованої формулі

TRUE   AND  p    (   tl   )   AND       AND  p    (   tm   )

Зокрема, слід зазначити, що якщо відношення r пусте, то даний вираз приймає значення TRUE Як приклад розглянемо відношення R, що містить ті ж кортежі, що і в попередньому прикладі, що стосується квантора EXISTS Тоді наведені нижче вирази будуть мати зазначені значення

FORALL V ( VA &gt 1 )                                           : FALSE FORALL V ( VB &gt 1 )                                            : TRUE FORALL V ( VA = 1 AND VC &gt 2 ) : TRUE

Примітка Обидва квантора підтримуються просто для зручності З точки зору логіки немає необхідності підтримувати обидва квантора, так як наведене нижче тотожність показує, що будь-який з них може бути визначений в термінах іншого

FORALL V (р) = NOT EXISTS V ( NOT p )

Неформально кажучи, вираз всі значення V задовольняють формулою р є не що інше, як і вираз немає таких значень V, які б не задовольняли формулою р. Наприклад, (істинне) твердження Для будь-якого цілого х існує ціле у, таке, що у> х рівносильно твердженням Не існує цілого х, такого, що не існує цілого у, такого, що у> х (Інакше кажучи, не існує найбільшого цілого числа) Однак одні твердження простіше виразити в термінах квантора FORALL, а інші – в термінах квантора EXISTS вірніше, якщо один з кванторів недоступний, то іноді виникає необхідність використовувати подвійне заперечення (як показано в попередньому прикладі) Тому з точки зору практики бажано, щоб підтримувалися обидва квантора

Додаткові відомості про вільних і повязаних змінних

Припустимо, що змінна х приймає значення з безлічі всіх цілих чисел,

і розглянемо наступну правильно побудовану формулу

EXISTS х (х> 3)

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

EXISTS у (у> 3)

семантично ідентична формулою, наведеною раніше

Тепер розглянемо іншу формулу WFF

EXISTS х (х> 3) AND x < Про

Тут є три посилання на змінну х, позначають дві різні змінні Перші два посилання повязані і могли б бути замінені посиланням на іншу змінну у без зміни загального змісту формули Третя посилання на змінну х вільна і не може бути безперешкодно змінена Таким чином, з двох наведених нижче формул WFF перша еквівалентна розглянутій вище формулою, а другий-ні

EXISTS У (У> 3) AND х

< Про EXISTS у (у> 3) AND у < Про

Крім того, заслуговує на увагу те, що остаточне значення первісної правильно побудованої формули не може бути визначено, якщо не відомо значення, вказане за допомогою посилання на вільну змінну х На відміну від цього, правильно побудована формула, в якій всі посилання на змінні є повязаними, завжди має певне значення, TRUE АБО FALSE

Додаткова термінологія Правильно побудована формула, в якій всі змінні звязані, називається закритою правильно побудованої формулою Відкрита правильно побудована формула- це формула, яка не є закритою, тобто така формула, яка містить принаймні одне посилання на вільну змінну Іншими словами, використовуючи термінологію, введену в розділі 3, закрита правильно побудована формула – це висловлювання, а відкрита правильно побудована – це предикат, який не є висловленням (До речі, слід зазначити, що висловлення- теж предикат, вірніше, вироджений окремий випадок предиката, в якому безліч формальних параметрів є порожнім)

Реляційні операції

Параметр &ltrelation op inv&gt не зовсім доречний в контексті обчислення – більш підходящим варіантом був би параметр &ltrelation def&gt. Однак ми будемо використовувати саме перший варіант для узгодженості з позначеннями в главі 7 Як нагадування наведемо його синтаксис

&ltrelation  op inv&gt

::=   &ltproto  tuple&gt  [  WHERE  &ltbool  exp&gt  ]

&ltproto   tuple&gt

:: = .. визначення див в тексті даної глави

Нагадуємо також, що наступні синтаксичні правила тепер кілька спрощені

■ Всі номери змінні області значень в параметрі &ltproto  tuple&gt по винні бути вільними в межах значення цього параметра з позначенням корті жа-прототипу

■ Посилання на змінну області значень в конструкції WHERE може бути сво бодні тільки в тому випадку, якщо посилання на цю ж змінну (обовязково сво Бодня) присутня у відповідному значенні параметра&ltproto  tuple&gt.

Наприклад, наступний вираз є допустимим значенням параметра

&ltrelation op inv&gt (Визначити номери постачальників, що знаходяться в Лондоні)

SXS#  WHERE  SXCITY  =   London

Тут посилання на змінну SX в кортежі-прототипі є вільною Посилання на змінну SX в конструкції WHERE також вільна, оскільки посилання на ту ж змінну області значень (обовязково вільну) є і в значенні параметра

&ltproto  tuple&gt цього виразу

Наведемо інший приклад (Отримати імена постачальників деталі з номером Р2; см

обговорення квантора існування EXISTS в підрозділі Квантори цього розділу)

SXSNAME WHERE EXISTS SPX ( SPXS# = SXS# AND SPXP# = P# (P2) )

Тут всі посилання на змінну SX є вільними, тоді як всі посилання на змінну SPX (в конструкції WHERE) є повязаними, як і повинно бути, оскільки на них немає посилань у кортежі-прототипі

Інтуїтивно ясно, що результатом виконання операції, заданої параметром

&ltrelation op inv&gt, буде відношення, що містить всі можливі значення кортежів, що визначаються параметром&ltproto  tuple&gt,  для яких результат обчислення логічного виразу, заданого в конструкції WHERE параметром, приймає значення TRUE (ЯКЩО конструкція WHERE опущена, це еквівалентно вказівкою вираження WHERE TRUE) Зробимо деякі уточнення

■ Насамперед, кортеж-прототип – це розділений комами список елементів, укладений у фігурні дужки (але фігурні дужки можуть бути опущені, якщо розділений комами список містить тільки один елемент), кожен елемент якого є або посиланням на атрибут області значень (яка може включати конструкцію AS для введення нового імені атрибута), або просто імям змінної області значень Є й інші варіанти, але для спрощення обмежимося тільки цими двома, по крайней мере, до тих пір, поки не буде вказано інше Проте, зазначимо таке

а)

У цьому контексті імя змінної області значень найчастіше є просто скороченим позначенням розділеного комами списку посилань на атрибути, по одній для кожного атрибута того ставлення, з якого приймає значення дана змінна області значень

б) Посилання на атрибут області значень без конструкції AS по суті є скороченим позначенням посилання, що включає таку конструкцію, в якій нове імя атрибута збігається зі старим

300 Частина II Реляційна модель

Отже, без втрати спільності кортеж-прототип можна розглядати як розділений комами список посилань на атрибути у вигляді vi Aj AS Bj, укладений у фігурні дужки Зверніть увагу, що не всі посилання Vi, повідомимо, будуть різними, і не обовязково повинні відрізнятися один від одного всі посилання Aj, а посилання в j повинні бути різними

■ Нехай V1, V2, .., Vm – різні змінні області значень, присутствую щие в кортежі-прототипі, областями значень яких є, відповідно, відносини rl, r2, .., rm Припустимо, що r 1 , r2, , Rm – це нові відно сини, отримані після перейменування атрибутів в конструкції AS, ar – це декартовій твір відносин r 1 , r2, .., rm .

■ Нехай відношення r – це скорочення відносини r , яке задовольняє правиль але побудованої формулою в конструкції WHERE

Примітка Тут передбачається, що на попередньому кроці були також перейменовані атрибути, що згадуються в конструкції WHERE в іншому випадку правильно побудована формула в конструкції WHERE може не мати сенсу Але, як показано в наступному розділі, в запропонованому тут конкретному синтаксисі неоднозначність усувається не на підставі цього припущення, а з використанням уточнюючої точкової системи позначень

■ Кінцеве значення реляційної операції, заданої параметром &ltrelation op inv&gt, визначається як проекція відносини r по всім заданим атрибутам Bj

У наступному розділі буде наведено кілька прикладів подібних виразів

Джерело: Дейт К Дж, Введення в системи баз даних, 8-е видання: Пер з англ – М: Видавничий дім «Вільямс», 2005 – 1328 с: Ил – Парал тит англ

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*