1. Булеви функции. Теорема на Пост-Яблонски за пълнота. Нека J2 = { 0, 1}. Всяка функция f : J2n  J



страница6/29
Дата11.01.2018
Размер5.91 Mb.
#44141
1   2   3   4   5   6   7   8   9   ...   29

Твърдение: Нека  (F) е функционален терм, c е константа и

R   c. Тогава  ()  c.

Доказателство: Провеждаме пълна индукция по дължината на извода R   c. Нека R   c с дължина на извода k и твърдението е вярно за изводи R   c с дължини по-малки от k.

Разглеждаме случаи в зависимост от вида на .

Случаите, когато  е константа,  е основна операция или  е условен терм следват непосредствено от индукционното предположение и дефиницията за стойност на терм.

Интересният случай е  = (1, 2, …, ). Имаме R   c с дължина на извода k, така че от лемата за извода съществуват константи c1, c2, …, , такива че R j  cj, j = 1, 2, …, ni с дължини на изводите по-малки от k и

R i (X1/c1, X2/c2, …, /, F)  c с дължина на извода

по-малка от k. От индукционното предположение имаме j ()  cj, j = 1, 2, …, ni и i (X/c, F)()  c. От лемата за съгласуване на заместване и стойност получаваме

i (c, )  c. Имаме  ()  i (1 (), 2 (), …, ())  i (c) 

 Гi ()(c)  i (c, )  c. Използвали сме, че е решение на системата за Г1, Г2, …, Гk.


Теорема: ОV (R) DV (R).

Доказателство: Нека ОV (R)(a)  b. Тогава R 0 (X/a, F)  b.

От предното твърдение получаваме 0 (X/a, F)()  b. Прилагаме лемата за съгласуване на заместване и стойност и получаваме

0 (a, )  b  DV (R)(a)  b. Така ОV (R) DV (R).


За всяко i  { 1, 2, …, k } дефинираме функцията i :   по следния начин:

i (a1, a2, …, )  b  R i (X1/a1, X2/a2, …, /, F)  b.

Функцията i e добре дефинирана от еднозначността на опростяването по стойност.
Лема: Нека  (F) е функционален терм и  ()  b.

Тогава R   b.

Доказателство: Индукция по построението на .

Случаите, когато  е константа,  е основна операция или  е условен терм следват непосредствено от дефиницията за стойност на терм, от индукционното предположение и от правилата за опростяване. По-интересен е следният случай:

 = (1, 2, …, ) и твърдението е изпълнено за термовете

1, 2, …, . Имаме  ()  b  съществуват

b1, b2, …, , такива че 1 ()  b1, 2 ()  b2, …, ()  и

i (b1, b2, …, )  b. От индукционното предположение



R j  bj, j = 1, 2, …, ni. Освен това i (b1, b2, …, )  b 

R i (X1/b1, X2/b2, …, /, F)  b. От правило 3.

получаваме R   b.
Следствие: е квазирешение на системата за Г1, Г2, …, Гk.

Доказателство: Нека Гi ()(a)  b. Тогава i (a, )  b. От лемата за съгласуване на заместване и стойност получаваме i (X/a, F)()  b и от предната лема R i (X/a, F)  b. Съгласно дефиницията на i получаваме i (a)  b. Така Гi () i, i = 1, 2, …, k  е квазирешение на системата за Г1, Г2, …, Гk.


Следствие: .

Доказателство: Тъй като е квазирешение на системата за

Г1, Г2, …, Гk, а е най-малкото квазирешение на тази система,

то .


Теорема: DV (R) OV (R).

Доказателство: Нека DV (R)(а)  b. Тогава 0 (a, )  b, и от твърдението за монотонност получаваме 0 (a, )  b. От лемата за съгласуване на заместване и стойност 0 (X/a, F)()  b и от лемата

по-горе получаваме R 0 (X/a, F)  b, т.е. OV (R)(a)  b.

Така DV (R) OV (R).


Kaто комбинираме двете теореми получаваме OV (R) = DV (R),

