18226

Реляційне числення. Мова Альфа

Реферат

Информатика, кибернетика и программирование

Реляційне числення. Мова Альфа Реляційне числення Кодда є одним із найважливіших наріжних каменів теорії реляційних моделей баз даних. У СУБД що існували до появи реляційного підходу було багато засобів для обробки даних і формулювання запитів. Основою для їх р

Украинкский

2013-07-07

87.5 KB

13 чел.

Реляційне числення. Мова “Альфа”

Реляційне числення Кодда є одним із найважливіших наріжних каменів теорії реляційних моделей баз даних. У СУБД, що існували до появи реляційного підходу, було багато засобів для обробки даних і формулювання запитів. Основою для їх розробки та впровадження виступали практичні потреби тої, чи іншої предметної області, або кількох областей. У дореляційну епоху не було створено теоретичного критерію стосовно повноти мовних засобів для формування запитів у межах певного класу мов. Ситуація у цьому розумінні видавалася досить складною: з одного боку множина запитів на основі природної мови (неформалізована область) і з іншого боку мовні засоби СУБД, тісно пов’язані з іноді досить складними структурами даних.

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

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

Для означення реляційного числення спочатку виберемо алфавіт :

V = V1 V2 V3  V4, де

V1 = {a; r; P; };  V2 = {; ; ; ; };  V3 = {=; ; ; ; ; };  V4 = {[; ]; (; ); ,; :};

Індекси  – це слова виду ... (m - штук), m = 0,1,2,...

Константи  – слова виду а... (m - штук), m = 0,1,2,...;  будемо позначати  am; a=a0;

Змінні  – слова виду r... (m - штук), m = 0,1,2,...;  будемо позначати   rm; Відзначимо, що кортежні змінні інтерпретуються кортежами значень.

Предикати (унарні)  – слова виду P... (m - штук), m = 0,1,2,...;  будемо позначати  Pm;

ці предикати інтерпретуються скінченними реляційними відношеннями.

Зрізи   – слова виду r...[...] (i та m - штук), і,m = 0,1,2,...; будемо позначати   ri[m] – зріз змінної ri  за m-м компонентом;

Далі з урахуванням раніш введених визначень та позначень специфікуємо наступні поняття:

Терми значень – слова виду Pi rj. Такий вираз вказує, що змінна rj приймає значення з реляції Ri, яке є інтерпретацією предиката Pi. За допомогою терма значень явно фіксується область значень змінної.

Терми зєднань – слова виду    , або   , де , -- зрізи, - константа, - бінарний предикат (порівняння).

 = {  =,  ≠, <,  >,  ≤,  ≥ }

Вони визначають умови з'єднання різних відношень.

 

Приклади термів зєднань:

r1[3] r2[1];  r1[2] = a ;

Правильно побудовані формули (ППФ)

  1.  Всі терми значень і терми зєднань є ППФ. Всі їх змінні – вільні.
  2.  Якщо FППФ, то FППФ. Змінні залишаються вільними.
  3.  Якщо F1 і F2 – ППФ і їх спільні змінні вільні у кожній з формул, то F1  F2, F1  F2  – ППФ. Змінні вільні у F1  F2, F1  F2, якщо вони вільні принаймні у одній формулі.
  4.  Якщо F – ППФ і r – вільна у ній змінна, то r(F), r(F) – ППФ; rзв’язана змінна.
  5.  Інших ППФ немає.

Приклади ППФ:

P1r2  (r2[1]  r3[2])        - всі змінні вільні

r2 ((P1 r1  P2r2) (r1 [1]  r2 [2]))        - r1- вільна змінна,  r2 – зв’язана квантором  

Правильно визначені формули (ППФ)

Безкванторна ППФ F називається правильно визначеною (ПВ) над змінною r, якщо виконуються такі умови:

  1.  r єдина вільна змінна в F;

2.   усі предикатні символи, що входять у формулу, інтерпретуються сумісними реляціями;

  1.  всі терми в F є термами значень;
  2.  символ входить в F тільки після , або відсутній.

При інтерпретації формул з  ,  реляція ми отримуємо різницю реляцій, а доповнення реляцій відсутнє.

Приклади формул, правильно визначених над змінною r.

P1r P2r P3r & P4r;  P1r P2r & P3r

Якщо предикати Р1, Р2, Р3, Р4 інтерпретуються реляційними відношеннями R1, R2, R3 R4, то перший приклад встановлює, що змінна r приймає значення з області (R1  R2 R3) R4, а другий встановлює для змінної наступну область інтерпретації: (R1  R2) – R3

