Von Kurt Lautenbach und Michael Dahr*

Neben Daten auch regelbasiertes Wissen zu speichern, ist die Aufgabe von deduktiven Datenbanken, die heute allerdings erst als Prototypen existieren. Ihre Funktionalitaet geht weit ueber das hinaus, was wir heute als Trigger-Funktion kennen. Zudem lassen sie sich als Deduktionskomponenten im Prinzip auf jedes Datenbankmodell aufsetzen.

Datenbanken dienen zur Speicherung und Verarbeitung von Daten. Im allgemeinen ist das Wissen in den Applikationen codiert. Da die Anwendungen unabhaengig voneinander auf ein und dieselbe Datenbank zugreifen koennen, ist die Wissensverarbeitung der Applikationen unter Umstaenden inkonsistent. In deduktiven Datenbanken wird deshalb neben den Daten regelbasiertes Wissen gespeichert, das ebenso wie die Daten vom Datenbank-Management-System (DBMS) verwaltet wird. Dadurch werden invariante Systemeigenschaften, die mit der Datenbank modelliert werden sollen, unabhaengig von den Applikationen. Inkonsistenzen bei der Wissensverarbeitung lassen sich so verhindern.

Das Wissen kann auf unterschiedlichen Ebenen in Form von Datenabhaengigkeiten repraesentiert werden. So stellen funktionale Abhaengigkeiten im relationalen Datenmodell Wissen ueber Attributwert-Abhaengigkeiten von Tupeln einer Relation dar (intrarelationale Abhaengigkeiten). Waehrend funktionale Abhaengigkeiten nur auf Erfuelltheit getestet werden, zaehlen die mehrwertigen bereits zu den tupelgenerierenden Abhaengigkeiten, die es - wie der Name bereits sagt - gegebenenfalls erforderlich machen, dass Tupel generiert werden.

Eine Integration von Experten- und DB-System

Interrelationale Abhaengigkeiten, also Abhaengigkeiten zwischen mehreren Tabellen, werden wegen des befuerchteten hohen Aufwands fuer ihre Ueberwachung meist nicht beruecksichtigt. Als Beispiel sei hier die vieldiskutierte referentielle Integritaet genannt.

Ein deduktives DBMS stellt eine regelbasierte Deduktionssprache sowie einen Ableitungsmechanismus zur Verfuegung, wodurch aus gespeicherten oder bereits abgeleiteten Daten weitere Daten generiert werden koennen. Beispielsweise lassen sich auf der Grundlage des relationalen Datenmodells durch eine in das DBMS integrierte Deduktionskomponente zusaetzliche Moeglichkeiten und Vorteile erzielen.

Das Gesamtsystem wird dann als deduktiv bezeichnet und zaehlt in gewisser Weise zu den aktiven Datenbanksystemen. Dabei stellen deduktive Datenbanksysteme - zumindest ansatzweise - eine Integration von Expertensystemen und Datenbanken dar.

Sowohl Fakten als auch Regeln

Die in einer Datenbank gespeicherten Daten repraesentieren Aussagen ueber Objekte der realen Welt und werden deshalb auch oft als Fakten bezeichnet. Findet man beispielsweise in einer Tabelle ueber dem Relationenformat

"nonstop flug(Ab,Nach, AbTag,AbZeit,AnTag,AnZeit)" einen Eintrag "(Frankfurt,Hamburg,MO, 07:15,MO,08:20",

so laesst sich daraus schliessen, dass es montags einen Direktflug von Frankfurt nach Hamburg gibt, dessen Abflugs- und Ankunftszeit 7.15 Uhr beziehungsweise 8.20 Uhr ist.

In deduktiven Datenbanken wird neben diesem Faktenwissen (eben den Daten) auch Wissen in der Form von (Deduktions-)Regeln fixiert. Mit Hilfe der gespeicherten Daten (extensionale Fakten) und Regeln koennen weitere Daten (intensionale Fakten) abgeleitet werden. In unserer Flugdatenbank dienen beispielsweise die folgenden beiden Regeln zur Definition von Fluegen (mit einer beliebigen Anzahl von Zwischenlandungen) aus Direktfluegen:

"r1: flug(X,Y,AbTag,AbZeit, AnTag,AnZeit) <-

