18226

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

Реферат

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

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

Украинкский

2013-07-07

87.5 KB

10 чел.

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

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

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

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

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

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


 

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

18267. Організація та зміст гуманітарної підготовки в ЗС України 50.2 KB
  Заняття 20: Організація та зміст гуманітарної підготовки в ЗС України. Мета заняття: формувати у курсантів риси необхідні військовому керівнику для професійної діяльності; сприяти розвитку почутт...
18268. Методи і форми військового навчання 68.03 KB
  Заняття 10: Методи і форми військового навчання. Мета заняття: формувати у курсантів риси необхідні військовому керівнику для професійної діяльності; сприяти розвитку почуття свідомої вій
18269. Методи виховання військовослужбовців 210.5 KB
  Заняття №10 Методи виховання військовослужбовців. Мета заняття: З’ясувати зміст поняття €œметоди виховання військовослужбовців€ та їх класифікацію. Вивчити методику застосування о...
18270. Закономірності та принципи навчання ійськовослужбовців 36.96 KB
  Заняття №7: Закономірності та принципи навчання ійськовослужбовців. Мета заняття: формувати у курсантів риси необхідні військовому керівнику для професійної діяльності; сприяти розвитку почу
18271. Специфіка військового навчання 272.5 KB
  Заняття №5: €œСпецифіка військового навчання Мета заняття: Розкрити основні концепції навчання їх використання у процесі військового навчання. 22. Проан
18272. Засоби визначення повітряних параметрів 676.5 KB
  Практичне 1.1. Засоби визначення повітряних параметрів. Навчальні питання 1. Система повного й статичного тисків 2. Пілотажний прилад комбінований резервний ППКРСВС Засоби визначення повітряних параметрів містять у собі: систему повного й статичного тисків я...
18273. ВЕЛИЧИНИ, ЩО ВИВЧАЮТЬСЯ В ШКІЛЬНОМУ КУРСІ МАТЕМАТИКИ 249 KB
  ВЕЛИЧИНИ ЩО ВИВЧАЮТЬСЯ В ШКІЛЬНОМУ КУРСІ МАТЕМАТИКИ Площа фігури її основні властивості. Одиниці площі та відношення між ними. Способи вимірювання площ. Рівновеликі і рівноскладені фігури. Поняття про об’єм тіла. Одиниці об’єму та відношення між ними. П
18274. ЕЛЕМЕНТИ ТЕОРІЇ МНОЖИН. ПОНЯТТЯ ТА ЇХ ОЗНАЧЕННЯ 72.5 KB
  Лекція 1 ЕЛЕМЕНТИ ТЕОРІЇ МНОЖИН. ПОНЯТТЯ ТА ЇХ ОЗНАЧЕННЯ Поняття про твердження. Математичні твердження та їх види. Поняття його обсяг і зміст. Відношення між поняттями. Означення понять. Способи означення. Означувані і неозначувані поняття. Вимоги д
18275. МНОЖИНИ ТА ВІДНОШЕННЯ МІЖ НИМИ 101 KB
  Лекція 2 МНОЖИНИ ТА ВІДНОШЕННЯ МІЖ НИМИ Поняття множини. Скінченні і нескінченні множини. Способи задання множин. Порожня і одинична множини. Точкові множини. Геометрична фігура як множина точок. Плоскі і просторові геометричні фігури. Круги Ейлера. Рівн...