с което показахме еквивалентността на операционната и денотационната семантика с предаване по стойност на рекурсивните програми.


Нека P е свойство на функциите от Fn, т.е. P : Fn  { tt, ff }.

Казваме, че P е (изброимо) непрекъснато, ако за всяка монотонно растяща редица от функции { fk}, fkFn,

P (fk) за всяко k    P ().

Теорема (правило на Скот): Нека P е непрекъснато свойство,

Г : FnFn e непрекъснато изображение.

Нека P (!) и за всякa g  Fn, P (g)  P (Г (g)).

Toгава P (f), където f е най-малката неподвижна точка на Г.

Доказателство: От доказателството на теоремата на

Кнастер-Тарски имаме f = , f0 = !, fk+1 = Г (fk) за всяко k  .

С индукция по k ще покажем, че P (fk) за всяко k  .

База: При k = 0, f0 = ! и P (f0) е вярно по условие.

Предположение: Нека е доказано P (fk).

Стъпка: Имаме P (fk)  P (Г (fk)), P (fk) е вярно  P (Г (fk)), т.е. P (fk+1).

Тъй като { fk} е монотоннo растяща редица и P е непрекъснато свойство имаме P (), т.е. P (f).


Ще дадем някои примери за непрекъснати свойства.
Свойство P от вида:

P (f)  за всяко x  n, (! f (x) & I (x))  O (x, f (x)), където

I (x) и O (x, y) са произволни предикати над ествените числа се нарича условие за частична коректност. Ясно е, че P (!) е вярно при всеки избор на предикатите I, O. Лесно се вижда, че P е непрекъснато.
Свойство P от вида:

P (f)  за всяко xNn, I (x)  (! f (x) и O (x, f (x))), където I, O имат същия смисъл се нарича условие за тотална коректност. Ясно е, че P (!) е вярно  I (x)  ff при всеки избор на O. Лесно се вижда, че P е непрекъснато. Правилото на Скот, обаче, не е приложимо за P, тъй като P (!) не е вярно (освен в тривиалния случай

когато I  ff).
Нека Г1 : FmFn и Г2 : FmFn са непрекъснати изображения.

Toгава свойството P, дефинирано с P (g)  Г1 (g) Г2 (g) е непрекъснато.


Твърдение: Нека P1 и P2 са непрекъснати свойства.

Тогава свойството P (g), дефинирано с P (g)  P1 (g) & P2 (g) е непрекъснато.

Доказателство: Ако P е вярно за всеки член на някоя монотонно растяща редица, то P1 и P2 също са вярни за всеки член на редицата, откъдето лесно следва твърдението.
Следствие: Нека Г1 : FmFn и Г2 : FmFn са непрекъснати изображения. Toгава свойството P, дефинирано с

P (g)  Г1 (g) = Г2 (g) е непрекъснато.

Доказателство: Г1 (g) = Г2 (g)  Г1 (g) Г2 (g) & Г2 (g) Г1 (g).
Твърдение: Нека P1 и P2 са непрекъснати свойства. Тогава свойството P (g), дефинирано с P (g)  P1 (g)  P2 (g) е непрекъснато.

Доказателство: Ако P е вярно за всеки член на някоя монотонно растяща редица, то поне едно от P1 и P2 е вярно за безброй много членове на редицата, откъдето лесно следва твърдението.


Ще отбележим, че лесно се проверява (чрез пример), че отрицание на непрекъснато свойство не винаги е непрекъснато.
5. Релационна алгебра. Релационно смятане. Нормални форми.
Домен е множество от стойности, подобно на тип данни (но не е тип, защото няма операции). Релационният модел изисква стойностите, които съдържат домените да са атомарни, т.е. да не могат да бъдат разбити на по-малки компоненти. Например, домени са множеството на целите числа, множеството на символните низове (с или без фиксирана дължина).

Нека D1, D2, …, Dk са домени. Релация наричаме всяко подмножество R на декартовото произведение D1 x D2 x …x Dk.

Числото k наричаме размерност (степен) на релацията.