У мовах програмування подібну роль виконують оператори декларації

Нехай  F – ПВ над змінною r, а G - ППФ і має r як вільну змінну, але не має термів значень виду Pir. Тоді формули

r (F  G)  та r (F  G)

називаються правильно визначеними на кванторах існування і узагальненняі. Для них будемо використовувати позначення

F (G)   та   F (G).

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

Нагадаємо поняття обмежених кванторів існування і загальності. Суть їх полягає в наступному. Для звичайних кванторів для побудови таблиці істинності формул хА(х) і хА(х) необхідно перебрати всі значення х з області інтерпретації D. Нехай задано предикат Р(х). Якщо ж тепер нас цікавить істинність формул хА(х) і хА(х) не для всіх х D, а тільки для тих, на яких істинний предикат Р(х), то це записується так:

х( Р(х)&А(х) )   і   х( Р(х) А(х) )

Формули з областю визначення

ППФ W називається формулою з областю визначення (ФОВ), якщо виконуються вимоги:

  1.  W = U1  U2  ... Un  V, n1;
  2.  Ui ,i = 1,2,...,n – є ПВ формулою над змінною ri (i j   ri  rj)
  3.  V – або пуста, або ППФ, що задовольняє умовам:
  •  квантори входять у V тільки у вигляді F(G), або  F(G);
  •  кожна вільна змінна з V є вільною в одній з Ui ;
  •  у V немає термів значень з вільними змінними.

Примітка. Формулу з областю визначення варто трактувати у такий спосіб:

  •  Нехай предикати U1, U2,…,Un інтерпретуються відношеннями S1, S2,…,Sn... Конструкція U1 & U2 &…&Un визначає декартовий добуток відношень S1, S2,…,Sn (за відсутності V)

Формула V задає умову з'єднання відношень S1, S2,…,Sn... Зокрема, терми значень задають умови з'єднань на окремих атрибутах відношень, а квантори – умови, обумовлені кванторними зв'язуваннями

Приклади формул з областю визначення:

(предикати P1, P2, P3 інтерпретуються відношеннями R1, R2, R3)

Формула   Інтерпретація

P1r1 & P2r3 & P3r3 -  декартовий добуток відношень R1, R2, R3.

P1r1 & (r1[3] = b) -  обмеження відношень R1 умовою, коли його третій стовпчик дорівнює b.

P1r1 & P3r3 & (r1[2] = r3[1]) -  з'єднання відношень R1, і R3 за умови, що другий стовпець R1 дорівнює першому стовпцю R3.

P1r1&P2r2&P3r3(r1[2]=r3[1]&r1[3]=r2[1])- ділення відношення R1 на R3 за умови r1[2] = r3[1] і з'єднання результату ділення з відношенням R2 за умови r1[3] = r2[1]

Альфа-вирази.

Формула з областю визначення не дозволяє встановити, які саме стовпці потрібні в результуючому відношенні. Для цього вводиться поняття альфа-виразу.

Вираз (t1, t2,…,tk):W називається простим альфа-виразом, якщо виконані такі умови:

  •  W – формула з областю визначення;
  •  t1, t2,…,tk–послідовність кортежних змінних і зрізів. Ці змінні повинні бути вільними у W.

Довільний альфа-вираз визначається аксіоматично в такий спосіб:

- Кожний простий альфа-вираз є альфа-виразом.

- Нехай t = (t1, t2,…,tk)... Якщо t : W1 і t : W2 – альфа-вираз, то вираз t : W1  W2,  t : W1 & W2 і  t : W1 & W2 є альфа-виразами.

Мова ALPHA

На реляційному численні базується ціла родина мов високого рівня. На подальших прикладах розглянемо одну із таких мов - запропоновану Е.Ф.Коддом мову ALPHA. Синтаксичні конструкції цієї мови будуються по аналогії з альфа-виразами. У пошуковому операторі GET є цільовий список, що визначає атрибути вихідної таблиці, та вираз, що відповідає  формулі з областю визначення, який визначає декартовий добуток вхідних відношень і умови їх з’єднання. У зрізах змінних r[m] замість номерів атрибутів використовуються їхні імена . За замовчуванням замість змінної r можна використати анонімну змінну, вказавши в тексті ім’я відповідної таблиці., а мовний процесор сам визначить цю анонімну змінну та зв’яже її з відповідною реляцією (таблицею).

Будемо використовувати реляційні схеми, описані раніше при розгляді реляційної моделі даних.

