68322 ullman137 (2)

♦    Datalog: Jest to inna, tym razem wywodząca się z logiki, postać języka zapytań dla modelu relacyjnego. W Datalogu definiuje się predykaty i relacje za pomocą reguł, w których występują podzadania tworzące treść reguły. Podzadania i nagłówek są atomami, a atom jest (czasami zanegowanym) predykatem, którego wartość zależy od szeregu argumentów. Wszystkie te zapytania, które można zdefiniować w postaci wyrażeń algebraicznych, można także wyrazić w Datalogu.

♦    Datalog rekurcncyjny. W regułach Datalogu można korzystać z reku-rencji, tzn. żc definicja relacji zawiera jej nazwę. Interpretację rcku-rencji w Datalogu stanowi najmniejszy punkt stały, czyli najmniejszy zbiór krotek definiowanej relacji, który spraw ia, źe relacja z nagłówka jest równa wynikowi wyliczonemu w treści reguły.

♦    Negacja warstwowa. W przypadku gdy reguła zawiera zarówno negację. jak i rekurencję, punkt stały nic musi być jednoznacznym rozwiązaniem (może ich być więcej niż jedno). Zdarza się więc. że taka reguła nie może zostać zinterpretowana Stąd zrodziło się pojecie negacji warstwowej. Dzięki temu można w niektórych regułach zawierających negację i rekurencję określić, które rozwiązanie stałopunk-towc jest właściwą interpretacją reguły.

♦    Relacje jako wielozbiory: W komercyjnych systemach baz danych relacje są traktowane jako wielozbiory, ponieważ dopuszczalne jest tam powtarzanie się w relacji tych samych krotek. Funkcje algebry relacji można rozszerzyć na pojęcie wiclozbioru, ale niektóre prawa algebraiczne przestają wówczas obowiązywać.

♦    Relacje w komercyjnych systemach baz danych: W komercyjnych systemach baz danych poza modelem wiclozbioru są dostępne polecenia, które nie mają odpowiedników ani w algebrze relacji, ani w Datalogu. Te polecenia obejmują: wstawianie, usuwanie oraz modyfikowanie krotek z relacji, agregacje wartości w relacji, a także krotki z wartościami pustymi.

4.9. Literatura do rozdziału 4

Podstawowy raport dotyczący modelu relacyjnego (4) zawiera także opis algebry relacji Natomiast język zapytań logiki nic ma już. tak jasno sprecyzowanego momentu powstania. We wczesnych pracach dotyczących modelu relacyjnego Codd (5) wprowadził rachunek relacyjny, który był pewną postacią logiki pierwszego rzędu Rachunek relacyjny jest językiem wyrażeń, przypominającym trochę algebrę relacji i. co udowodniono, o mocy ekspresji równoważnej algebrze relacji.

Powstanie Datalogu, którego składnia bazuje na regułach, było inspirowane językiem programowania Prolog Jest to język mocniejszy niż rachunek relacyjny, ponieważ zawiera rekurencję Praca [6] jest bardziej związana z ideą języka logiki jako języka zapytań; w pracy [2] natomiast więcej uwagi przywiązano do rozważania pojęć logiki w kontekście baz danych A pierws/ą pracą, która opisuje zastosowanie zapytań do określenia więzów, jest [8].

Pomysł dokonywania właściwego wyboru rozwiązania stałopunktowego za pomocą gacji warstwowej /ostał zaprezentowany w opracowaniu (3], natomiast zastosowanie podejścia w Datalogu /.ostało po ru/. pierwszy przedstawione niezależnie w pracach (II oraz 110]. Praca (10) zawiera opis zagadnień dotyczących negacji warstwowej, związ między algebrą relacji, Datalogicm u rachunkiem relacyjnym, a także przetwarzania i DauJogu zawierających negacje lub bez negacji.

I Apt K R., Blair H., Walker A.: Towards a theory of dcclarativc knowlcdge, w Foundai oj Dtduclivt databases and Logic Programming (J Minklcr, cd.) s 89-148, Mor •Knufman, San Francisco, 1988.

2.    Bancilhon F., Romakrishnan R. An amateufs introduction to rccursivc qucr>-proces slratcgics: ACM StGMOD Intl. Conf On Management of Data. s 16-52. 1986.

3.    Chandra A K . Harc! D.: Structurc and complc.\ily of relational ąuertes. J. Computer System Sciences 25:1, s. 99-128

4.    Codd K. F.: A relational model for large shared data banks, Comm ACM 13:6, S. 377-1970.

5.    Codd E. F.: Relational complctcness of databasc sublanguages, w Database Sys, (R Rustin. cd.). Prentice Hall, Englewood Cliffs, NJ, 1972.

6.    Gallairc H. Minker J.: Logic of databases. Plenum Press, New York, 1978.

7.    Naqvi S.: Negation as failure for first-order ąuerics. Proc Fifth ACM Symp. On Princt of Databasc systems, $tr. 114-122, 1986.

8.    Nicolas J. M.: Logic for improving integrity chccking in relational databases. Acta o manca 18:3, S. 227-253, 1982

9.    Ullman J. D.: Pnnctples of Database and KnowleJge-Basc Systemu, Volumc I. Comp Science Press, New York, 1988

10.    Van Gcldcr A Negation as failure using tight dcrivations for generał logie progn w Foundations of Deductlw databases and Logic Programming (I Minklcr, cd ) y 176. Morgan-Kaufman. San Francisco. 1988