Deduktive Datenbanken

Während der letzten 15 Jahre ist die Symbiose von Datenbanksystemen und Logikprogrammierung intensiv untersucht worden, mit dem Ziel traditionelle sowie neue Datenbankanwendungen besser zu behandeln. Dies führte zu Erweiterungen der herkömmlichen, relationalen Datenbankensysteme um regelbasierte Sprachen zur Wissensrepräsentation - die sowohl als Modellierungs- als auch als Anfragesprache verwendet werden - und um Deduktionsmethoden zur Wissensverarbeitung. Als zentrale Konzepte der deduktiven Datenbanken werden in diesem Artikel Ableitungsregeln und Integritätsbedingungen behandelt. Diese Konzepte sind in relationalen Datenbanksystemen nur in sehr eingeschränktem Umfang modellierbar. Der kürzlich entwickelte neue Standard SQL3 für relationale Datenbanken ermöglicht u.a. jetzt aber die Spezifikation von rekursiven Sichten und greift somit das deduktive Konzept der allgemeinen Ableitungsregeln auf. Das ebenfalls neu eingeführte Triggerkonzept ermöglicht eine imperative Spezifikation der Integritätsprüfungen. Deduktive Datenbanksysteme ermöglichen eine wesentliche Erweiterung des Anwendungsbereiches von Datenbanksystemen, und sie können auch die Migration zwischen unterschiedlichen Datenbanksystemen erleichtern.

Eine deduktive Datenbank, die auf einer relationalen Datenbank basiert, besteht aus Tupeln (auch Fakten genannt), sowie zusätzlich Ableitungsregeln und Integritätsbedingungen.

Eine Ableitungsregel ist eine allgemeine Definition, die es ermöglicht, Daten intensional zu spezifizieren, wie etwa die Regel 2Alle Bücher des Springer-Verlages aus der Reihe LNCS sind auf Englisch verfaßt" zur Verwaltung eines Informationssystems über eine Bibliothek. Zum Ausdruck von Ableitungsregeln werden Sprachen mit 2Wenn-Dann-Regeln" verwendet, wie in den Bereichen der Künstlichen Intelligenz (vgl. manche Expertensysteme), der Logikprogrammierung sowie der automatischen Deduktion. Dabei wird ein Tupelkalkül, wie etwa in der bekannten relationalen Sprache SQL, verwendet (z.B. "Buch. Nummer = 1234 and Buch. Sprache = Englisch"), oder ein sogenannter Domänenkalkül (womit das obige SQL-Beispiel als "Buch(1234, Englisch)" ausgedrückt wird), wie in der Logik. Die oben erwähnte Ableitungsregel kann z.B. wie folgt im Domänenkalkül dargestellt werden:
Buch(x, Englisch) <- Verlag(x, Springer),Reihe (x, LNCS)

Rekursive Regeln ermöglichen die intensionale Spezifikation von Daten, die auf Zusammenhängen von unbestimmtem Umfang beruhen, wie etwa die Definition einer Stücklistenauflösung (billofmaterials) oder einer indirekten Flugverbindung mit möglicherweise mehreren Maschinenwechseln. Wie in relationalen Datenbanken wird die Negation als Scheitern interpretiert, d.h. ein negierter Ausdruck wie etwa "not Buch (x, Englisch)" gilt als wahr, wenn für keine Buchnummer "x" der positive Ausdruck "Buch (x, Englisch)" ableitbar ist.

Ableitungsregeln werden bei der Auswertung von Anfragen automatisch eingesetzt, um das intensional dargestellte Wissen effizient wiederzugeben, wie etwa zur Beantwortung folgender Anfrage über in Englisch geschriebene Bücher über Datenbanksysteme (DBS) unter Berücksichtigung der oben erwähnten Regel: 

Buch (x, Englisch), Thema (x, DBS)

Ein Hauptthema der Forschung über deduktive Datenbanken war die Definition von terminierenden und vor allem effizienten Anfrageauswertungsverfahren.

