• W Datalogu klauzule zapisujemy jako reguły.

• Każdy predykat jest

  • albo ekstensjonalny: zdefiniowany wyłącznie przez fakty zapisane w bazie danych,

  • albo intensjonalny: zdefiniowany wyłącznie przez reguły.

• Reguły mają nieco zmienioną postać zapisu następnik <- poprzednik AND ...

  przy czym zarówno następnik jak i poprzedniki mają postać wzorców, na przykład P(?x,?y,?z) <- Q(?x,?y,?z) AND x > 10

• Ponieważ takie reguły, podobnie jak klauzule, odpowiadają implikacjom z logiki, posiadają one zarówno interpretację logiczną jak i proceduralną.

• Na przykład regule

  Dziadek(?x,?z) <- Ojciec(?x,?y) AND Ojciec(?y,?z)
  

  odpowiada implikacja ∀x,y,z Ojciec(x,y) ∧ Ojciec(y,z) → Dziadek(x,z)

• Jeśli reguła nie zawiera poprzedników, to jej następnik jest zawsze spełniony.

• Podobnie jak fakty, reguły przechowuje się także w bazie danych.

• Reguła pasuje do zapytania, jeśli jej konkluzja pasuje do zapytania.

• Znajdowanie odpowiedzi na zapytanie przy użyciu reguł polega na znalezieniu reguł pasujących do zapytania i dla każdej z nich wyszukanie w sposób spójny (tzn. tak, żeby wartości zmiennych były zgodne) odpowiedzi na podzapytania powstałe z przesłanek (czyli rekursja :-) i złożenie otrzymanych wyników, podstawiając otrzymane wartości zmiennych na zmienne w konkluzji.

• Ostateczną odpowiedzią na zapytanie jest lista wyszukanych faktów (dla reguł będą to konkretyzacje ich konkluzji).

• Pozwalają otrzymywać odpowiedzi wymagające domknięcia przechodniego.

• Przykład:

  • Mamy tabelę Zawiera(obiekt,składnik,ile) dotyczącą pojazdów (np. rowerów, sanek itp.) podającą obiekty i ich bezpośrednie składowe.

  • Chcemy otrzymać informację o wszystkich częściach wchodzących w skład obiektu 'rower'.

Zawiera

• Definicja w Datalogu

  Czesci(?calosc,?czesc)
    <- Zawiera(?calosc,?czesc,?_).
  Czesci(?calosc,?czesc)
    <- Zawiera(?calosc,?skladnik,?_)
       AND Czesci(?skladnik,?czesc).
  

• i samo zapytanie

  Czesci('rower',?co) ?
  

• W odróżnieniu od programowania w logice w Datalogu nie używa się nawracania.

• Budowa odpowiedzi odbywa się bottom-up: rozpoczynamy od pustej relacji Czesci i iteracyjnie dodajemy do niej wszystkie wiersze, które w tym momencie można otrzymać z reguł.

• Optymalizacja: w kążdym kroku używam reguł tylko dla wierszy dodanych w poprzednim kroku.

• Zauważmy, że jest to typowy algorytm wyznaczania minimalnego punktu stałego (tzw. minimalnego modelu).

• Z otrzymanej ekstensji relacji wybieramy tylko wiersze pasujące do zapytania.

• Rozpoczynam od pustej tabeli Czesci.

• Krok 1: z pierwszej reguły dodaję do niej wiersze <'rower','koło'>, <'koło','piasta'>, <'koło','obręcz'>, <'obręcz','szprycha'>, <'koło','opona'>, <'rower','rama'>, <'rama','siodełko'>, <'rama','kierownica'>.

• Krok 2: używając drugiej reguły dodaję wiersze <'rower','piasta'>, <'rower','obręcz'>, <'rower','opona'>, <'rower','siodełko'>, <'rower','kierownica'>, <'koło','szprycha'>.

• Krok 3: używając drugiej reguły dodaję wiersz <'rower','szprycha'>.

• Krok 4: ponieważ żadna reguła nie produkuje już nowych wierszy, kończę iterację i wybieram wiersze <'rower','koło'>, <'rower','rama'>, <'rower','piasta'>, <'rower','obręcz'>, <'rower','opona'>, <'rower','siodełko'>, <'rower','kierownica'>, <'rower','szprycha'>.

• Zapytania rekurencyjne w SQL-3 definiuje się konstrukcją

  WITH [RECURSIVE] R(...) AS
      zapytanie używające R
    SELECT ...;
  

• Można tak zdefiniować kilka pomocniczych relacji wzajemnie rekurancyjnych.

• Zapiszemy nasze zapytanie z Datalogu w SQL

  WITH RECURSIVE Czesci(calosc,czesc) AS
      (SELECT obiekt,skladnik FROM Zawiera)
      UNION
      (SELECT obiekt,czesc
       FROM Zawiera, Czesci
       WHERE skladnik = calosc)
    SELECT czesc FROM Czesci
    WHERE calosc = 'rower';
  

• W poprzednikach reguł Datalogu można poprzedzać predykaty negacją NOT.

• Taki literał jest spełniony, jeśli ta negacja jest prawdziwa dla tego predykatu w minimalnym modelu.

• Aby można to było sprawdzać, program z negacjami musi być stratyfikowalny: reguły predykatów intensjonalnych dzielimy na warstwy tak, by

  • Definicja predykatu nie była w wyższej warstwie, niż jego wykorzystanie w definicjach innych predykatów.

  • Negacja predykatu występowała w wyższej warstwie niż jego definicja.

• Minimalne punkty stałe wyznaczamy kolejno poczynając od najniższej warstwy.

• Podobne ograniczenie na poprawność rekursji z negacją obowiązuje w SQL-3.