Prädikatenlogik als Regelsprache

  • Regeln als Implikationsformeln der Prädikatenlogik: \[\underbrace{A_1 \wedge A_2\wedge \ldots\wedge A_n}_{\textrm{Rumpf}} \to \underbrace{H_{}}_{\mathrm{Kopf}}\] → Semantisch äquivalent zu Disjunktion: \[ H\vee \neg A_1 \vee\neg A_2\vee \ldots\vee\neg A_n\]
  • Konstanten, Variablen und Funktionssymbole erlaubt 
  • Quantoren für Variablen werden oft weggelassen:
    Variablen als universell quantifiziert verstanden (d.h. Regel gilt für alle Belegungen)
  • Disjunktion mit mehreren nicht-negierten Atomen
    → disjunktive Regel: \[ \underbrace{A_1 \wedge A_2\wedge \ldots\wedge A_n}_{\textrm{Rumpf}} \to \underbrace{H_1 \vee H_2 \vee \ldots\vee H_m}_{\mathrm{Kopf}}\]

Arten von Regeln

Bezeichnungen für „Regeln“ der Prädikatenlogik:
  • Klausel: Disjunktion von atomaren Aussagen oder negierten  atomaren Aussagen 
  • Hornklausel: Klausel mit höchstens einem nicht-negiertem Atom
  • Definite Klausel: Klausel mit genau einem nicht negiertem Atom
  • Fakt: Klausel aus einem einzigen nicht-negiertem Atom
Beispiele:
  • Klausel: \[\mathsf{Person}(x) \;\to\;\mathsf{Frau}(x) \vee \mathsf{Mann}(x)\]
  • definite Klausel: \[\mathsf{Mann}(x) \wedge \mathsf{hatKind}(x,y) \;\to\;\mathsf{Vater}(x)\]
  • Funktionsymbol: \[\mathsf{hatBruder}(\mathsf{mutter}(x),y) \;\to\;\mathsf{hatOnkel}(x,y)\]
  • Hornklausel, "Integritätsbed": \[\mathsf{Mann}(x) \wedge \mathsf{Frau}(x) \;\to\;\]
  • Fakt: \[\mathsf{Frau}(\mathsf{gisela})\]

Datalog

Einschränkung auf Horn-Regeln ohne Funktionssymbole

→ Datalog-Regeln  

Datalog

  • logische Regelsprache, ursprünglich Grundlage deduktiver Datenbanken
  • Wissensbasen („Datalog-Programme“) aus Horn-Klauseln ohne Funktionssymbole
  • entscheidbar
  • effizient für große Datenmengen, Gesamtkomplexität wie OWL Lite (EXPTIME)

Semantik von Regeln

Standardsemantik der Prädikatenlogik!
  • Semantik weithin bekannt und gut verstanden
  • mit anderen prädikatenlogischen Ansätzen kompatibel (z.B.  Beschreibungslogik)
 

Semantik von Datalog

 Semantik definiert über über logische Modelle: 
  • Interpretation \(\mathcal{I}\) mit Domäne \(\Delta_{\mathcal{I}}\)
  • Auswertung von Variablen: Variablenzuweisung \(\mathcal{Z}\) (Abbildung von Variablen auf \(\Delta_{\mathcal{I}}\))
  • Interpretation von Formeln und Termen unter \(\mathcal{I}\) (und \(\mathcal{Z}\)):
    • Interpretation einer Konstante: \(a^{\mathcal{I},\mathcal{Z}} = a^{\mathcal{I}} \in \Delta_{\mathcal{I}}\)
    • Interpretation einer Variable: \(x^{\mathcal{I},\mathcal{Z}} =\mathcal{Z}(x) \in \Delta_{\mathcal{I}}\)
    • Interpretation eines n-stelligen Prädikats: \(p^{\mathcal{I}} \in \Delta_{\mathcal{I}}^n\)
    • \(\mathcal{I},\mathcal{Z}\models p(t_1,\ldots,t_n)\) genau dann wenn \((t_1^{\mathcal{I},\mathcal{Z}},\ldots,t_n^{\mathcal{I},\mathcal{Z}})\in p^{\mathcal{I}}\),
    • \(\mathcal{I}\models B\to H\) genau dann wenn für jede Variablenzuweisung \(\mathcal{Z}\) gilt: entweder \(\mathcal{I},\mathcal{Z}\models H\) oder \(\mathcal{I},\mathcal{Z}\not\models B\).
  • \(\mathcal{I}\) ist ein Modell für eine Regelmenge, wenn gilt: \(\mathcal{I}\models B\to H\) für alle Regeln \(B\to H\) dieser Menge
 

Datalog in der Praxis

Datalog in der Praxis:
  • verschiedene Implementierungen verfügbar
  • Anpassungen für das Semantic Web: Datentypen aus XML Schema, URIs (z.B. IRIS)
Erweiterungen von Datalog:
  • disjunktives Datalog erlaubt Disjunktionen in Köpfen
  • nichtmonotone Negation (keine prädikatenlogische Semantik)
  • Einbindung von Informationen aus OWL-Ontologien (z.B. dl-programs, dlvhex)
    → lose Kopplung von OWL und Datalog (nicht über gemeinsame prädikatenlogische Semantik)