nonstop flug(X,Y,AbTag,AbZeit,AnTag,AnZeit).

r2: flug(X,Y,AbTag,AbZeit, AnTag,AnZeit) <-

flug(X,Stop,AbTag,AbZeit, StopTag,AnStopZeit) &

flug(Stop,Y,StopTag, AbStopZeit,AnTag,AnZeit) &

AnStopZeit<AbStopZeit".

Die Regel r1 besagt, dass jeder Nonstopflug auch ein Flug ist. Mit Hilfe der Regel r2 werden aus Fluegen weitere Fluege abgeleitet. Diese Regel bedeutet, dass ein Flug von X nach Y existiert, wenn es Fluege von X nach Stop und von Stop nach Y gibt, deren Ankunfts- und Abflugszeiten einen Weiterflug am selben Tag ermoeglichen.

Beide Regeln zusammen definieren ein Schema "flug" ueber den Attributen des Schemas "nonstop flug". Die Parameter der Regeln sind Variablen, die beim Ableiten von intensionalen Fakten durch Werte der in den Tabellen nonstop flug und flug gespeicherten Daten ersetzt werden.

Regelvariablen werden durch Tupelwerte ersetzt

Der Ausdruck: "flug(X,Stop,AbTag,AbZeit,StopTag,AnStopZeit)"

wird beim Ableiten wie folgt interpretiert: Gibt es in der Tabelle "flug" zum Beispiel eine Zeile "<Frankfurt,Hamburg,MO,07:15,MO,08:20>", so werden die Regelvariablen durch die Werte des Tupels entsprechend der Reihenfolge ersetzt. X enthaelt somit den Wert Frankfurt, Stop den Wert Hamburg etc.

Koennen alle Variablen der rechten Seite von "<-" (dem Regelkoerper) auf diese Weise mit Werten belegt werden und sind die Vergleichsoperationen (hier zum Beispiel "AnStopZeit<AbStopZeit") erfuellt, so wird das durch die linke Seite von "<-" (dem Regelkopf) definierte Tupel in die Tabelle "flug" ein- gefuegt.

Dieser Prozess ist genau dann beendet, wenn kein weiteres Tupel mehr ableitbar ist.

Vorteile gegenueber den klassischen Views

Verdeutlichen laesst sich das an einem Beispiel: Neben dem oben definierten Direktflug von Frankfurt nach Hamburg seien die Tupel "(Hamburg,Berlin,MO,06:40,MO,07:25)" und "(Hamburg,Berlin,MO,08:50, MO,09:35)" in der Tabelle "nonstop flug" enthalten. Mit Hilfe der Regel r1 sind alle drei Tupel der Tabelle "nonstop flug" auch in der Tabelle "flug" vertreten. Zusaetzlich kann das Tupel "(Frankfurt,Berlin,MO,07:15,MO,09:35)" mit Hilfe der zweiten Regel abgeleitet werden, denn es gilt nach Anwendung der ersten Regel:

"flug(Frankfurt,Berlin,MO, 07:15,MO,09:35) <-

flug(Frankfurt,Hamburg,MO, 07:15,MO,08:20) &

flug(Hamburg,Berlin, MO,08:50,MO,09:35) &

08:20<08:50".

Der erste Eintrag des Flugs von Hamburg nach Berlin kann nicht benutzt werden, da dessen Abflugszeit von Hamburg vor der Ankunftszeit des Flugs von Frankfurt in Hamburg liegt und somit die Vergleichsoperation im Regelkoerper unerfuellt ist. Die abgeleiteten Fakten lassen sich entweder in intensionalen Tabellen speichern oder aehnlich den View-Definitionen in relationalen Datenbanken benutzen, die meist erst bezueglich gegebener Anfragen eva- luiert werden.

Hier stellt sich sofort die Frage, welche Vorteile ein deduktiver Ansatz im Datenbankbereich gegenueber klassischen Views bietet, wie sie beispielsweise mit SQL definiert werden koennen. Der wichtigste Aspekt ist die Ausdrucksstaerke (expressive Power) einer Datenbanksprache. Im Gegensatz zu SQL sind die logikbasierten Deduktionssprachen berechnungsuniversell: Alle berechenbaren Funktionen koennen mit ihnen ausgedrueckt werden.