Integritätsbedingungen ermöglichen es, normative Bedingungen auszudrücken, wie etwa folgende funktionale Abhängigkeit zwischen Attributen einer Relation: "Die Nummer eines Buches ist ein eindeutiger Bezeichner des Buches", oder beliebig komplexe Zusammenhänge zwischen Daten: "An jedem Arbeitstag gibt es mindestens einen direkten Flug von einem der drei größten Flughäfen Deutschlands zur Ostküste der USA".Integritätsbedingungen setzen Normen, die die Datenbank nach jeder beliebigen Aktualisierung erfüllen soll. Im Gegensatz zu Ableitungsregeln können Integritätsbedingungen in der Regel zur Beantwortung von Anfragen nicht verwendet werden, weil sie die Daten nicht notwendigerweise eindeutig spezifizieren.

Integritätsbedingungen können anschaulich mit Hilfe von Ableitungsregeln dargestellt werden, deren Konklusionen "falsch" sind, wie etwa in: 

false Reihe <- (x,LNCS), not Thema(x, Informatik)

d.h. "Es gibt kein Buch ,x‘ aus der LNCS-Reihe, welches nicht über Informatik ist". Weitere Hauptbeiträge der Forschung über deduktive Datenbanksysteme sind die Behandlung von uneingeschränkten, allgemeinen Integritätsbedingungen und die Automatisierung der Integritätsprüfung, d.h. der Spezifikation von effizienten, inkrementellen Verfahren zur Auswertung der Integritätsbedingungen nach jeder Aktualisierung. Diese beruhen auf Deduktionsmethoden, die aus deklarativen Integritätsbedingungen, welche als Programmspezifikation dienen, ein aus Triggern bestehendes imperatives Programm zur Integritätsprüfung automatisch generieren.

Im Gegensatz zu Integritätsbedingungen ermöglichen Trigger - wie z.B. in SQL3 vorhanden - nur eine imperative Spezifikation der Integritätsprüfung, aber keine deklarative Definition von Bedingungen. Der Unterschied kann bei komplizierten Integritätsbedingungen wesentlich sein. Wenn komplexe Zusammenhänge zwischen Daten im allgemeinen leicht vom Datenbankdesigner deklarativ spezifiziert werden können, erweist sich eine den Integritätsbedingungen entsprechende, effiziente Spezifikation von Triggern - wenn überhaupt möglich - oft als eine schwierige Aufgabe. Darüber hinaus ist die Aktualisierung von imperativen Integritätsprüfungs-Triggern viel komplexer und fehleranfälliger als eine Änderung von deklarativen Integritätsbedingungen. Text

Objektorientierte Datenmodellierung: Da die „flache" Wissensrepräsentation in der sogenannten "ersten Normalform" in Tupel- und Domänen-Kalkülen zu wenig Strukturierungsmöglichkeiten bietet, sind deduktive und objektorientierte Modellierungs- und Anfragesprachen kombiniert worden, so daß neben den herkömmlichen Daten auch Ableitungsregeln und Integritätsbedingungen in einem objektorientierten Kontext spezifiziert werden können. Man spricht dann von DOOD-Systemen, d.h. deduktiven und objektorientierten Datenbanksystemen.

In den meisten Datenbankanwendungen sind intensionale Spezifikationen konzeptuell allgegenwärtig. Sie werden in nichtdeduktiven Datenbanken durch extensionale, d.h. explizite, Spezifikationen von Tupeln oder Objekten sowie durch spezielle Anwendungsprogramme implementiert, die für jede Anwendung gesondert entwickelt werden müssen. Dabei zeigen sich folgende Nachteile, die von deduktiven Datenbankverwaltungssystemen vermieden werden:

• Abweichung von den tatsächlichen Spezifikationen,
• unsystematische Programmentwicklung,
• stark von der Programmierung abhängende Effizienz,
• Verwaltung der Programme außerhalb der Datenbank,
• imperative statt deklarative Spezifikationen.

