Der CHASE ist ein grundlegender Algorithmus der Datenbanktheorie, der uber noch ungenutztes Potential hinsichtlich seiner praktischen Umsetzung in Systemen verfugt. In den von uns untersuchten Anwendungsbereichen wurden eine Reihe von Problemfallen identi ziert, fur die der CHASE interessant sein konnte. Allerdings sind diese Anwendungsbereiche mit zahlreichen Datenbankkonzepten wie komplexeren Anfrageoperationen verbunden, die bisher nicht (gemeinsam) in den CHASE integriert wurden. Die Erweiterung des CHASE um diese Anfrageoperationen, wie Negation, allgemeine Vergleiche oder Aggregatfunktionen, muss jedoch kontrolliert erfolgen, um E ektivitat, Kon uenz und Terminierung des CHASE nicht zu gefahrden und so eine e ektive Anwendung des Algorithmus auf praktisch relevante Problemfalle zu ermoglichen. Um Auswirkungen von CHASE-Erweiterungen einschatzen zu konnen, mussen zunachst E zienz, Kon uenz, Terminierung und E ektivitat des bisher etablierten CHASE verstanden und gegebenenfalls naher untersucht werden. In dieser Arbeit stellen wir erste Erkenntnisse hinsichtlich Terminierung und Kon uenz des Standard-CHASE zusammen.
Der CHASE integriert CHASE-Parameter, dargestellt als spezielle pradikatenlogische Formeln, in CHASE-Objekte, diese auch dargestellt als spezielle, aber andersartige, pradikatenlogische Formeln. So kann man Integritatsbedingungen als CHASE-Parameter in Anfragen integrieren, um die Anfragen semantisch (unter Berucksichtigung der Integritatsbedingungen) optimieren zu konnen. Auf diese Weise kann beispielsweise die Anzahl der Verbundoperationen reduziert werden, was die E zienz der Anfrage steigert. Man kann als CHASE-Parameter aber auch Sichtde nitionen verwenden, um diese in Anfragen integrieren zu konnen, um die Anfragen statt uber den Relationen der Datenbank nur noch uber den Sichten auszufuhren. Auf diese Weise kann beispielsweise Privacy garantiert werden, wenn der direkte Zugri auf die Basisrelationen der Datenbank aus Datenschutzgrunden nicht erlaubt ist. Statt Anfragen als CHASE-Objekte zu verwenden, kann man aber auch eine Datenbank als CHASEObjekt verstehen. Die CHASE-Parameter sind dann Transformationen der Datenbank, etwa auch Datenanalysen oder klassische Anfragen. Der CHASE kann dann als Anfragemechanismus verstanden werden. Anwendungsfalle fur den CHASE auf Datenbanken ist etwa die Integration mehrerer lokalen Datenbanken zu einer zentralen Datenbank oder die gemeinsame Evolution eines Datenbankschemas und den jeweiligen Datenbankanfragen unter Berucksichtigung der Provenance. In Unterabschnitt 3.1 werden wir, nach Besprechung der theoretische Grundlagen des CHASE und ihrer Demonstration anhand eines praktischen Beispiels, auf die unterschiedlichen Anwendungszwecke des CHASE zuruckkommen.
Um die oben genannten Teilprobleme der Privacy, Provenance und Anfrageoptimierung gemeinsam losen zu konnen, mussen die bisher getrennten Anwendungen des CHASE auf verschiedene CHASE-Objekte und mit verschiedenen CHASE-Parametern in eine gemeinsame Technik integriert werden. 2.
Die Rahmenbedingungen Privacy, Provenance und E zenzoptimierung sollen in Datenauswertungsverfahren integriert werden, indem uber die einheitliche Grundtechnik des CHASE ursprunglich getrennte Problemlosungen zu einer Gesamtlosung kombiniert werden.
Hieraus leiten sich folgende zwei Herausforderungen ab:
Vereinheitlichung der CHASE-Techniken: Obwohl
der CHASE { von einem abstrakten Gesichtspunkt
betrachtet { ein universeller Algorithmus ist, der unterschiedliche
Arten von Parametern verarbeiten und so in einer Vielzahl
von Aufgabengebieten Verwendung nden konnte [
Erweiterung des CHASE: Obwohl der CHASE in der Datenbanktheorie ein ungeheuer machtiges Werkzeug darstellt, ist er bisher fur praktische Erfordernisse von Datenbankanwendungen inadaquat. Tatsachlich beschrankt sich der klassische Standard-CHASE auf die Abbildung von Konjunktionen positiver Selektions-Projektions-Verbund-Anfragen, wobei die Selektion lediglich auf dem Testen von Gleichheit beruht. Um E ektivitat in den zuvor genannten Anwendungsgebieten zu erreichen, wird eine Erweiterung um weitere Vergleichsoperatoren, Negation und Funktionen benotigt. Diese Erweiterung sollte jedoch kontrolliert erfolgen, um Terminierung, Kon uenz und E zienz des Verfahrens nicht zu gefahrden. Tatsachlich handelt es sich beim in dieser Arbeit betrachteten CHASE-Algorithmus bereits um eine Erweiterung des ursprunglichen Tableau-Verfahrens { auch diese Erweiterungen gingen mit Einschrankungen der ursprunglich garantierten Terminierung und Kon uenz einher.
Zahlreiche grundlegende Anwendungsfalle der
Datenbankforschung haben gemeinsam, dass sie mit Hilfe eines
Universalmodells gelost werden konnen [
Im Folgenden soll der grundlegende Ablauf eines CHASESchrittes betrachtet werden. Der grundlegende Ablauf ist in Algorithmus 1 (mit CHASE-Parametern , CHASE-Objekt I und neu erzeugten Nullwerten bzw. existenzquanti zierten Variablen FRESH) gegeben. Zunachst mussen wir einige Begri ichkeiten klaren. Der CHASE arbeitet, allgemein gesehen, Parameter in Objekte ein. Sowohl Parameter als auch Objekte sollten als pradikatenlogische Formeln erster Ordnung (ohne Funktionssymbole oder Negationen) darstellbar sein. Ohne Verlust der Allgemeinheit werden wir die Parameter als Integritatsbedingungen und das Objekt als Datenbankinstanz bezeichnen { tatsachlich konnte die Instanz jedoch z.B. auch den Korper einer Datenbankanfrage darstellen (die sogenannte kanonische\ Instanz der Anfrage).
" Integritatsbedingungen lassen sich in tupelerzeugende Abhangigkeiten (TGDs) und gleichheiterzeugende Abhangigkeiten (EGDs) unterteilen:
T GD : 8X; Y : (X; Y ) ! 9Z : (X; Z)
EGD : 8X : (X) ! x1 = x2: und sind hierbei Mengen relationaler Atome, X; Y und Z sind jeweils Mengen allquanti zierter Variablen und Konstanten, Z ist eine Menge existenzquanti zierter Variablen, und x1 sowie x2 sind Variablen oder Konstanten aus X. Kommen keine existenzquanti zierten Variablen im Kopf der TGD vor, so sprechen wir von einer vollen Abhangigkeit, ansonsten von einer eingebetteten Abhangigkeit.
Durch den Rumpf der Integritatsbedingung wird ein Muster de niert. Erfullt ein Tupel der Instanz (oder ein Atom eines Anfragerumpfes) das Muster, lasst sich ein Homomorphismus von den Variablen der Bedingung zu den KonstanAlgorithmus 1 STANDARD-CHASE( , I) 1: while xpoint not reached do 2: choose nondeterministically 2 3: for each active trigger h for in I do 4: if is a TGD with head 9Z : (X; Z) then 5: h := h [ fZ 7! N g where N FRESH 6: I := I [ h( (X; Z)) 7: else if is an EGD with head xi = xj then 8: if fh(xi) 6= h(xj)g CONSTANT then 9: fail 10: ! := fh(xi) ! h(xj)g (h(xj) > h(xi)) 11: I := !(I) ten und Nullwerten der Instanz (bzw. zu den all- und existenzquanti zierten Variablen des Anfragerumpfes) nden. In diesem Fall sprechen wir auch vom Vorliegen eines Triggers. Der Trigger ist aktiv (Zeile 3), wenn die Bedingung noch nicht erfullt ist. Fur TGDs testen wir hierfur, ob der Homomorphismus so fur die existenzquanti zierten Variablen des TGD-Kopfes erweitert werden kann, dass das Bild des TGDKopfes unter dem erweiterten Homomorphismus bereits in der Datenbank existiert. Ist dies nicht der Fall, wird der Homomorphismus stattdessen so erweitert, dass die existenzquanti zierten Variablen auf neu erzeugte markierte Nullwerte abgebildet sind (Zeile 5). Die so de nierten neuen Tupel werden in der Datenbankinstanz materialisiert (Zeile 6). Fur EGDs wird uberpruft, ob das Gleichheitsatom x1 = x2 bereits erfullt ist, also ob das Bild beider Terme unter dem Homomorphismus identisch ist. Ist dem nicht der Fall, unterscheiden wir die folgenden drei Falle:
Das Bild beider Terme sind unterschiedliche Konstanten (wobei das Bild einer Konstanten die Konstante selbst ist). Ist dies der Fall, scheitert der CHASE (Zeile 9).
Das Bild beider Terme sind unterschiedliche Nullwerte. In der gesamten (Ziel-) Datenbankinstanz wird einer der Nullwerte (gewohnlich der mit hoherem Index) durch den anderen ersetzt.
Das Bild des einen Terms ist eine Konstante, wahrend das Bild des anderen Terms ein Nullwert ist. In der gesamten (Ziel-) Datenbankinstanz wird der Nullwert durch die Konstante ersetzt.
Fur Instanzen lasst sich also eine Hierarchie zwischen Konstanten und Nullwerten de nieren (siehe Gro envergleich in Zeile 10 des Algorithmus). Handelt es sich beim CHASEObjekt um eine Datenbankanfrage, besteht diese Hierarchie zwischen Konstanten, allquanti zierten und existenzquantizierten Variablen.
In der Langversion dieser Arbeit [
Der CHASE-Algorithmus ist uber vierzig Jahre alt [
Weitere Anwendungsgebiete, wie etwa die Invertierung von
Datenbanktransformationen und Provenance-Management,
sind gegenwartiger Stand der Forschung am Lehrstuhl fur
Datenbank- und Informationssysteme [
Aus den oben genannten Anwendungsgebieten ergibt sich bereits eine deutliche Variabilitat der moglichen CHASEParameter und -Objekte. Fur Datenbankintegration und Datenbanktransformation werden Transformationsregeln (source-to-target TGDs) verwendet, fur AQuV kommen Sichtdenitionen (TGDs) zum Einsatz, und Data Cleaning sowie Anfrageoptimierung erfolgt unter Verwendung allgemeiner Integritatsbedingungen (EGDs und TGDs). Wie bereits zuvor erwahnt, handelt es sich beim Objekt des CHASE entweder um eine Datenbankanfrage (Anfrageoptimierung und AQuV) oder um eine Datenbankinstanz (alle anderen Anwendungsfalle).
Wahrend die meisten der oben genannten Probleme bei Wahl geeigneter CHASE-Parameter und -Objekte durch den Standard-CHASE direkt gelost werden konnen, setzt die Anfrageoptimierung und -transformation unter Integritatsbedingungen durch den CHASE mehrere Hilfsalgorithmen voraus. Im Wesentlichen handelt es sich hierbei um das unter dem Namen Backchase bekannte Verfahren, der das Ergebnis des vorherigen CHASE als Ausgangspunkt eines erneuten CHASE in umgekehrter Richtung verwendet und anschlie end durch Finden eines homomorphen Kerns Redundanzen aus dem Ergebnis entfernt. 3.2
Bisher wird der CHASE-Algorithmus zwar noch nicht in
kommerziellen Losungen verwendet (Ausnahme: aus dem
Forschungsprototyp Clio entwickelte Teile des IBM
Information Servers), es gibt jedoch eine Reihe prototypischer
Implementierungen, mit denen einige Anwendungsfalle des
CHASE naher untersucht werden konnen. Allerdings kann bisher
keiner dieser Prototypen alle in Unterabschnitt 3.1
genannten Anwendungsbereiche bearbeiten. So sind in der
CHASESoftware Llunatic [
Die Verarbeitung der unterschiedlichen
CHASE-Parameter und -Objekte ist tatsachlich in keinem uns bekannten
Werkzeug vereinheitlicht, stattdessen kommen immer
getrennte Techniken zum Einsatz. Die CHASE-Software Graal
[
An dieser Stelle sei erwahnt, dass einige
CHASE-Prototypen bereits jetzt uber Erweiterungen des zuvor
beschriebenen Standard-CHASE verfugen. VLog integriert
beispielsweise Negationen in den CHASE [
Die ursprungliche Variante des CHASE { d.h. die Berucksichtigung von Verbund-Abhangigkeiten (JDs) und Funktionalen Abhangigkeiten (FDs) beim Datenbankentwurf { ist sowohl terminierend, als auch kon uent. Der CHASE erzeugt in diesem Fall also unabhangig von der Reihenfolge der Regelanwendungen stets das gleiche (oder zumindest ein isomorphes) Ergebnis. Die Erweiterung des CHASE um existenzquanti zierte Variablen erlaubt es zwar, z.B. Inklusionsabhangigkeiten und damit auch Fremdschlusselbeziehungen zu berucksichtigen, jedoch unter Verlust der sicheren Terminierung des Algorithmus. Tatsachlich kann diese Terminierung des CHASE sogar abhangig von der Reihenfolge der Regelanwendungen sein. Obwohl das allgemeine Problem der CHASE-Terminierung unentscheidbar ist, wurden inzwischen eine ganze Reihen von Testverfahren entwickelt, welche eine sichere Terminierung des CHASE allein auf Basis der Integritatsbedingungen zusichern konnen. Einige dieser Kriterien werden in Abschnitt 4 vorgestellt.
Wahrend die Terminierung des CHASE also recht gut
verstanden ist, wurde die erwahnte Reihenfolgeabhangigkeit,
also die Kon uenz des CHASE, bisher kaum untersucht.
Wie zuvor erwahnt ist der CHASE auf Funktionalen
Abhangigkeiten kon uent. Fur Erweiterungen der Funktionalen
Abhangigkeit ist der CHASE entweder kon uent
(GraphCHASE in [
Obwohl zum CHASE bereits zahlreiche Komplexitatsuntersuchungen existieren, beziehen sich diese bisher meist auf Worst-Case-Abschatzungen. In dieser Arbeit soll dies durch neuere Techniken erweitert werden. So erlaubt die Untersuchung der parametrischen Komplexitat, relativ konstant bleibende Parameter (z.B. die Anzahl der Attribute) zu isolieren. Durch die kostenbasierte Laufzeitabschatzung werden prazisere Aussagen zur E zienz des CHASE moglich, die uber ein Worst-Case Szenario hinaus gehen.
Die Thematik der CHASE-Terminierung wurde von uns
bereits in vorbereitenden Arbeiten untersucht [
Indem wir vor Durchfuhrung des eigentlichen CHASE den verwendeten CHASE-Parameter auf seine Zugehorigkeit zu einer dieser Klassen uberprufen, konnen wir die Terminierung des CHASE unabhangig vom verwendeten CHASEObjekt garantieren. Allerdings berucksichtigen die meisten Terminierungstests nur eine Form von CHASE-Parameter, und zwar TGDs, wahrend EGDs entweder ignoriert werden konnen (z.B. im Fall der Schwachen Azyklizitat) oder sogar zu fehlerhaften Testergebnissen fuhren konnen (z.B. im Fall der Azyklizitat). Aus den verglichenen Terminierungskriterien wurden die Kriterien Schwache Azyklizitat, Reiche Azyklizitat, Safety und Azyklizitat ausgewahlt und in Form eines Terminierungstesters des CHASE-Werkzeugs ChaTEAU umgesetzt. Wahrend einige Terminierungskriterien nicht vergleichbar miteinander sind, bilden Reiche Azyklizitat, Schwache Azyklizitat, Safety und Azyklizitat (in dieser Reihenfolge) eine Hierarchie hinsichtlich ihrer Machtigkeit, wobei Azyklizitat das machtigste der untersuchten Kriterien darstellt.
Schwache Azyklizitat. Wenn eine TGD zu einer Endlosschleife des Standard-CHASE beitragt, muss sie dazu in der Lage sein, beliebig oft neue Tupel zu generieren. Da die ursprungliche Datenbankinstanz als endlich angenommen wird, enthalten diese Tupel notwendigerweise Werte, die zuvor noch nicht in der Datenbankinstanz vorkamen { durch den CHASE zuvor erzeugte markierte Nullwerte. Diese Erkenntnis gilt ebenfalls fur die eingebetteten TGDs, welche diese Nullwerte zuvor generiert hatten. Das Kriterium der Schwachen Azyklizitat verfolgt die Weitergabe dieser Nullwerte anhand eines Graphen mit besonderen (Beitrag zur Erzeugung eines neuen Nullwertes) und gewohnlichen Kanten (Weitergabe eines Wertes). Existiert in diesem Graphen ein Zyklus, der durch eine besondere Kante geht, ist die Terminierung des CHASE nicht garantiert.
Reiche Azyklizitat. Im Gegensatz zum Standard-Chase uberpruft der naive Oblivious-Chase die Aktivitat des Triggers nicht. Gerat diese CHASE-Variante in eine Endlosschleife, so enthalten wenigstens die Trigger der beteiligten TGDs Werte, die zuvor nicht in der Datenbankinstanz vorkamen. Wir fordern also nicht, dass diese Nullwerte des Triggers in die neu erzeugten Tupel gelangen. Es werden folglich in zusatzlichen Fallen neue Nullwerte erzeugt. Wir erganzen den Graphen der Schwachen Azyklizitat daher um weitere spezielle Kanten. Die Terminierung des naiven Oblivious-CHASE kann nur dann garantiert werden, wenn der Graph keine Zyklen durch besondere oder spezielle Kanten enthalt. In diesem Fall wurde auch der Standard-CHASE terminieren, da die Terminierung des naiven Oblivious-CHASE hinreichendes Kriterium fur die Terminierung des Standard-CHASE ist.
Safety. Fur die Kriterien der Schwachen und Reichen Azyklizitat wird zwischen der Erzeugung von Nullwerten und der Weitergabe von Werten unterschieden. Unter Umstanden konnen wir allerdings ausschlie en, dass bestimmte Variablen einer TGD mit einem Nullwert der Instanz belegt sind (indem wir Gleichheit mit einem Attribut fordern, welches keinen Nullwert enthalten kann). Fur das Safety-Kriterium schranken wir die Weitergabe allgemeiner Werte auf die Weitergabe potentieller Nullwerte ein, wodurch wir die Machtigkeit des Testkriteriums der Schwachen Azyklizitat erhohen.
Azyklizitat. Bei diesem Terminierungskriterium wird die Azyklizitat der gegenseitigen TGD-Aufrufung nicht untersucht (was einem wesentlich einfacheren Terminierungskriterium entsprache). Stattdessen werden die relationalen Atome der einzelnen TGDs um einen String sogenannter "Adornments\ erganzt. Die Adornments werden auf eine Weise zwischen Atomen des TGD-Rumpfes und TGD-Kopfes einer TGD bzw. zwischen TGD-Kopf und TGD-Rumpf verschiedener TGDs weitergegeben, die dem CHASE-Algorithmus ahnelt. Diese U bertragung und Neuentstehung von adornten Atomen wird durch einen Graphen modelliert, dessen Zyklenfreiheit die Terminierung des CHASE garantiert. Durch Nutzung des ebenfalls implementierten Constraint-RewritingAlgorithmus der Substitutionslosen Simulation verarbeitet der Terminierungstester neben TGDs auch EGDs.
Diese Vorarbeiten hinsichtlich der CHASE-Terminierung sollen in Folgearbeiten aktualisiert und durch vergleichbare Untersuchungen zur Kon uenz erganzt werden.
Um die Inkon uenz des CHASE anschaulicher diskutieren zu konnen, de nieren wir zunachst eine Beispieldatenbank, welche aus einer Tabelle fur Noten des Studiengangs Informatik und einer Tabelle fur alle eingeschriebenen Studierenden besteht. Wir nehmen an, dass die Tabelle der Noten aller Studierenden aus E zienzgrunden horizontal fragmentiert wurde, sodass jeder Studiengang uber eine separate Notentabelle verfugt. Die Relation Noten Informatik besteht aus den Attributen Matrikelnummer (Ma), Modulnummer (Mo) und Note (No), wahrend die Attribute der StudierendenRelation Matrikelnummer (Ma), Name (Na) und Studiengang (St) sind.
Im Folgenden orientieren sich die Namen der Variablen an den Abkurzungen der Attribute, in denen sie stehen, wobei existenzquanti zierte Variablen durch zwei Gro buchstaben, allquanti zierte Variablen hingegen durch zwei Kleinbuchstaben gekennzeichnet sind. Aufgrund dieser Konvention konnte auf Quantoren verzichtet werden.
U ber die Matrikelnummer der Studierenden sei eine Fremdschlusselbeziehung zwischen beiden Relationen de niert. Die folgende TGD r1 beschreibt die hiermit verbundene Inklusionsabhangigkeit: r1 :Noten Informatik(ma; mo; no)
! Studierende(ma; NA; ST ): Wie in Unterabschnitt 3.2 erwahnt, kann der Test der Triggeraktivitat als Negation verstanden werden: r10 :Noten Informatik(ma; mo; no);
:Studierende(ma; NA2; ST2) ! Studierende(ma; NA; ST ): Wird der CHASE ausschlie lich auf volle TGDs angewandt, ist er monoton, womit sich seine Kon uenz begrunden lasst. Wenn der CHASE durch Erweiterungen ein nicht-monotones Verhalten zeigt, fuhrt dies also unter Umstanden zur Inkonuenz des CHASE. Beispiele fur derartige nicht-monotonen Erweiterungen sind Negation (einschlie lich des Tests der Triggeraktiviertheit) und Deletion. Letzteres bezieht sich etwa auf das Verschmelzen zweier Tupel nach Anwendung einer EGD. Allerdings fuhren EGDs unter Umstanden divergente Datenbankzustande zusammen und etablieren so Konuenz.
Betrachten wir zunachst einen einfachen Fall von Inkonuenz auf Grundlage der zuvor de nierten Inklusionsabhangigkeit r1. Wir erganzen eine weitere Inklusionsabhangigkeit fur die Noten-Tabelle der Mathematikstudenten. Hier wollen wir jedoch zusatzlich festlegen, dass Studierende, welche Noten in Mathematik-Modulen erhalten, auch im Studiengang Mathematik eingeschrieben sind: r2 :Noten Mathematik(ma; mo; no)
! Studierende(ma; NA; "Mathematik\): Objekt des CHASE sei folgende Datenbankinstanz I: I = fNoten Informatik(2; "Datenbanken III\; 4:0); Noten Mathematik(2; "Stochastik I\; 1:0);
Studierende(1; "Mustermann\; "Informatik\)g: Wenden wir zuerst r1, und dann r2 an, werden zwei neue Tupel erzeugt. Das gleiche Ergebnis erhalten wir, wenn die Aktivitat des Triggers nicht getestet wird oder beide Regeln parallel ausgewertet werden:
I0 = I [ fStudierende(2; 1; 2);
Wenden wir r2 zuerst an, wird der Trigger von r1 deaktiviert, und kein zusatzliches Tupel kann erzeugt werden:
I00 = I [ fStudierende(2; 1; "Mathematik\)g:
Das Ergebnis der Regelanwendung ist hier abhangig von ihrer Reihenfolge. Beide Ergebnisse erfullen alle gegebenen Abhangigkeiten und sind universelle Losungen. Sind wir nur an der Existenz eines bestimmten Eintrags interessiert, liefen beide Reihenfolgen dasselbe Ergebnis. Wollen wir hingegen die Anzahl vorhandener Tupel bestimmen { z.B. durch Verwendung der Aggregatfunktion COUNT() in der Datenbankanfrage { lasst sich eine sichere Antwort lediglich in Form eines Intervalles ermitteln.
Nehmen wir an, dass nicht alle Studierenden, die Noten im Studiengang Informatik erworben haben, auch Informatik studieren, sondern Informatikmodule etwa nur als Nebenfach besuchen. Mathematik-Studierende, die Informatik als Nebenfach belegen, haben durch ihre Hauptfach bereits einen Eintrag in der Relation Studierende, sollten dort aber zusatzlich als Informatikstudenten gefuhrt werden, wenn sie entsprechende Module absolviert haben: r20 :Noten Informatik(ma; mo; no);
! Studierende(ma; NA2; "Informatik (Nebenfach)\): Erweitern wir die zuvor verwendete Instanz um eine Mathematikstudentin:
I2 = fNoten Informatik(2; "Datenbanken III\; 4:0); Noten Mathematik(2; "Stochastik I\; 1:0); Studierende(1; "Mustermann\; "Informatik\) Studierende(2; "Musterfrau\; "Mathematik\)g:
Obwohl r2 und r20 nahezu identische Kopfe aufweisen, liegt keine Inkon uenz zwischen r1 und r20 vor. Bei der Untersuchung von Inkon uenz nehmen wir an, dass mehrere Regeln gleichzeitig angewandt werden konnten. Wir setzen fur r20 jedoch voraus, dass Mathematik-Studierende bereits einen Eintrag in der Relation Studierende besitzen. Unter dieser Annahme (die in I2 zutri t) kann r1 aber nicht angewandt werden:
I3 = I2 [ fStudierende(2; 1; "Informatik (Nebenfach)\)g: Varianten dieser U berlegung konnen genutzt werden, um zyklische Beziehungen zu untersuchen. Wir de nieren hierfur, dass Studierende, die Mathematik studieren, auch mindestens einen Eintrag in der Relation Noten Mathematik besitzen (vor Absolvieren ihres ersten Moduls erhalten Studierende etwa einen Platzhalter-Eintrag in dieser Tabelle): O ensichtlich sind r2 und r3 zyklisch. Tupel, die von der einen TGD erzeugt werden, konnen von der jeweils anderen Regel als Trigger verwendet werden. Dennoch besteht (bei Verwendung des Standard-CHASE) keine Gefahr, in einer Endlosschleife unendlich viele Tupel zu generieren. Wenn wir r2 anwenden, erzeugen wir fur einen Studierenden der Relation Noten Mathematik, dessen Matrikelnummer bekannt ist, einen Eintrag in der Relation Studierende. Es existieren nun also Eintrage fur den Studierenden mit besagter Matrikelnummer in beiden Tabellen. Wenn wir fur diesen Studierenden r3 anwenden wollen, darf in der Noten MathematikTabelle noch kein Eintrag mit dieser Matrikelnummer existieren (alle anderen Attribute sind nicht festgelegt), was fur diesen Studierenden aber nicht zutri t. Tatsachlich ist dieser Gedankengang Grundlage eines einfachen Terminierungskriteriums des CHASE, der Schwachen Azyklizitat. 6.
Der CHASE-Algorithmus ist ein universeller Algorithmus der Datenbanktheorie. Um ihn tatsachlich universell in praktischen Anwendungsszenarien einsetzen zu konnen, werden Erweiterungen { wie Negation oder Funktionssymbole { benotigt.
Es ist bereits abzusehen, dass diese Erweiterungen Kon uenz und Terminierung beein ussen. In der vorliegenden Arbeit wurde dargelegt, dass bereits der etablierte CHASE eine Form von Negation implementiert und daher inkon uent ist. Da die Nicht-Terminierung des CHASE auf der Generierung neuer Werte beruht, ist o ensichtlich, dass skalare Funktionsterme eine ahnlichen Auswirkung wie existenzquanti zierte Variablen auf die CHASE-Terminierung haben. Da Kon uenz, Terminierung und E zienz also wohl nicht im Allgemeinen fur den erweiterten CHASE garantiert werden konnen, mussen Spezialfalle identi ziert werden, in denen der CHASE e ektiv auf die untersuchten Anwendungsfalle anwendbar ist.