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


 

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

2791. Внеклассная работа по теме: Animals 34.5 KB
  Внеклассная работа по теме: Animals Для учащихся 3-4 классов общеобразовательных школ Цели внеклассной работы: - расширение и углубление знаний, - развитие у учащихся умения работать в команде, - развитие у учащихся интереса к предмету. Задачи вне...
2792. Ролевая игра Береги себя. (суд над алкоголем) 87 KB
  Внеклассное мероприятие. Ролевая игра Береги себя! (суд над алкоголем). Цели ролевой игры: Показать на примере этанола двойственность химического вещества: его положительные и отрицательные стороны, изучить области применения этанола...
2793. Части речи 26.86 KB
  Части речи Цель: активизировать мыслительную деятельность учащихся. Задачи:  Обучающие: проверка знаний учащихся по русскому языку, учить разрешать проблемные вопросы, Развивающие: формирование положительной мотивации изучения предмета...
2794. There is no place for tobacco in my life 33 KB
  There is no place for tobacco in my life Aims: To teach new vocabulary on the topic. To develop skills in speaking, listening and speaking on the topic. To show negative aspects of smoking. To develop negative attitude to smo...
2795. Путешествие по океану языкознания 292.79 KB
  Тема: Путешествие по океану языкознания Цели:  Обобщение и углубление знаний учащихся по темам: Большая буква в именах собственных, Звуки речи (Ь знак), Ударение, Слоги, Составление предложений, Развитие мыслительных операций...
2796. Определение момента инерции тела методом крутильных колебаний 54 KB
  Определение момента инерции тела методом крутильных колебаний. Цель работы: Изучить метод определения момента инерции тела сложной геометрической формы. Краткое теоретическое обоснование: Для определения моментов инерции тел, неоднородных по плот...
2797. Изучение простейшей электрической цепи переменного тока 90.5 KB
  Изучение простейшей электрической цепи переменного тока. Цель работы: Теоретическое и экспериментальное изучение простейшей электрической цепи. Краткое теоретическое обоснование: Мощность NИ развиваемая источником энергии Работа AИ совершае...
2798. Измерение горизонтальной составляющей индукции магнитного поля Земли при использовании тангенс − буссоли 74 KB
  Измерение горизонтальной составляющей индукции магнитного поля Земли при использовании тангенс. Измерить горизонтальную составляющую индукции B0 магнитного поля Земли г. Казани...
2799. Определение частоты тока с помощью струны 59.5 KB
  Определение частоты тока с помощью струны Цель работы. Осуществление механического резонанса, усвоение методики экспериментального определения частоты переменного тока. Краткое теоретическое обоснование: Натянутая струна совершает колебания, если...