left up right

4. Logik-Datenbanken:


Die Begriffe  "Logik-Datenbank", "deduktive Datenbank", "Wissenssysteme",..., u.ä., wurden Mitte der 80er Jahre eingeführt. In dieser Zeit wurden große Fortschritte in der sogenannten "Künstlichen Intelligenz" Forschung, und ganz besonders im Teilbereich der logischen Programmierung (LISP, PROLOG,...) gemacht. Bei Logik-Datenbanken kommen genau diese Entwicklung zu tragen. Logik-Datenbanken, oder genauer deduktive Datenbanken, überdecken die Fachgebiete der Datenbanken, der Expertensysteme (Wissensrepräsentation ausschließlich in Regeln und Listen) und der logische Programmierung. Dabei vollzieht sich die Änderung zur herkömmlichen Datenbank nicht so sehr in den gespeicherten Daten - man kann ohne weiters auch eine relationale Datenbank verwenden - sondern in einer Erweiterung des DBMS. Es kann gesagt werden, dass sich die "Sichtweise" der Daten vom DBMS aus entscheidend ändert.
 

4.1. Modellsicht versus Beweissicht:

Bei herkömmlichen (relationalen) DBMS wurden die Daten als direktes Modell, oder möglichst isomorphe Abbildung, der Wirklichkeit gesehen. Jeder Datensatz entspricht darin einem (Elementar-)Satz, welcher eine Tatsache der Wirklichkeit beschreibt. Will man etwas in diesen Daten suchen, so muss man sich mit denen in der Datenbank abgelegten "Satz-Fragmenten" begnügen. D.h. alles was abgefragt werden kann muss vorher eingegeben werden. Es soll hier aber nochmals erwähnt werden, dass auch relationale Datenmodelle auf den Grundprinzipien der Logik basieren, jedoch nur rein extensionale Fakten zugelassen werden.

Sieht man die Datenbank (Daten und DBMS) aber als Beweisapparat, so ändert sich das Datenmodell in wesentlichen Punkten. Der extensionale Anteil der Daten bleibt im wesentlichen gleich, nur werden die Tupel nun als Basisaxiome eines logischen Kalküls betrachtet. Diese werden in der Datenbank um  intensionales Wissen erweitert. Diese intensionalen Teile - die Folgerungs- bzw. Umformungsregeln - erlauben es nicht nur direkt auf die extensionalen Fakten zuzugreifen, sondern auf neue Fakten zu schließen. Die Fakten, die durch die Daten in der Datenbank repräsentiert werden, werden  um den Teil erweitert, der mittels der Schlussregeln erzeugt werden kann. Dies ergibt die sogenannte "deduktive Hülle" an. Ausserdem wird meist angenommen, dass alle Fakten, die nicht in der deduktiven Hülle enthalten sind, als nicht zutreffend, also "falsch", einzustufen sind (man spricht hier von der "closed world assumption").
Man kann auch sagen, dass sich die Daten in der Datenbank aus Fakten (den Extensionen) und aus Wissen (den Intensionen) zusammensetzen. Dieses Wissen ist meist als Regeln formalisiert, welche Erlauben durch Umformung bestehender Fakten, neue Fakten zu erzeugen. Um Regeln formalisieren zu können, muss man zuvor aber allgemeine Gesetzmäßigkeiten in der Wirklichkeit, oder in der abstrahierten Struktur der Wirklichkeit, erkannt haben. Die Logik (meist Prädikatenlogik 1. Stufe) kommt dort zum Einsatz, wo Fakten und Wissen formalisiert werden und wo danach über Anwendung der Regeln auf die bestehenden Fakten hypothetische Fakten bewiesen oder widerlegt werden sollen.

Als logischer Kalkül kommen im wesentlichen die Aussagenlogik, einstufige und mehrstufige Prädikatenlogiken zum Einsatz. Diese "klassischen Logiken" können aber je nach Anspruch und Aufgabe der Datenbank so erweitert sein, dass sie auch z.B. ungenaues, mögliches oder widersprüchliches Wissen beinhalten können. Man verlässt dann den Bereich der klassischen Prädikatenlogik und verwendet dann z.B. stochastische, modale oder nonmonotone Kalküle, die allesamt zu den nichtklassischen Logiken zählen (mehr dazu weiter unten).