Елементите на една релация R наричаме кортежи. Всеки кортеж на една k-мерна релация има k компонента. За краткост кортежите означаваме по следния начин: v1v2…vk, където vi  Di е i-тият компонент на кортежа.

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

Полезно е релацията да се разглежда като таблица. Всеки ред в таблицата е кортеж и всяка колона съответства на един компонент от съответния домен. На колоните често им се дава имена, които се наричат атрибути. Обикновено атрибутите описват значението на стойностите в колоните на релацията.

Всяка релация си има име. Името на релацията, заедно с множеството от атрибутите на релацията образуват схемата на релацията. Ако името на релацията е REL и нейните атрибути са

A1, A2, …, Ak, то релационната схема означаваме по следния начин:

REL (A1, A2, …, Ak). Атрибутите в схемата на една релация са множество, а не списък, т.е. няма наредба на атрибутите. При разместване на атрибутите или кортежите, получаваме релация, която е еквивалентна на първоначалната. Въпреки това се предполага, че при визуализация атрибутите се записват в определен стандартен ред. Този стандартен ред винаги ще определяме от записа на схемата на релацията.

Схемата на една релационна база данни наричаме множеството от схемите на релациите, които участват в базата данни.

Релациите не са статични, те се променят в течение на времето – добавят се нови кортежи, променят се съществуващи кортежи, изтриват се съществуващи кортежи. По-рядко се променя схемата на една релация – добавяне или изтриване на атрибути. В една голяма релация това са твърде тежки операции.



Реализацията на една релационна база данни се характеризира с независимост на данните. С други думи, вътрешната структура на имплементация на базата данни се скрива от външната концептуална структура. Концептуално данните са организирани в таблици, физически имаме записи в някаква файлова структура, които представят кортежите. За да бъде подобрена ефективността на заявките се използват различни механизми за индексиране като хеширане и B+ дървета.

Потребителите търсят информация в релационната база данни като образуват заявки, написани на някоя от формалните нотации за изразяване на операции върху релации. Тези нотации са два вида:



  1. Алгебрическа нотация, наречена релационна алгебра, където заявките се изразяват чрез прилагане на специални операции към релациите.

  2. Логическа нотация, наречена релационно смятане, където заявките се изразяват чрез писане на логически формули, които трябва да удоволетворяват кортежите в резултата.

Двете нотации (при някои ограничения) имат еквивалентна изразителна мощ, т.е. всяка от тях може да изрази произволна заявка, която другата може.
Релационната алгебра е нотация за описване на заявки към релации. Множеството от операциите, които осигурява релационната алгебра не е пълно по Тюринг, в смисъл че съществуват операции, които не могат да се опишат със средствата на релационната алгебра, но могат да се опишат например на C++ или на кой да е от обикновените езици за програмиране. Предимството е, че това дава възможност за по-ефективно оптимизиране на заявките.

Операциите от релационната алгебра формално се извършват върху релации, които се разглеждат като множества от кортежи.


Съществуват пет основни операции, които се дефинират в релационната алгебра.
Първите две основни операции са обикновени операции върху множества: обединение и разлика.

За да могат да се приложат тези операции върху две релации

R и S, то трябва да са изпълнени следните условия:


  • R и S трябва да имат едни и същи схеми с идентични множества от атрибути, както и идентични домени за тези атрибути;

  • преди да се изпълни операцията колоните на R и S трябва да се подредят по един и същи начин.

Обединението на R и S бележим с R  S и то представлява множеството от кортежи, които се срещат в R, в S или едновременно в R и S.

Разликата на R и S бележим с R - S и тя представлява множеството от кортежи, които се срещат в R, но не се срещат в S.


Третата основна операция служи за комбиниране на кортежите в две релации. Тя се нарича декартово произведение.