Приклади.

  1.  Знайти всі відомості про всіх постачальників.

GET W(П.КП, П.прізвище, П.статус, П.місто)

GET W(П)

RANGE П X

GET W(X.КП, X.прізвище, X.статус, X.місто)

Маємо три функціонально еквівалентні варіанти запиту. Перші два – використовують анонімну змінну, а в третьому – за допомогою оператора RANGE явно оголошується змінна Х безпосередньо на реляції (таблиці) П.

GET – пошуковий оператор.

W специфікує таблицю результату або віртуальний пристрій, куди спрямовується результат.

У дужках  - цільовий список кортежних змінних і зрізів, тобто ті  атрибути, які повинні бути представлені у вихідній таблиці. У нашому випадку – вся інформація про постачальників. У вихідну таблицю будуть включені всі кортежі  таблиці П.

  1.  Знайти коди постачальників з статусом більше 20, що живуть в місті N

GET W(П.КП): П.статус > 20 Ù П.місто = ‘N’

Цільовий список складається з одного елемента – зрізу змінної, що набуває значень з  таблиці П, за атрибутом КП (код постачальника).

В цьому випадку після двокрапки з’являється формула з областю визначення, в якій задані умови, за яких вибираються кортежі для формування вихідної таблиці, тобто статус постачальників повинен бути більшим 20 і  місто проживання – N.

Якщо потрібно знайти код постачальника з найбільшим статусом, то використовуємо  такий оператор  GET:

.

GET W(1) (П.КП, П.статус): П.місто = ‘N’ DOWN П.статус

Ключове слово  DOWN означає впорядкування вихідного потоку за спаданням по значенням атрибута, що специфікований після DOWN  (П.статус).

  1.  Знайти прізвища постачальників, що постачають деталь Д3.

RANGE ОПД X

GET W(П.прізвище): $X (X.КП = П.КП & X.КД = Д3)

Для пояснення перефразуємо запит так, щоб зазвучали квантори:: знайти прізвища постачальників, для яких існують поставки деталей з кодом Д3

RANGE ОПД X – оператор декларації  змінної  X,

ОПД – її тип ( у нашому випадку – відношення ОПД) .

Зв’язані змінні  обов’язково декларуються.

Підкванторна формула – це два терми з’єднання, перший з яких з’єднує два реляційні відношення ОПД і КП, а другий – накладає умову на код деталі.

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

Перефразуємо запит: знайти прізвища постачальників, для яких існує поставка, в яких існує червона деталь.

Перший варіант:

RANGE Д X

GET W(ОПД.КП): $X (X.КД = ОПД.КД & X.колір = червоний)

RANGE W Y

GET W2(П.прізвище): $Y (Y.КП = П.КП)

В першому операторі  GET вибираються коди поставок, в яких є червона деталь, в другому -  прізвища постачальників, які роблять ці поставки.

Другий варіант:

RANGE Д X

RANGE ОПД Y

GET W(П.прізвище): $X $Y (Y.КП = П.КП & X.КД = Y.КД & X.колір = червоний)

Тут  використовуються три відношення: П, ОПД, Д. Вони поєднуються за допомогою перших двох термів з’єднання у підкванторній формулі, третій – визначає колір деталі.

  1.  Знайти прізвища тих постачальників, які постачають принаймні одну деталь, яку постачає постачальник П5.

 Перефразуємо запит: знайти прізвища тих постачальників, для яких існує така поставка деталі, для якої існує поставка, яку зробив П5

RANGE ОПД X

RANGE ОПД Y

GET W(П.прізвище): $X $Y (X.КП = П.КП & X.КД = Y.КД & Y.КП = П5)

Змінна X використовується для зв’язування з поставками, які роблять постачальники, яких треба знайти. Y - з поставками постачальника П5, тобто X  та Y виконують різні ролі, отримуючи значення з однієї таблиці  ОПД.

Зауваження: В мові “Альфа” порядок однойменних кванторів несуттєвий, різних кванторів – суттєвий.

  1.  Знайти прізвища тих постачальників, які не постачають деталь Д1.

Перефразуємо запит: знайти прізвища тих постачальників, для яких не існує поставки деталі Д1. Використаємо для його реалізації метод від супротивного, тобто спочатку напишемо запит: “ Знайти прізвища постачальників, для яких існує поставка деталі Д1”, а поті поставимо знак заперечення перед формулою.  

RANGE ОПД X

GET W(П.прізвище): Ø($X(X.КП = П.КП & X.КД = Д1))

Або: знайти прізвища тих постачальників, що для кожної поставки КД ¹ Д1.