Dieser Unterschied zeigt sich bereits in unserem Flugbeispiel, wo durch die Regel r1 und die rekursive Regel r2 alle Fluege mit beliebig vielen Zwischenlandungen abgeleitet und gegebenenfalls in die Tabelle "flug" eingefuegt werden. Dies kann in SQL nur fuer eine fest vorgegebene Anzahl von Zwischenlandungen ausgedrueckt werden.

Der allgemeine Fall (der einer Huellenberechnung entspricht) laesst sich in SQL nicht formulieren.

Die Anfrage "Welche Fluege gibt es mit genau einer Zwischenlandung?" kann entsprechend der Regel r2 in SQL folgendermassen als View definiert werden:

"CREATE VIEW flug mit einer zwischenlandung AS

SELECT f1.Ab,f2.Nach, f1.AbTag,f1.AbZeit,f2.AnTag, f2.AnZeit

FROM nonstop flug f1, nonstop flug f2

WHERE (f1.Nach=f2.Ab) AND (f1.AnTag=f2.AbTag) AND (f1.AnZeit<f2.AbZeit)".

Ein zu r2 aequivalentes SQL-Statement fuer eine beliebige Anzahl von Zwischenlandungen existiert jedoch nicht.

Allerdings haben SQL und die Regelsprache etwas gemeinsam: Beide Sprachen sind deklarativ; das heisst, der Benutzer beschreibt (deklarativ) das gewuenschte Ergebnis - nicht den Loesungsweg. Genau wie Views koennen auch die abgeleiteten Tabellen mit Hilfe von SQL abgefragt werden. Als Anfragesprache laesst sich sowohl SQL als auch die Regelsprache verwenden.

Eindeutige Ergebnisse lassen sich ableiten

Des weiteren koennen mit Deduktionsregeln verknuepfte Fakten repraesentiert und abgeleitet werden. Dies ist besonders dann wichtig, falls ueber das zu modellierende System nur unvollstaendiges Wissen vorhanden ist. Besonders haeufig treten solche Situationen auf, wenn Datenbanken fuer naturwissenschaftliche Zwecke angelegt werden sollen, beispielsweise Gen-Datenbanken. Fuehrt eine Analyse nicht zu einem eindeutigen Ergebnis, so ist es oft dennoch sinnvoll, die moeglichen Alternativen in einer Datenbank zu speichern, um daraus mit Hilfe von Deduktionsregeln weitere Konsequenzen (intensionale Fakten) ableiten zu koennen.

Dies soll wieder an einem einfachen Beispiel veranschaulicht werden. Es sei das nicht eindeutige Resultat einer Untersuchung, dass ein Patient p1 an einem Grippevirus "Grippe A" oder "Grippe B" leidet. Als disjunktives Faktum wird dies so dargestellt: "resultat(p1,Grippe A)" oder "resultat(p1,Grippe B)". Hierbei kann "resultat" wieder als Tabelle einer relationalen Datenbank verstanden werden.

Auch negative Fakten sind nutzbar

Weiter nehmen wir an, dass die folgenden Regeln bezueglich der angenommenen Datenbank formuliert sind: "indikation(Patient,multi forte)<-resultat(Patient,Grippe A) und indikation(Patient,multi forte)<- resultat(Patient,Grippe B)", wobei "multi forte" ein spezielles Antibiotikum darstellen soll. Die erste Regel besagt, dass ein "Grippe A"-Patient mit "multi forte" behandelt werden kann. Entsprechendes besagt die zweite Regel fuer "Grippe B"-Patienten. Obwohl nichts ueber das spezifische Grippevirus unseres Patienten bekannt ist, kann mit Hilfe des in Form von Regeln formulierten Wissens abgeleitet werden, dass die Grippe unseres Patienten mit "multi forte" behandelt werden kann, weil dieses Medikament gegen beide Grippeviren einsetzbar ist. Bisher haben wir nur positive Fakten, die also in der Datenbank gespeichert sind oder mit Hilfe der Regeln und der Datenbank abgeleitet werden koennen, zur Deduktion von intensionalen Fakten benutzt. Mit Hilfe von Default-Regeln, die eine konstruktive Negation implementieren, koennen jedoch auch nicht in der Datenbank gespeicherte Fakten (negative Fakten) zur Deduktion benutzt werden.