Da der Beweisprozess automatisch, eben durch das DBMS, ablaufen soll wurden mehrere Techniken entwickelt, die einen solchen automatische Beweis ermöglichen, also deduktive Schlüsse aus den vorhandenen Fakten ableiten bzw. berechnen können. Im folgenden Abschnitt sollen die begrifflichen Grundlagen der wichtigsten, in deduktiven Datenbanken verwendeten, Techniken besprochen werden.
 

4.2. Horn-Klausen, PROLOG, DATALOG:

Der Kalkül der Aussagenlogik behandelt logische Aussagen, welchen semantisch immer einer von zwei möglichen Wahrheitswerten ("wahr", "falsch") zugewiesen werden kann. Komplexere Sätze entstehen durch Verknüpfung einfacher Aussagen mittels der logischen Konnektive "und", "oder", "nicht" und der "Implikation". Als Schlussregel kommt hauptsächlich der "Modus Ponens" zum Einsatz, der wie folgt lautet: P, P -> Q  |- Q  (wenn P wahr, und P impliziert Q, dann ist auch Q wahr; |- bezeichnet das Metasymbol der Ableitbarkeit).
Prädikatenlogik erster Stufe stellt (vereinfacht gesehen) eine Erweiterung der Aussagenlogik um Variablen und Quantoren (Existenz- und All-Quantor) dar. Als weitere logische Satzbausteine gibt es noch die Prädikate. Hier kann bereits eine Analogie zum relationalen Modell erkannt werden, wo die  Relationen aus Tupeln aufgebaut sind. Prädikate symbolisieren im Prinzip genau solche relationalen Verknüpfungen. Quantifizierte Formeln der Prädikatenlogik entsprechen dann den Abfragen und Integritätsbedingungen relationaler Datenbanksprachen.
Da das volle System der Prädikatenlogik zwar sehr mächtig, aber formal auch schwer bearbeitbar ist, verwendet man Systeme mit reduzierter Komplexität, bei denen gewisse Einschränkungen in der Syntax die Anwendung automatischer Ableit- bzw. Beweissysteme erlauben. Die wohl häufigste Einschränkung ist die auf sogenannte Horn Klausen. Unter einer Klause versteht man dabei eine Formel die sich aus der Disjunktion von Satzbausteinen zusammensetzt. Eine Horn-Klause ist dann eine Klause mit mindestens einem positiven (also nicht negierten) Satzbaustein. Berücksichtigt man, dass  A -> B <=> B v ~A und dass ~A v ~B <=> ~(A^B) so kann man die Hornklause wie folgt umformen:

A v ~B v ~C v ~D v....
A <- ~(~B v ~C v ~D v...)
A <- ~~(B ^ C ^ D ^....)
A <- B ^ C ^ D

Im Formalismus von PROLOG oder DATALOG würde diese Formel dann so aussehen:

A :- B, C, D, ...

A wäre der sogenannte Kopf der Klause ("Head") und Teil rechts von :- nennt man den Körper ("Body"). Der Kopf wird also gewissermaßen über seinen Körper definiert. Mehrere solcher Definitionen ergeben ein PROLOG Programm. Eine Klause ohne Körper nennt man Einzelklause ("Unit Clause", ist immer "wahr"), eine ohne Kopf wird als Abfrage ("Query" oder "Goal") bezeichnet.

Die Einzelklausen in einem logischen Programm stellen somit den extensionalen Anteil der Datenbank dar. Alle anderen Klausen sind dann der intensionale Anteil. Dieser intensionale Anteil repräsentiert in Analogie zum relationalen Datenbankmodell die Integritätsbedingungen, und darüber hinaus auch abgeleitete Fakten und erlaubt aber auch Rekursion.