GET W(П.прізвище): "X(X.КП ¹ П.КП Ú X.КД ¹ Д1)

Другий варіант запиту еквівалентний першому, бо його можна отримати з попереднього у відповідності  із законами числення предикатів 1-го порядку.

Але прямий запис другого варіанту набагато складніший від першого.

  1.  Знайти прізвища постачальників, які постачають всі деталі.

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

RANGE Д X

RANGE ОПД Y

GET W(П.прізвище): "X $Y(Y.КП = П.КП & Y.КД = X.КД)

  1.  Знайти прізвища тих постачальників, що постачають принаймні всі ті деталі, що і Петренко.

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

RANGE ОПД X

RANGE ОПД X1

RANGE Д Y

RANGE П Z

GET W(П.прізвище): "Y ($X $Z (X.КП = Z.КП & X.КД = Y.КД & Z.прізвище = Петренко) Þ

$X1 (X1.КП = П.КП & X1.КД = Y.КД))

Для цього прикладу зручно використати метод декомпозиції, реалізуючи спочатку підзапити до і після імплікації.

  1.  Знайти коди одержувачів, які не одержують жодної червоної деталі від постачальників з міста N.

Перефразуємо запит: знайти коди одержувачів, для яких не виконується:

існує поставка, для якої існує постачальник з міста N, для якого існує деталь червоного кольору.

RANGE П X

RANGE Д Y

RANGE ОПД Z

GET W(О.КО): Ø($Z $X $Y (X.місто = N & Y.колір = червоний & Z.КП = X.КП

& Z.КД = Y.КД & Z.КО = О.КО))

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

Перефразуємо запит: знайти прізвища тих постачальників, для яких існує така деталь, що для всіх одержувачів існує поставка цієї деталі.

RANGE О X

RANGE Д Y

RANGE ОПД Z

GET W(П.прізвище): $Y "X $Z (Z.КП = П.КП & Z.КД = Y.КД & Z.КО = X.КО)

  1.  Знайти коди одержувачів, потреби яких повністю задовольняє постачальник з кодом П7.

Перефразуємо запит: знайти коди одержувачів таких, що для всіх поставок постачальником є постачальник з кодом П7.

RANGE ОПД X

GET W(О.КО): "X (X.КО = О.КО Þ X.КП = П7)

  1.  Знайти коди деталей, які постачаються всім одержувачам з міста ‘N’.

Перефразуємо запит: знайти коди деталей таких, що для всіх одержувачів, якщо місто одержувача ‘N’,  то існує поставка цієї деталі цьому одержувачу.

RANGE ОПД X

RANGE О Y

GET W(Д.КД): "Y (Y.місто = ‘N’ Þ $X (X.КД = Д.КД & X.КО = Y.КО))

  1.  Знайти коди одержувачів, які використовують тільки ті деталі, що постачаються від поставника П7.

Перефразуємо запит: знайти коди одержувачів таких, що для всіх деталей, якщо існує поставка цієї деталі цьому одержувачу, то існує поставка цієї деталі від постачальника П7.

RANGE ОПД X

RANGE Д Y

RANGE ОПД Z

GET W(О.КО): "Y ($Z (Z.КД = Y.КД & Z.КО = О.КО) Þ $X(X.КД = Y.КД & X.КП = П7))

  1.  Знайти коди одержувачів, які використовують тільки деталі від постачальника П7.

Перефразуємо запит: знайти коди одержувачів таких, що для всіх деталей, якщо існує поставка цієї деталі цьому одержувачу, то існує поставка цієї деталі цьому одержувачу від постачальника П7.

RANGE ОПД X

RANGE Д Y

RANGE ОПД Z

GET W(О.КО): "Y ($Z (Z.КД = Y.КД & Z.КО = О.КО) Þ $X(X.КД = Y.КД & X.КО = О.КО & X.КП = П7))

  1.  Змінити колір деталі Д6 на червоний.

HOLD W(Д.КД, Д.колір): Д.КД = Д6

W.колір = червоний

UPDATE W

HOLD – здійснюється пошук, але залишається вказівник на  тому місці зовнішньої пам’яті, звідки дані отримані.

UPDATE Wоновлюється результуюче відношення

Також використовуються: DELETE W – вилучення даних, PUT W – внесення даних.

 

 ВИКОРИСТАННЯ ВБУДОВАНИХ ФУНКЦІЙ

  1.  Знайти загальну кількість постачальників.

GET W(COUNT (П.КП))

