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


 

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

52554. Впровадження інтерактивних технологій в освітній процес з метою розвитку мовленнєвої компетентності у дошкільників 56 KB
  План проведення майстер класу для вихователів: п п Зміст роботи Відповідальний Джерела І Вправа Очікування Вихователь методист Базова програма Я у Світі Майстер класи для вихователів ДНЗ випуск№2 упоряд. Настільна гра На гостину до казки III Вправа Очікування підсумок Вихователь методист Матеріал: магнітофон з записами дитячих мелодій стікери кораблики плакат з намальованою річкою маркери конверти з завданнями ілюстрації до різних казок предметні картинки гуашева фарба аркуші А 4 пензлики тампончики...
52555. Ігрова вправа «Народно-поетичні символи України» 95 KB
  У чужій сторонці не так світить і сонце Хочеш собі добра не роби нікому зла За гроші честі не купиш Гра Чи вірите ви що Чи вірите ви що гімн це колискова пісня Чи вірите ви що вінок символ молодості і дівоцтва Чи вірите ви що калина державний символ України Чи вірите ви що Павло Чубинський автор тексту гімну Чи вірите ви що оранжевий і синій кольори Державного Прапора України Чи вірите ви що лелека символ працьовитості Чи вірите ви що у тризубі відображено триєдність життя Чи...
52556. Воспитательный час «Если добрый ты…» 54 KB
  Участники и действующие лица: ведущая учительница Незнайка школьный класс поделенный на три команды из числа которых назначаются чтецы и исполнители инсценировок. Входит Незнайка. Незнайка. Скажи пожалуйста как тебя зовут Незнайка.
52557. Інтегроване заняття на тему: Людина починається з добра (з використанням казок В. Сухомлинського) 57 KB
  Діти до кого я привіталася Так я привітала новий день все що оточує нас наших гостей. Добрий день Стук у двері відчинили і внесли лист Діти до нас листоноша приніс листа від Казкаря. Давайте пригадаємо разом ці прислівя діти пригадують прислівя. Молодці діти.
52558. Хто людям добра бажає, той сам його здобуває 36.5 KB
  Донести до дитини важливість слова людяний. Удосконалювати вміння добирати слова близькі за значенням. Мовленева вправа Добери слова з протилежним значенням Злий жорстокий співчутливий добрий милосердний. Малюючи кожну пелюсточку промовляйте такі слова щоб довести що кожен із вас справжній друг.
52559. Як розрізняють добро і зло 32.5 KB
  Допомогти учням усвідомити зміст етичних понять «добро» «доброчинність», робити вибір між добром і злом, давати оцінку добру і злу; формувати вміння учнів моделювати ситуації та розв’язувати їх; виховувати в учнів моральні цінності та орієнтири, правила культури поведінки.
52560. Людина починається з добра. Від усмішки іде до всіх тепло. Музика – нев’януча краса духовної культури усіх народів 74.5 KB
  Що ми можемо сказати Чи потрібні вони у житті людини Чи впливає музика на емоції людини Чи потрібні нам ці теми уроків Епіграф до уроків Бо ти на землі людина І хочеш того чи ні Усмішка твоя єдина Мука твоя єдина Очі твої одні. Дуже важливими є емоції людини які підтримують нас...
52562. Виховний захід для учнів початкової школи “Дорогою добра” 88 KB
  Збагатити знання учнів про чудодійні обереги нашого життя квіти і виховувати глибокі почуття добра і любові до рідного краю свого роду; Розширити знання учнів про звязок людини з природою її вплив на культуру нашого народу. Виходить дівчатка і збирає в кошик квіти які посадили на підлозі. Тому сьогодні ми поговоримо про вічні супутники людського життя і в горі і в радощах квіти. Я землі цієї паросток зелений Я землі цієї крапля дощова Заплелись у мене приросли до мене Жито і дерева квіти і трава.