1. Булеви функции. Теорема на Пост-Яблонски за пълнота. Нека J2 = { 0, 1}. Всяка функция f : J2n J
Изтегляне 5.91 Mb.
|
- Навигация на страницата:
- Теорема
- Ограничения
Заявка на релационното смятане с променливи кортежи наричаме израз от вида { t | F }, където F е формула, която има единствена свободна променлива t. Отговорът на заявката е релацията, съставена от всички кортежи, чиито стойности, когато бъдат заместени в съответните компоненти на променливата t, правят F истинна. Понякога заявките може да дават безкраен отговор. Затова се налага да се ограничим до разглеждането само на безопасни формули. Освен, че трябва да дефинират само крайни релации, тези формули трябва да отговарят и на някои други изисквания. За да определим безопасните формули ни трябват две допълнителни дефиниции. Първо ще дефинираме какво означава компонентата s[A] на променливата s да бъде ограничена в една формула. Във формулата R (s) всеки компонент на променливата s е ограничен. Във формулата s[A] op t[B] няма ограничени компоненти. Във формулите s[A] = c, c = s[A], компонентата s[A] на променливата s е ограничена. Във формулата s[A] op c, c op s[A], където op е операция за аритметично сравнение, различна от = няма ограничени компоненти. Във формулата F няма ограничени компоненти. Във формулата F1 F2 eдна компонента на променлива е ограничена точно когато тази компонента е ограничена или във F1 или във F2. Във формулата F1 F2 eдна компонента на променлива е ограничена точно когато тази компонента е ограничена във F1 и във F2. Във формулата (s)F една компонента на променлива е ограничена точно когато тази компонента е ограничена във F и променливата е различна от s. Във формулата (s)F една компонента на променлива е ограничена точно когато тази компонента е ограничена във F и променливата е различна от s. След това дефинираме какво означава компонентите s[A] и t[B] на две променливи s и t да бъдат изравнени в една формула. Във формулата R (s) няма изравнени компоненти на променливи. Във формулата s[A] op t[B], където op не е = няма изравнени компоненти на променливи. Във формулата s[A] = t[B], s[A] и t[B] са изравнени компоненти на променливи. Във формулите s[A] op c, c op s[A], няма изравнени компоненти на променливи. Във формулата F няма изравнени компоненти на променливи. Във формулата F1 F2 две компоненти на променливи са изравнени точно когато тези компоненти са изравнени или във F1 или във F2. Във формулата F1 F2 две компоненти на променливи са изравнени точно когато тези компоненти са изравнени във F1 и във F2. Във формулата (s)F две компоненти на променливи са изравнени точно когато двете променливи са различни от s и компонентите са изравнени във F. Във формулата (s)F две компоненти на променливи са изравнени точно когато двете променливи са различни от s и компонентите са изравнени във F. Естествено, предполагаме рефлексивност, симетричност и транзитивност: s[A] е изравнена със s[A] във всяка формула, ако s[A] е изравнена с t[B] в една формула, то t[B] е изравнена със s[A] в същата формула и ако s[A] е изравнена с t[B] в една формула и t[B] е изравнена с u[C] в същата формула, то s[A] е изравнена с u[C] във формулата. Казваме, че формулата F е безопасна, ако:
Казваме, че заявката { t | F} е безопасна, ако формулата F е безопасна. Теорема: Всяка заявка, изразима в релационната алгебра е изразима в безопасното релационно смятане с променливи кортежи. Релационното смятане с променливи върху домени е вид релационно смятане, при което променливите означават компоненти на кортежи. Под атом разбираме един от следните изрази:
op { =, <, >, , , } е операция за аритметично сравнение. Дефиницията за формула е индуктивна и е абсолютно аналогична на дефиницията за формула на релационното смятане с променливи кортежи, с тази разлика, че вместо променлива кортеж вече говорим за променлива върху домен. По-същия начин паралелно се дефинират понятията свободна и свързана променлива на формула. Заявка на релационното смятане с променливи върху домени наричаме израз от вида { x1x2…xn | F }, където F е формула със свободни променливи x1, x2, …, xn. Отговорът на заявката е релацията, съставена от всички кортежи a1a2…an, такива че, замествайки с ai всяко свободно срещане на xi във F за всяко i { 1, 2, …, n } получаваме истинна формула. Както при релационното смятане с променливи кортежи, отговорът на някои заявки може да бъде безкрайна релация. Затова отново се налага да разглеждаме само безопасни формули. Дефиницията е както при релационното смятане с променливи кортежи. Първо се дефинира какво означава променливата x да бъде ограничена в една формула. След това се дефинира какво означава две променливи x и y да бъдат изравнени в една формула. И след това, казваме, че формулата F е безопасна, ако:
Казваме, че заявката { x1x2…xn | F } е безопасна, ако формулата F е безопасна. Теорема: Всяка заявка, изразима в релационното смятане с променливи кортежи е изразима в релационното смятане с променливи върху домени. Следствие: Всяка безопасна заявка, изразима в релационното смятане с променливи кортежи е изразима в безопасното релационно смятане с променливи върху домени. Теорема: Всяка безопасна заявка, изразима в релационното смятане с променливи върху домени е изразима в релационната алгебра. При проектиране на схема на една релация трябва да се избягват следните аномалии:
Общоприетият начин за елиминиране на изброените аномалии е декомпозицията на релациите – една релация се разбива на две нови релации. По-формално, нека R (A1, A2, …, An) е релация. Тогава тя се декомпозира на две нови релации S (B1, B2, …, Bm) и T (C1, C2, …, Ck), ако:
B1, B2, …, Bm.
C1, C2, …, Ck. В много случаи известните факти за реалния свят, че не всяко крайно множество от кортежи може да е екземпляр на дадена релация, дори да имат правилна размерност и стойности от правилните домени. Можем да различим два вида ограничения:
Най-важните ограничения от втория тип са функционалните зависимости. Функционална зависимост в една релация R наричаме твърдение, което е изпълнено за всички възможни екземпляри на R и има следния вид: ако два кортежа имат едни и същи компоненти, отговарящи на атрибутите A1, A2, …, An, то те имат едни и същи компоненти, отговарящи на атрибутите B1, B2, …, Bk. Бележим функционалната зависимост по следния начин: A1A2…An B1B2…Bk. Казваме, че множеството { A1, A2, …, An} от един или повече атрибути на релацията R образуват ключ на R, ако за всеки атрубит B на R е в сила функционалната зависимост A1A2…An B и { A1, A2, …, An} е минимално по включване с това свойство, т.е. за всяко собствено подмножество { Възможно е една релация да има повече от един ключ. Обикновено в такава ситуация се избира един ключ, който се обявява за първичен ключ. Първичният ключ се използва при съхранение на релацията. Понякога терминът възможен ключ се използва за означаване на произволен ключ на релацията, а терминът ключ се запазва за първичния ключ. Казваме, че множеството { A1, A2, …, An} от атрибути на релацията R образуват суперключ на R, ако за всеки атрубит B на R е в сила функционалната зависимост A1A2 …An B. С други думи, суперключ на една релация R се нарича множество от атрибути, което съдържа ключ. Ще разгледаме някои правила, чрез които от даден набор функционални зависимости в релация можем да извличаме нови функционални зависимости в тази релация. Функционалните зависимости за една релация често могат да бъдат представени по различен начин. По-формално, казваме че множествата S и T от функционални зависимости са еквивалентни, ако множеството от екземплярите на релацията, удоволетворяващи S съвпада с множеството от екземплярите на релацията, удоволетворяващи T. По-общо, множеството функционални зависимости T следва от множеството от функционални зависимости S, ако всеки екземпляр на релацията, който удоволетворява S, удоволетворява и T. Бележим S T. Естествено, S T и T S тогава и само тогава, когато S и T са еквивалентни.
Тогава можем да заменим тази функционална зависимост със следните функционални зависимости: A1A2…An Bi, i = 1, 2, …, m. Това правило наричаме правило за разделяне. Обратно, функционалните зависимости A1A2…An Bi, i = 1, 2, …, m можем да заменяме с една функционална зависимост A1A2…An B1B2…Bm. Това правило наричаме правило за комбиниране. Очевидно е, че и в двата случая полученото множество функционални зависимости е еквивалентно на изходното.
Bi { A1, A2, …, An}. Казваме, че функционалната зависимост A1A2…An B1B2…Bm е напълно нетривиална, ако за всяко i { 1, 2, …, m}, имаме Bi { A1, A2, …, An}. Нека A1A2…An B1B2…Bm е нетривиална функционална зависимост. Тогава можем да премахнем онези Bi, които съвпадат с някое Aj. Получаваме нова напълно нетривиална функционална зависимост A1A2…An C1C2…Ck, която очевидно е еквивалентна на изходната. Това правило наричаме правило за отстраняване на тривиалните зависимости. Нека A1A2…An B1B2…Bm и B1B2…Bm C1C2…Ck са функционални зависимости. Тогава добавяме нова функционална зависимост A1A2…An C1C2…Ck. Това правило наричаме транзитивно правило. Ясно е, че добавената функционална зависимост следва от изходните функционални зависимости, така че получаваме еквивалентно множество от функционални зависимости. Аксиомите на Армстронг са правила, чрез които може да се извлече всяка функционална зависимост, която следва от дадено множество функционални зависимости. Те са следните:
A1A2…An B1B2…Bm.
A1A2…AnC1C2…Ck B1B2…BmC1C2…Ck.
B1B2…Bm C1C2…Ck, то A1A2…An C1C2…Ck. Като цяло нормалните форми са условия, които ако са изпълнени в дадена релация, то в нея със сигурност няма аномалии от определен вид. Целта на декомпозицията е да разбие релациите на по-малки релации, за които е в сила условието за нормална форма. Казваме, че една релационна схема R се намира в първа нормална форма (1NF), ако всичките и домени се състоят от атомарни (неделими) стойности. Казваме, че една релационна схема R се намира във втора нормална форма (2NF), ако за всяка нетривиална функционална зависимост A1A2…An B, която е изпълнена за R имаме, че B е елемент на ключ или { A1, A2, …, An } не е собствено подмножество на ключ. Казваме, че една релационна схема R се намира в трета нормална форма (3NF), ако за всяка нетривиална функционална зависимост A1A2…An B, която е изпълнена за R имаме, че B е елемент на ключ или { A1, A2, …, An } е суперключ. Казваме, че една релационна схема R се намира в нормална форма на Boyce-Codd (BCNF), ако за всяка нетривиална функционална зависимост A1A2…An B, която е изпълнена за R имаме, че { A1, A2, …, An } е суперключ. Естествено, BCNF 3NF 2NF. Лесно може да се покаже, че всяка релационна схема с два атрибута е в BCNF. Многозначна зависимост в една релация R наричаме твърдение, което е изпълнено за всички възможни екземпляри на R и има следния вид: ако компонентите на кортежите, отговарящи на атрибутите A1, A2, …, An съвпадат, то компонентите на кортежите, съответни на атрибутите B1, B2, …, Bm са независими от компонентите на кортежите, съответни на всички останали атрибути. Бележим многозначната зависимост по следния начин: A1A2…An B1B2…Bm. По-прецизно, казваме че многозначната зависимост A1A2…An B1B2…Bm е в сила за една релация R, ако за всяка двойка кортежи t, u в екземпляр на R, които се съгласуват по A1, A2, …, An съществува кортеж v, такъв че:
С други думи при фиксирани стойности на A1, A2, …, An съответните стойности на B1, B2, …, Bm и стойностите на всички останали атрибути се комбинират по всевъзможни начини в различни кортежи на релацията R. Ще разгледаме някои правила за многозначните зависимости, които наподобяват правилата за функционалните зависимости, но има някои разлики. Дефиницията за еквивалентност и следване на множества от функционални зависимости автоматично се пренася и върху многозначни зависимости. Ако за една релация R е в сила многозначната зависимост A1A2…An B1B2…Bm, то за нея е в сила многозначната зависимост A1A2…An C1C2…Ck, където C1, C2, …, Ck съдържат B1, B2, …, Bm и някои от A1, A2, …, An. Също за R е в сила многозначната зависимост A1A2…An D1D2…Dr, където D1, D2, …, Dr са тези от B1, B2, …, Bm, които не са от A1, A2, …, An. Тези две правила наричаме правила за тривиалните зависимости.
A1A2…An B1B2…Bm и B1B2…Bm C1C2…Ck, то за R е в сила многозначната зависимост A1A2…An C1C2…Ck. Това правило наричаме транзитивно правило. Може да се покаже с пример, че за многозначните зависимости не е в сила правилото за разделяне. Aко функционалната зависимост A1A2…An B1B2…Bm е в сила за една релация R, то за R е в сила многозначната зависимост A1A2…An B1B2…Bm. С други думи, всяка функционална зависимост е многозначна. За многозначните зависимости е в сила следното правило за допълнение, което не е в сила за функционалните зависимости: ако за R е в сила многозначната зависимост A1A2…An B1B2…Bm, то за R е в сила многозначната зависимост A1A2…An C1C2…Ck, където C1, C2, …, Ck са всички атрибути на R без A1, A2, …, An, B1, B2, …, Bm.
Казваме, че една релационна схема R е в четвърта нормална форма (4NF), ако във всяка нетривиална многозначна зависимост A1A2…An B1B2…Bm, която е изпълнена за R имаме, че { A1, A2, …, An} е суперключ. Естествено, всяка релация, която се намира в четвърта нормална форма се намира и в трета нормална форма, т.е. 4NF BCNF. Това следва от факта, че всяка функционална зависимост е многозначна. Обратното не е вярно. Всяка релация с два атрибута се намира в четвърта нормална форма, тъй като в нея не може да има нетривиални многозначни зависимости. Нека R (A1, A2, …, An) е релация и R се декомпозира на две релации S (B1, B2, …, Bm) и T (C1, C2, …, Ck). Казваме, че декомпозицията е със съединение без загуба, ако R = S ⋈ T. Теорема: Декомпозицията на релацията R (A1, A2, …, An) на две релации S (B1, B2, …, Bm) и T (C1, C2, …, Ck) е със съединение без загуба тогава и само тогава, когато за R е изпълнена поне една от двете многозначни зависимости { B1, B2, …, Bm} { C1, C2, …, Ck} { B1, B2, …, Bm} - { C1, C2, …, Ck}, { B1, B2, …, Bm} { C1, C2, …, Ck} { C1, C2, …, Ck} - { B1, B2, …, Bm}.
Стратегията за декомпозиция, която възприемаме е следната. Нека A1 A2 …An () B1 B2 …Bm е нетривиална функционална (многозначна) зависимост и { A1, A2, …, An} не е суперключ. Тогава декомпозираме релацията R на следните две релации:
Ако новополучените релации не са в BCNF (4NF), то към тях прилагаме същата процедура. При това, функционалните зависимости в новите релации се изчисляват чрез проектиране на функционалните зависимости от изходната релация. Многозначните зависимости в новите релации, обаче, както вече споменахме може да не се изчерпват с проектираните многозначни зависимости от изходната релация – възможно е съществуването на вградени многозначни зависимости. Процесът на декомпозиране ще е краен, тъй като винаги получаваме релации с по-малко атрибути, а всяка релация с два атрибута е в BCNF (4NF). Ще отбележим, че в общия случай декомпозицията в BCNF (4NF) не е със съединение без загуба на функционалните зависимости. Съществува, обаче, алгоритъм за декомпозиция в 3NF, който е със съединение без загуба и запазва функционалните зависимости. Този алгоритъм в повечето случаи се справя с излишествата, породени от фукционални зависимости. 6. Компютърни архитектури – Формати на данните. Вътрешна структура на централен процесор – блокове и конвейерна обработка, инструкции. Структура и йерархия на паметта. Сегментна и странична преадресация. Система за прекъсване – приоритети и обслужване. Под персонален компютър разбираме изчислителна машина, използвана от един човек, за решаване на специфични, лични алгоритмични задачи и проблеми. Специфичните особености на персоналния компютър са, че той заема малък обем, има проста структура и система от команди, има ограничен обем на основната памет и опростен интерфейс, към който се свързват всички устройства в изчислителната система. Въпреки голямото разнообразие на производители и размери, персоналните компютри се характеризират с еднакъв модел на вътрешна архитектура. Този модел е изграден от три основни компоненти:
|
, 
, …, 
} на { A1, A2, …, An} съществува атрибут B на R, такъв че не е в сила функционалната зависимост