COUNT вбудована функція, що підраховує поля будь-яких типів.

Також використовуються: TOTAL, MAX, MIN, AVERAGE – але для цих функцій можливе використання лише по числовим полям, точніше по типам даних, де задані арифметичні операції.

  1.  Знайти коди постачальників з найбільшим статусом.

GET W(П.КП): TOP(1, П.статус)

Також використовується BOTTOM – найменше значення.

  1.  Для кожної деталі, що постачається, знайти її номер та загальний об’єм поставки.

GET W(ОПД.КД, iTOTAL(ОПД, КД, кількість))

Функція iTOTAL в даному випадку  обчислюється наступним чином: ‘ОПД’ – реляція, в якій відбувається групування по атрибуту ‘КД’ і для кожної групи підраховується сума по атрибуту ‘кількість’.

Також використовуються: iCOUNT, iMAX, iMIN, iAVERAGE.

  1.  Знайти коди деталей, що постачаються більш ніж одним постачальником.

GET W(ОПД.КД):iCOUNT(ОПД, КД, КП) > 1


 

А также другие работы, которые могут Вас заинтересовать

75338. Франция в XII-XIII веках 43.5 KB
  Социальноэкономическое развитие Франции в это время отличали заметные сдвиги и прогресс в развитии производительных сил следствием которых явилось повышение продуктивности сельского хозяйства см. Процесс сокращения и даже ликвидации барской запашки получил наиболее выраженные формы именно во Франции и особенно в хозяйствах светских феодалов. Особенностью развития Южной Франции в Х1ХП вв. Обретя большую степень самостоятельности и ориентированные по преимуществу на внешнюю торговлю южные города не сыграли значительной роли в деле...
75339. Франция в XIV-XV веков 34 KB
  Франция в XIVXV вв. В первой трети XIV в. Широкое распространение денежной ренты и личная свобода крестьянства укрепили его наследственные владельческие права на цензиву ставшую в XIV в. XIV вв.
75340. Германия в XII-XIII веках 43.5 KB
  Германия в XII-XIII вв. Наиболее важную роль в истории XII первой половины XIII в. Положение крестьянства в XII XIII вв. Все эти обстоятельства вызвали по все видимости значительный рост аграрного производства в XII XIII вв.
75341. Германия в 14-15 веках 46 KB
  Швейцарский союз. эти три кантона заключили между собой вечный союз для борьбы за свободу. Так возник и утвердился Швейцадский союз который в течение последующих двух веков продолжал отстаивать свою свободу и политическую независимость. С этой целью они стали объединяться в союзы.
75342. Германия в XIV-XV веках 30.5 KB
  Германия в XIVXV вв. XIV XV вв. империя не имела твердо закрепленных границ они изменялись в результате войн династических браков перемен в вассальных связях Для средневековой Германии XIV и XV столетия стали временем наивысшего расцвета ее городов бурного роста ремесел и торговли Собственное производство в немецких городах было рассчитано на местные рынки. Во второй половине XIV в.
75343. Столетняя война 42.5 KB
  Борьба изза бывшей территории Франции Аквитании особенно ее зап. область Франции юридически была фьефом англ. Толчком к войне послужила династическая ситуация сложившаяся во Франции в 1328 г. Корона Франции была передана Филиппу VI Валуа представителю боковой ветви Капетингов.
75345. Кризис в Западной Римской империи в III-V вв. и возникновение протофеодальных отношений. Падение Западной Римской империи и образование варварских королевств 45.5 KB
  Кризис в Западной Римской империи в IIIV вв. Падение Западной Римской империи и образование варварских королевств. в состав рабовладельческой Римской империи кроме Италии входили большая часть Британии Испания Галлия области по правому берегу Дуная Балканский полуостров Малая Азия острова Средиземного моря Киренаика Сирия Северная Аравия часть Месопотамии Северная Африка и Египет. в большей части империи наблюдалось уже запустение земель деградация ремесла и острая нехватка рабочей силы вызванная низкой производительностью труда...
75346. Государства крестоносцев на Востоке. Второй и третий крестовый походы 36.5 KB
  Вскоре после взятия Иерусалима крестоносцы овладели значительной частью восточного побережья Средиземного моря. Поделив между собой новые владения крестоносцы установили в них феодальные порядки во многом схожие с теми которые существовали на их родине. При этом крестоносцы жили главным образом в прибрежных юродах и укрепленных замках которые им пришлось построить чтобы обеспечить себе безопасность. началось сплочение мусульманских княжеств в результате чего крестоносцы стали терять свои владения.