Die Beweisverfahren für Systeme der Prädikatenlogik erster Stufe basieren auf der Resolution. Das Grundprinzip das dahintersteht ist, dass ein Statzbaustein einer disjunkiven Kette wahr sein muss, wenn alle anderen Elemente der mit Disjunkten verbundenen Formel als falsch bewiesen werden können. Wendet man das Verfahren der Resolution auf Horn Klausen an erhält man Beweissysteme, welche hauptsächlich im Bereich der logischen Programmierung (und auch bei PROLOG) angewendet werden.
Ein PROLOG-Programm besteht also aus einer Menge von Axiomen (den Definitionen). Das DBMS, oder in diesem Kontext auch PROLOG Interpretierer oder auch Inferenzmaschine genannt, ermöglicht es mit Hilfe der Axiome Theoreme zu beweisen. Dies entspricht eine Abfrage im herkömmlichen datenbankkontext. Wenn man das PROLOG-Programm mit P bezeichnet und die Abfrage mit Q, dann versucht das DBMS den Satz P ^ ~Q zu widerlegen. P besteht aus der Konjunktion von Axiomen, ist also per Definition immer wahr. Um also P ^ ~Q "falsch" zu haben, muss ~Q "falsch" sein und somit Q "wahr". Eine detaillierte Darstellung von PROLOG findet sich in ERTL 1988; über Details der Funktionsweise und unterschiedlichen Methoden von Inferenzmaschinen siehe z.B. COLOMB 1998 oder CREMERS e.a. 1994.

Eine Anpassung der logischen Programmierung an die Bedürfnisse der Datenbankprogrammierung stellt DATALOG dar. Dabei wird PROLOG so weiter eingeschränkt, dass eine einfachere und effizientere Nutzung des Systems hinsichtlich der zu erwarteten Datenbankfunktionalitäten gewährleistet ist. Im konkreten Fall handelt es sich  in erster Linie um Integritätsbedingungen und die rekursive Verknüpfung diverser Dateninhalte. Da aber DATALOG auf PROLOG aufbaut und somit ebenfalls ein logisches Programmiersystem darstellt, sind natürlich alle Methoden des logischen  Kalküls auch innerhalb DATALOG anwendbar. Dies erlaubt einerseits eine Umformung des logischen Programms entsprechend der Umformungsregeln des Kalküls, sodass die Performanz der Beweismaschine erhöht wird und andererseits ermöglicht der logische Kalkül die Formulierung von Formeln, die in wichtigen Punkten weit über die Aussagekraft von Formeln der relationalen Algebra hinausgehen.
Eine zusätzliche Erweiterung von PROLOG, die für die Anwendung im Datenbankbereich von besonderer Wichtigkeit ist, ist die sogenannte "all_solutions"-Methode. Diese Änderungen in PROLOG ermöglichen  sogenannte "set-at-a-time" Abfragen im Gegensatz zu "clause-at-a-time" (mit gewissen Einschränkungen; siehe unten). Damit ist gemeint, dass in PROLOG ein beliebiger Beweis gesucht wird, und wenn dieser gefunden ist, beendet das System den Beweisprozess. Bei Datenbankabfragen werden aber alle möglichen Beweise gesucht. Man will nicht nur wissen ob eine Abfrage eine Lösung hat, sondern auch wie alle möglichen Lösungen aussehen.

Allgemein gilt, dass PROLOG (mit der "all_solutions"-Methode) die relationale Algebra logisch enthält. Alle Formeln der relationalen Algebra können in solche der Horn-Klausen-Prädikatenlogik umgeformt werden. Andererseits können aber gewisse PROLOG-Formeln, nämlich jene welche Variablen oder Funktionen enthalten, bzw. solche mit rekursiven Definitionen, nicht in die relationale Algebra transformiert werden. PROLOG, aber auch DATALOG, sind also logisch mächtiger und expressiver als die relationale Algebra. Diese Versatilität der Prädikatenlogik erster Stufe ist aber auch gekoppelt an das Problem der Nicht-Terminierung.
 

4.3. Nicht-Terminierung:

Ein allgemeines Problem bei Inferenzmaschinen für Prädikatenlogik erster Stufe, also auch bei PROLOG, stellt die Nicht-Terminierung dar. Es gibt Theoreme, die von einer Inferenzmaschine nicht in einer endlichen Anzahl von Schritten bewiesen oder widerlegt werden können. D.h. dass die Inferenzmaschine bei gewissen Theoremen zu keiner Lösung, also keinem Beweis kommen kann. Dies ist ein Aspekt der Prädikatenlogik erster Stufe die auf die Unvollständigkeitstheoreme Kurt Gödls zurückzuführen ist. Gödl hat gezeigt, dass in einem Kalkül, der ausreichend kompliziert ist (vereinfacht gesagt genügt das Vorhandensein rekursiver Axioms-Definitionen) es immer Theoreme geben wird, die weder bewiesen noch widerlegt werden können. Die Anwendung dieser Unvollständigkeitstheoreme Gödls auf formale Beweisverfahren wurde von Turing mit seinen Turingmaschinen gezeigt (mehr zu diesem Thema findet sich in DEPAULI-SCHIMANOVICH & WEIBEL 1997).
Ein einfaches Beispiel für ein nicht terminierendes logisches Programm mit Resolutionsmethode ist mit fogendem Axiom bereits gegeben: P :- P. Bei einer Abfrage ?~P sollte unter der  " closed world assumtion" (siehe oben) diese mit "wahr" bewertet werden. Im automatisierten Beweisverfahren kommt es hingegen zu einem unendlichen Zirkel.
Genau dieser Aspekt der Nicht-Terminierung macht auch eine "set-at-a-time" Evaluierung (siehe oben) in PROLOG schwierig. Mit der "all-solutions"-Methode kann zwar versucht werden alle möglichen Lösungen zu einer Query zu finden, allerdings liegt im Prinzip der Nicht-Terminierung auch die Möglichkeit, dass gewisse Lösungen nicht in einem endlichen Zeitintervall gefunden werden können. Man kann also in PROLOG nicht bei allen Beweisergebnissen sicher sein auch wirklich alle Lösungen zu einer komplexen Abfrage erhalten zu haben, da es sein kann, dass der Beweisprozess nach einer vordefinierten, endlichen Zeit abbrechen muss (falls er nicht zuvor nach einer endlichen Anzahl von Beweisschritten von selbst terminierte) um nicht unendlich lange im Beweisprozess gefangen zu sein.

In DATALOG wird der formale Apparat der Horn-Klausen von PROLOG noch weiter eingeschränkt, sodass das Problem der Nicht-Terminierung ausgeschaltet wird und echte "set-at-a-time" Abfragen ermöglicht werden. In der striktesten Form beschränkt man sich auf sogenannte "sichere" Horn-Klausen (das sind solche ohne Funktionen, Variablen und ohne Negation). In diesem Fall sind fast alle Axiome die in DATALOG formuliert werden können auch in die relationale Algebra transformierbar. Einzig rekursive Definitionen lassen sich nur eingeschränkt transformieren (nämlich nur dann, wenn auch die relationale Algebra um rekursive Strukturen erweitert wurde). Es gibt aber auch Versionen von DATALOG wo weniger strikte Einschränkungen getroffen werden um gewisse Aspekte im Sprachumfang der Prädikatenlogik erhalten zu können.
 

4.4. Non-Monotonie:

