18226

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

Реферат

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

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

Украинкский

2013-07-07

87.5 KB

14 чел.

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

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

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

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

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

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


 

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

25262. Спільне філософії і науки 64.5 KB
  Природні релігії. Надприродні релігії. Природні релігії це релігії які створив людський розум.
25263. Проблема класифікації релігій. Огляд різноманітних типологій релігії 28.5 KB
  Огляд різноманітних типологій релігії Більшість дослідників прагне розподілити релігії за певними критеріями але потрібно відкинути нормативні класифікації розподіл на релігію істинну свою і релігію хибну інших. 3 групи: 1 релігії арійських народів індоєвропейські народи; 2 релігії семітських народів семітськохамітська мовна група; 3 релігії туранських народів народи Уралу і Алтаю. Три релігії природи: чаклунство; брахманізм і буддизм; стадія переходу до релігії свободи зороастризм єгипетська і фінікійська релігії; 2...
25264. Проблема сутності християнства: огляд різноманітних точок зору. Ідейні передумови появи християнства 30 KB
  Проблема сутності християнства: огляд різноманітних точок зору. Ідейні передумови появи християнства Афанасій Великий: Слово про втілене слово і сповідання віри про втіленого Бога дало стійкість християнству це ортодоксальна точка зору. Іша точка зору: Євангеліє формується під грецьким впливом і долає іудаїзм; ІІга точка зору: Євангеліє це є продовження іудаїзму іудаїзм єдина основа християнства. Це однією точкою зору є бачення смислу християнства у етичному вченні Ісуса Христа.
25265. Утвердження християнства в Київській Русі. Володимирова версія хрещення Русі: аргументи „за” і „проти” 30 KB
  Утвердження християнства в Київській Русі. Володимирова версія хрещення Русі: аргументи за і проти Ідеї християнства на територію Східної Європи почали проникати ще за римських часів про що свідчать матеріали археологічних памяток Кримського півострова. На Русі знайомство з новою вірою відбулося у ІХ ст. Процес впровадження православя на Русі був дуже довгим і не однозначним.
25266. Українське православя: його витоки та особливості історичного розвитку. Православний рух в Україні 90-х рр. XX ст.-початку XXI ст 30 KB
  УАПЦ 1990 незалежна УПЦ Друга половина XVI ст. Філарет веде політику щоб УПЦ отримала автокефалію травень 1992 р. в Харкові Собор єпископів Російської православної церкви на якому Філарет був усунений з кафедри предстоятеля УПЦ. утворення Української православної церкви Київського патріархату злиття УПАЦ і тих хто підтримував Філарета від УПЦ.
25267. Містицизм в рел іст людства. Особливості міст сприйняття. Заг хар христ містики 24 KB
  як правило супроводжує періоди сусп криз: занепад Рим імперії неоплатонізмтворцем світу є надчуттєве абстрактне єдине що може бути сприйняте людиною лише в екмтазі гностицизмматерія гріховне і зле начало що протистоїть духовному непізнаваному первоначалу; кін сер віків суфізмпізнання Бога шляхом особливих танців або постійного повторення молитв кабалавтручання в божественні процеси за допомогою спец ритуалів молитв ісихазмчерез містичне споглядання у чернецтві можна досяг вищий ступінь пізнання запереч пізн Бога за...
25268. Проблеми християнської антропології 33.5 KB
  Видима частина тіло плоть; невидима душа дух психічне те що існує у формі почуттів уявлень думок. 2 частини у Л: душа і тіло. Дух душа тіло. Ідея про тіло як необхідний орган знаряддя душі.
25269. Особливості розвитку православної філософії і богослов'я в ХІХ-ХХ століттях 34.5 KB
  Щербацький велику увагу приділяли проблемам пізнання істини суті пізнання. Концепція пізнання себе: âПізнай себеâ. Пізнання це наближення до Бога шляхом пізнання себе. Теорія пізнання Сковороди безпосередньо пов'язана з його вченням про три світи і дві натури вона є двоїстою: з одного боку Г.
25270. Християнський неноплатонізм. Корпус ареопагітиків 28 KB
  Корпус ареопагітиків включає 4 трактати: Про небесну ієрархію Про церковну ієрархію і Про божественні імена Таємниче богословя і 10 послань в них розкривається доктрина вища точка християнського неоплатонізму. Автор повязав онтологію неоплатонізму з соціальною проблематикою; доктрина про церковну ієрархію безпосередньо підстроюється до доктрини небесних ієрархій. При цьому на відміну від мітичного історизму Августину Церква як град Божий образ церкви як ідеальна людська спільнота що знаходиться у згоді з...