Декартовото произведение на релациите R и S бележим с R x S и то представлява множеството от всевъзможните кортежи, които са съединение на кортеж от R с кортеж от S. Схемата на R x S е обединение на схемите на R и S с тази особеност, че ако R и S имат атрибути с еднакви имена предварително трябва да се извърши преименуване на дублиращите се атрибути. Изполваме точкова нотация - за да различаваме общия атрибут A на релациите R и S записваме R.A за атрибута от R и S.A за атрибута от S. Ще считаме, че атрибутите на R предшестват атрибутите на S в схемата на R x S.


Последните две основни операции са унарни и чрез тях се премахва част от релация. Те се наричат проекция и селекция.

Операцията проекция, приложена върху релация R се използва за образуване на нова релация, в която участват само някои от

колоните на R. Бележим , където A1, A2, …, An са част от атрибутите на R. Схемата на новата релация се състои само от атрибутите A1, A2, …, An. Кортежите на новата релация са проекции на кортежите на R върху атрибутите A1, A2, …, An,

с други думи кортежът v1v2…vn присъства в новата релация точно тогава, когато съществува кортеж на R, който има стойност vi за компонентата, отговаряща на атрибута Ai за всяко i  { 1, 2, …, n }.

Резултатът от операцията селекция, приложена върху релация R е друга релация с множество кортежи, което е подмножество на кортежите на R. Кортежите, които се включват в резултата са точно онези кортежи от R, които удоволетворяват някакво условие C за стойностите на атрибутите.

Резултатът от селекцията бележим по следния начин: C (R).

Схемата на релацията C (R) съвпада със схемата на R.

C е условен израз, в който като операнди участват константи или имена на атрибути на R. В C могат да се използват различните операции за сравнение =, <, >, , , , както и логическите съюзи , , . Условието C се прилага към всеки кортеж t на релацията R, като името на всеки атрибут в условието C се замества със съответната му стойност от кортежа t. Ако условието се оцени като истина, то кортежът t се включва в релацията C (R), в противен случай не се включва.


В релационната алгебра са дефинирани и някои допълнителни операции, които могат да бъдат изразени с помощта на основните пет операции.
Операцията сечение може да се прилага върху две релации R и S, за които са изпълнени условията, описани при операциите обединение и разлика. Сечението на R и S бележим с R  S и то представлява множеството от кортежи, които се срещат едновременно в R и S. Сечението се изразява чрез разлика по следния начин: R  S = R - (R - S).
Операцията частно може да се прилага върху две релации R и S, ако са изпълнени следните условия:

  • ако схемата на R е R (A1, A2, …, An), то схемата на S трябва да има вида S (Ai, Ai+1, …, An), 1 < i  n;

  • релацията S е непразна.

Частното на R и S бележим с R  S и то представлява множеството от всички кортежи v1v2…vi-1, такива че за всеки кортеж viv+1…vn

на S кортежът v1v2…vn е кортеж на R. С други думи, R  S е

най-голямата релация, такава че (R  S) x S  R.

Частното се изразява чрез петте основни операции така:

R  S = .
Операцията съединение (-съединение) е операция за комбиниране на кортежите на две релации R и S.

Резултатът от операцията означаваме по следния начин: R ⋈C S.

Схемата на R ⋈C S е обединение на схемите на R и S, при това при дублиране на атрибути отново трябва да се използва точковата нотация. C е условен израз, подобен на условния израз от селекцията, но в него могат да участват имена на атрибути и на R и на S. Кортежите на R ⋈C S получаваме по следния начин:


  • образуваме релацията R x S;

  • избираме онези кортежи на R x S, които удоволетворяват условието C (след заместване на имената на атрибутите със съответните стойности).

Ясно е, че -съединението се изразява по следния начин чрез основните операции: R ⋈C S = C (R x S).
Операцията естествено съединение също е операция за комбиниране на кортежите на две релации R и S. Резултатът от операцията означаваме по следния начин: R ⋈ S. Кортежите на

R ⋈ S са всевъзможни съединения на кортеж от R с кортеж от S, които се съгласуват по общите атрибути на релациите R и S.