Ein weiters Problem bei logischen Datenbanken stellt die Veränderung der axiomatischen Wissensbasis dar. Logische Programme stellen normaler Weise eine weitgehend statische, weil optimale, Beschreibung der Wirklichkeit dar. Hat man einmal die richtigen Axiome gefunden, dann lassen sich aus diesen alle bestehenden Sachverhalte ableiten. Dieses Grundmodell funktioniert noch recht gut, wenn man es mit einem sehr eingeschränkten Problembereich zu tun hat. Für eine allgemeinere Weltbeschreibung ist aber die Erstellung der axiomatischen Wissenbasis nicht ganz so einfach. Somit ist es bei deduktiven Datenbanken unerlässlich auch nach der ersten Erstellung der Wissensbasis neues Wissen hinzufügen zu können oder auch bestehendes Wissen verändern zu können.
Ein logisches System, das unveränderbar und statisch eine bestimmte Welt beschreibt wird als monoton bezeichnet. Das Gegenteil dazu, also ein System, bei dem sich mit der Zeit Axiome und auch abgeleitete Fakten verändern können wird als non-monoton bezeichnet. Da man eine ewig gültige Beschreibung der Wirklichkeit nur in einer sehr idealisierten Welt finden wird können, ist also bei deduktiven Datenbanken die Erweiterung auf eine non-monotone Sichtweise dringend notwendig. Dabei ist es nun von größter Wichtigkeit, die logische Konsistez der Datenbank, also die Vermeidung von logischen Widersprüchen, zu garantieren. Was bei relationalen Datenbanken mittels Integritätsbedingungen gewährleistet wird, nämlich die Vermeidung von widersprüchlichen und missverständlichen Fakten, wird bei deduktiven Datenbanken  durch Beschränkung auf bestimmte logische Formen (siehe Beschränkungen in DATALOG weiter oben), durch beschränkende Abfragen (was zum Beispiel die genauere Spezifikation gewisser Individuen betrifft; diese werden nach einer Veränderung der Wissenbasis durchgeführt und dürfen keine Lösung haben; wird eine Lösung gefunden, so wird dadurch ein Teil der Wissensbasis identifiziert, der die Integritätsbedingungen verletzt) und durch zusätzliche Methoden die non-monotone  Veränderungen der Wissensbasis erlauben, ermöglicht. Kommt es nämlich zu einem Widerspruch in der Wissensbasis, so lässt sich in weitere Folge jedes beliebige Faktum, also jede beliebige Abfrage beweisen (wegen Axiom: A ^ ~A -> B), was die  Datenbank als nutzlos erscheinen lässt.
Prinzipiell wird bei diesen Methoden entweder versucht die Monotonie des logischen Systems wieder herzustellen, oder aber in einer Erweiterung der klassischen Logik, also in einer non-monotonen Logik zu arbeiten, die trotz (lokaler) Inkonsistenzen eine logische Evaluierung von Sätzen erlaubt.
Im Folgenden soll die sogenannte "belief revision" exemplarisch als Methode für die non-monotone Erweiterung einer deduktiven Datenbank dargestellt werden.

Korrektur von geglaubten Sätzen ("Belief Revision"):

Die sogenannte "belief revision" oder "Korrektur von geglaubten Sätzen". Dabei werden die logischen Sätze in der Wissenbasis nicht als ewig-gültige Wahrheiten betrachtet sonden als sogenannte "beliefs" oder "geglaubte Sätze". Dabei werden gewisse Sätze stärker geglaubt als andere. Zum Beispiel neu hinzugefügte Sätze werden mit größter Sicherheit geglaubt, sodass bei der Verletzung der Konsistenz der Wissensbasis (also bei der Verletzung von Integritätsbedingungen der Datenbank) durch diese neu hinzugefügten Sätze in der Wissensbasis andere weniger stark geglaubte Sätze gesucht werden, deren Entfernung aus dem System die Konsistenz wieder herstellt, bzw. kann auch nach neuen Sätzen gesucht werden, deren hinzufügen zur Wissensbasis die Integrität und Konsistenz wieder herstellt.. Dieser Prozess wird als "belief revision" bezeichnet.
Am Anfang dieser Methode steht die Identifizierung einer Integritätsverletzung durch eine Abfrage einer Integritätsbedingung. Danach werden anhand des Beweises die Bestandteile der Wissensbasis identifiziert, die für die Ermöglichung der Lösung des Beweises maßgebend waren. Je nachdem ob es sich dabei um negierte oder positive Fakten handelt kann man dann entweder die doppelt-negierten Fakten, hinzufügen oder die positiven Sätze aus der Wissensbasis entfernen. Meist gibt es dabei aber mehrere Lösungen, sodass ein Entscheidungsverfahren notwendig ist. Dabei werden den unterschiedlichen Sätzen bestimmte Glaubenswerte (meist als diskrete Zahlenwerte), entweder direkt oder über Glaubens-Relationen, zugewiesen und dann die Teile der Wissensbasis verändert, die die geringeren Glaubenswerte aufweisen. Es handelt sich bei diesem Verfahren also meist um einen halbautomatischen Prozess, bei dem durch Experten bestimmt wird, welche Anteile der Wissensbasis mehr oder weniger stark geglaubt werden, danach automatisch mittels Relationen zusätzliche Abhängigkeiten berücksichtigt werden und Glaubenswerte entsprechend angepasst werden, und am Ende wieder automatisch aufgrund der Analyse des Beweisverfahrens der Integritätsverletzung und den festgelegten Glaubenswerten eine Revision der Wissenbasis vorgenommen wird.