So koennte ein Abkommen zwischen einer Bahn- und einer Fluggesellschaft wie folgt lauten: "Zwischen den wichtigsten Staedten gibt es pro Tag mindestens eine Bahn- oder Flugverbindung." Ein Passagier, der keine Flugverbindung von Frankfurt nach Koblenz im Flugplan findet, kann aufgrund des Abkommens schliessen, dass es eine Bahnverbindung zwischen beiden Staedten gibt.

Die beiden Deduktionsregeln zu diesem Abkommen lauten unter der Annahme einer moeglicherweise verteilten Datenbank: "bahn verbindung(A,B)<-nicht flug verbindung(A,B) und flug verbindung(A,B)<-nicht bahn verbindung(A,B)", wobei A und B Variablen sind, die als Werte Staedte annehmen koennen. Nicht "flug verbindung(Frankfurt,Koblenz)" trifft zu, wenn es keinen Eintrag "(Frankfurt,Koblenz)" in der Tabelle "flug verbindung" gibt. In diesem Fall kann mit Hilfe der ersten Regel abgeleitet werden, dass eine Bahnverbindung von Frankfurt nach Koblenz existiert.

Die hier verwendete Negation entspricht allerdings nicht ganz der in der Logik gebrauchten Negation, da in der Datenbank keine Eintraege ueber nicht vorhandene Verbindungen gespeichert sind. Diese sind nur mit Hilfe der Default-Negation ableitbar, die im Alltag auch oft angewendet wird: Findet man in einem Fahrplan keine Verbindung von Frankfurt nach Koblenz, so nimmt man an, dass es keine solche Verbindung gibt.

Im Gegensatz zu objektorientierten stellen deduktive Datenbanken eine Weiterentwicklung der bereits existierenden Datenbanksysteme um Deduktionskomponenten dar. Sie sind mehr oder weniger unabhaengig von einem speziellen Datenmodell und besitzen eine formale Grundlage, die in der ersten Stufe der Praedikatenlogik wurzelt.

Darin unterscheiden sich die deduktiven Komponenten von den oft als Trigger bezeichneten Regeln, die bereits heute in DBMS realisiert sind. Die Trigger sind aktionsgesteuert und imperativ. Sie realisieren Konstrukte nach dem Schema "if (condition) then (action)" und besitzen im allgemeinen nur eine nichtdeterministische Semantik. Trotzdem lassen sich mit Triggern recht elegant und einfach Integritaetsbedingungen wie die referentielle Integritaet formulieren und ueberwachen.

In vielen Bereichen koennen sich beide Arten von Regeln in einem geordneten Systemablauf, in dem zum Beispiel getrennte Aktivierungspunkte (assertion points) sowohl fuer Trigger als auch fuer Deduktionsregeln in Transaktionen vereinbart werden, gegenseitig ergaenzen. Weiterhin koennen Deduktionskomponenten zur Ueberwachung von Integritaetsbedingungen sowie zur Schemaintegration in foederierten (verteilten) Datenbanksystemen benutzt werden.

Mit Hilfe von Petri-Netzen lassen sich die Regeln nicht nur grafisch darstellen, sondern auch evaluieren, simulieren und analysieren. Aehnlich wie zum Entwurf von relationalen Datenbanken Entity-Relationship-Diagramme benutzt werden, koennen Petri-Netze zum Entwurf von Wissensbasen herangezogen werden.

Obwohl deduktive Datenbanken im universitaeren Bereich schon recht lange untersucht und diskutiert werden, gibt es heute unseres Wissens nach kein Produkt, das eine solche Deduktionskomponente enthaelt. An zahlreichen Universitaeten existieren jedoch Prototypen deduktiver Datenbanksysteme - auch solche, die auf Petri-Netzen basieren.

*Professor Dr. Kurt Lautenbach und sein Mitarbeiter Dr. Michael Dahr sind am Institut fuer Software-Technik der Universitaet Koblenz-Landau fuer Datenbanken und Petri-Netze zustaendig.