По-прецизно, нека A1, A2, …, An са общите атрибути в схемите на релациите R и S. Тогава схемата на R ⋈ S е теоретико-множествено обединение на схемите на R и S, т.е. не се използва точковата нотация и атрибутите A1, A2, …, An участват само по веднъж в схемата на R ⋈ S. Два кортежа r на R и s на S се съединяват успешно, ако те се съгласуват по стойностите на

A1, A2, …, An. Toгава съответният кортеж на R ⋈ S се съгласува по всички атрибути на R с кортежа r и по всички атрибути на S с кортежа s. Естественото съединение се изразява чрез основните операции така:

R ⋈ S = L (C (R x S)). Условието C има вида:

R.A1 = S.A1  R.A2 = S.A2  … R.An = S.An.

Списъкът от атрибути L започва с атрибутите на R, последвани от тези атрибути на S, които не са атрибути на R.
Форма на логиката, наречена релационно смятане лежи в основата на повечето комерсиални езици за заявки, базирани на релационния модел. Разликата между релационната алгебра и релационното смятане е, че релационната алгебра е
операционална – един израз на релационната алгебра дава стъпка по стъпка процедурата, която трябва да бъде извършена, за да се изчисли резултата. От друга страна, релационното смятане е декларативно – това е език от предикати, които казват дали даден кортеж се съдържа или не в резултата.

Релационното смятане съществува в две разновидности – релационно смятане с променливи върху кортежи и релационно смятане с променливи върху домени.


Релационното смятане с променливи върху кортежи е вид релационно смятане, при което променливите означават кортежи, а не компоненти на кортежи. Ако s е променлива, A е атрибут, то ще означаваме със s[A] стойността на компонентата на s, отговаряща на атрибута A.

Под атом разбираме един от следните изрази:



  • R (s), където R е име на релация, s е променлива, атомът R (s) се оценява с истина, ако s е кортеж на релацията с име R, в противен случай се оценява с лъжа;

  • s[A] op t[B], където s и t са променливи, A и B са атрибути,

op  { =, <, >, , ,  } е операция за аритметично сравнение;

  • s[A] op c, c op s[A], където s, A, op имат същия смисъл, а c е константа от домена на атрибута A.

Дефиницията за формула е индуктивна, успоредно дефинираме понятията свързана и свободна променлива на формула.

Всеки атом е формула, атомът няма свързани променливи и всички променливи, участващи в атома са свободни.

Ако F е формула, то F е формула. Свободните променливи на F са свободните променливи на F и свързаните променливи на F са свързаните променливи на F. Формулата F е истина тогава и само тогава когато F е лъжа.

Ако F1 и F2 са формули, то F1  F2 e формула. Свободните променливи на F1  F2 са свободните променливи на F1 и F2, свързаните променливи на F1  F2 са свързаните променливи на

F1 и F2. Формулата F1  F2 e истина тогава и само тогава когато

F1 е истина и F2 е истина.

Ако F1 и F2 са формули, то F1  F2 e формула. Свободните променливи на F1  F2 са свободните променливи на F1 и F2, свързаните променливи на F1  F2 са свързаните променливи на

F1 и F2. Формулата F1  F2 e истина тогава и само тогава когато

F1 е истина или F2 е истина.

Ако F е формула и s е свободна променлива на F, то (s)F е формула. Свободните променливи на (s)F са свободните променливи на F без s, а свързаните променливи на (s)F са свързаните променливи на F и s. Формулата (s)F е истина тогава и само тогава когато съществува кортеж с конкретни стойности за компонентите му, такъв че, ако заместим с него свободните срещания на s във F получаваме истинна формула.

Ако F е формула и s е свободна променлива на F, то (s)F е формула. Свободните променливи на (s)F са свободните променливи на F без s, а свързаните променливи на (s)F са свързаните променливи на F и s. Формулата (s)F е истина тогава и само тогава когато за всеки кортеж с конкретни стойности за компонентите му, ако заместим с него свободните срещания на s във F получаваме истинна формула.




Сподели с приятели:
1   2   3   4   5   6   7   8   9   ...   29




©obuch.info 2024
отнасят до администрацията

    Начална страница