Neben der eben besprochenen Methode gibt es noch eine Vielzahl von Methoden und Erweiterungen zu deduktiven Datenbanken die mit non-monotonen Ansätzen umgehen. Hier eine Aufzählung der wichtigsten Gebiete (aus TROST 1996):

Diese Aufzählung ist natürlich unvollständig, da sich gerade im Bereich non-monotoner Logiken in der Forschung regelmäßig neue Entwicklungen ergeben (mehr zu diesem Thema in GINSBERG 1987 und GENESERTH & NILSSON 1987).

 

4.5. Unvollständiges Wissen:

Relationale Datenbankmodelle beruhen auf der Annahme, dass das Modell eine perfekte Abbildung (möglichst isomorph) der Wirklichkeit darstellt. Darin darf es keine Ungenauigkeiten oder Unsicherheiten in der Beschreibung von Sachverhalten geben. Bei deduktiven Datenbanken stellt sich das wesentlich flexibler dar. So kann man z.B. in einer Datenbanksprache wie DATALOG auch einen Sachverhalt wie A(a) v B(a) beschreiben, der z.B. aussagen könnte, dass man weiss, dass eine Person (a) entweder in Wien (A()) oder in Bregenz (B()) wohnt. Mit weiteren Axiomen könnte dieses "unsichere" oder besser "unbestimmte" Wissen trotzdem zum Beweis einer Hypothese führen und somit sein epistemischen Wert im Zuge eines Beweises voll zur Anwendung kommen. In einer relationalen oder objektorientierten Datenbank ist das kaum möglich, da dort alle Sachverhalte als mehr oder weniger unverrückbare, deterministische "Elementarsätze" beschrieben werden und die Abspeicherung einer Aussage wie "a wohnt in A oder a wohnt in B" durch Integritätsbedingungen und die fehlende Disjunktion bei der Verknüpfung von Records verhindert werden würde.
Weiter Ansätze unsicheres Wissen in Datenbanken abzubilden verwenden meist eine erweiterte logische Sprache wie z.B. probabilistische Modallogiken oder die sogenannte "Fuzzy Logic". Dabei wird der Wahrheitsgehalt, bzw. der Beitrag einzelner Prädikate zum Wahrheitsgehalt bestimmter Elementarsätze (oder Axiome) mittels einer rationalen Funktion mit einem kontinuierlichen Wertebereich zw. 0 und 1 ermittelt. Dabei handelt es sich aber nicht um nichtklassische, also z.B. mehrwertige Logiken, sondern nur um intensionale Erweiterungen der klassischen Prädikatenlogik. Für die endgültige Festlegung des Wahrheitswertes einer Aussage oder Formel wird von den rationalen Werten mittels sogenannter "logischer Evaluierungsfunktionen" auf die diskreten Werte 0 und 1 zurückgerechnet welche den Wahrheitswerten "falsch" und "wahr' entsprechen. Näheres zur Thematik der probabilistischen und fuzzy Datenbanken findet sich in ZANIOLI e.a. 1997 und in RICH & KNIGHT 1991.
 
 
 
 


©Mag.Dr. Alfred Hofstadler : "Datenbanken und Wittgenstein: ontologische Vergleiche",Diplomarbeit an der Universität Wien, März 2001.
 
left up right