Aus der Sicht relationaler Datenbanken ist die Erweiterung einer Datenbank um Ableitungsregeln und (uneingeschränkte) Integritätsbedingungen aus mehreren Gründen natürlich. Zum einen stellen Ableitungsregeln lediglich eine Verallgemeinerung des im relationalen Modell vorhandenen Begriffes der "Sicht" (view) dar. Zum anderen war ein allgemeiner Ansatz für Integritätsbedingungen bereits ein Ziel der relationalen Datenbanken, das bisher nur teilweise realisiert worden ist. Intensionale Darstellungen haben nicht nur den Vorteil, konzeptuell natürlicher zu sein als traditionelle, extensionale Datenbankspezifikationen. Sie haben den zusätzlichen Vorteil, oft eine wesentliche Datenkompaktierung zu ermöglichen. Kompaktierungsfaktoren von 10 bis mehrere 100 sind in Anwendungen nicht selten, die - wie etwa Fahrpläne - eine reguläre Stuktur aufweisen. Weniger Platz ist notwendig, um z.B. die folgende Regel zu spezifizieren: "12 Minuten nach jeder vollen Stunde gibt es einen Flug von München nach Frankfurt/Main", als die Angaben zu allen solchen Flügen mehrfach zu speichern.

Klassische Datenbanken, wie etwa Verwaltungsdatenbanken, werden intern in Unternehmen eingesetzt, z.B. zur Verwaltung von Personaldaten, Bankkonten oder Versicherungspolicen. Während des letzten Jahrzehnts wurden zunehmend Informationssysteme für ein breites Publikumangeboten, z.B. öffentliche Verkehrsinformationssysteme. Weil sie eine deklarative Modellierung ermöglichen, sind für solche Anwendungen deduktive sowie relationale Datenbanksysteme sehr passend. Neuerdings setzen sich Informationssysteme durch - auch übers Internet zugreifbar - die nicht nur Auskünfte geben, sondern auch komplexe Transaktionen wie etwa Buchungen von kompletten Flugreisen oder Bestellungen bei einem Versandhaus ermöglichen. Für Anwendungen aus diesem Bereich erweist sich der deklarative Ansatz der deduktiven Datenbanksysteme als sehr gut geeignet. Auch für neuere Datenbankanwendungen wie etwa im Bereich des Computer-Aided-Designs (CAD) oder der Entscheidungsunterstützung (z.B. Diagnosesysteme und Expertensysteme) sind deduktive Datenbanksysteme besonders geeignet. Darüber hinaus sind wegen ihrer Behandlung von uneingeschränkten Integritätsbedingungen deduktive Datenbanksysteme im traditionellen Bereich der Verwaltungsdatenbanken auch sehr nützlich. Regeln erleichtern z.B. die Spezifikation der Aufnahme in Sperrlisten bei Kreditkartenunternehmen.

Neuere Anwendungen für deduktive Datenbanken erfordern erweiterte Möglichkeiten zur Repräsentation von Wissen. Zur Zeit wird deshalb intensiv an der Erweiterung deduktiver Datenbanken um eine uneingeschränkte Negation als Scheitern und um verschiedenen Formen von unsicherem Wissen, wie etwa in disjunktiven Datenbanken, gearbeitet. Für viele Anwendungen ist die deklarative Spezifikation von Datenbankänderungen sehr wichtig. Dies hat zu Forschungsaktivitäten im Bereich der aktiven Datenbanken geführt, in denen Regelformalismen zur Definition von Änderungen verwendet werden. Auch neueste Datenbankthemen, wie z.B. Knowledge Discovery (auch Data Mining genannt) und Constraint-Datenbanken, bei denen spezielle Theorien zur Spezifikation von besonderen Daten wie etwa Intervallen oder numerischen Werten eingesetzt werden, nutzen oder erweitern Methoden der deduktiven Datenbanken.

Die in deduktiven Datenbanken eingeführten Erweiterungen haben für die Datenbankforschung einen Sprung ins Unbekannte dargestellt. Zum ersten Mal wurde ein Datenbankkonzept vorgeschlagen, das genauso wie eine Programmiersprache uneingeschränkte Berechnungen ermöglicht, weil die aus Fakten und Ableitungsregeln bestehenden Sprachen Turingvollständig sind. Daran mag es liegen, daß die neue, zukunftsweisende Technologie der deduktiven Datenbanken sich nur langsam außerhalb der Forschungskreise etabliert. Die kürzliche Aufnahme von rekursiven Sichten im neuen Standard SQL3 wird in Fachkreisen als eine wichtige Erweiterung von traditionellen Datenbanksystemen um Konzepte deduktiver Datenbanksysteme angesehen.