Ereignismuster für die Verwaltung von komplexen Tupelereignissen in Probabilistischen Datenbanken Sebastian Lehrack Brandenburgische Technische Universität Cottbus Institut für Informatik, Postfach 10 13 44 D-03013 Cottbus, Deutschland slehrack@informatik.tu-cottbus.de ABSTRACT Arte tid aid type sond age ETArte Probabilistische Datenbanken haben sich als adäquate Tech- t1 art1 vase fragment 3 300 (X1 = t1 ) nik zur Verwaltung und Verarbeitung von umfangreichen t2 art2 spear head 10 500 (X2 = t2 ) unsicheren Datenmengen etabliert. Eine der größten Her- t3 art3 vase fragment 4 300 (X3 = t3 ) ausforderungen für probabilistische Datenbanken ist eine ef- fiziente Anfrageverarbeitung. Eine zentrale Rolle spielen da- ArteExp bei Ableitungsformeln, welche komplexe Tupelereignisse in tid expert aid culture conf ETArteExp Form von aussagenlogischen Formeln verkörpern. Eine di- t4 Peter art1 roman 0.3 (X4 = t4 ) rekte Abspeicherung und Verarbeitung von komplexen lo- t5 Peter art1 greek 0.4 (X4 = t5 ) gischen Formeln wird von relationalen Datenbanksystemen t6 Kathleen art1 roman 0.4 (X5 = t6 ) jedoch nicht unterstützt. Diese Arbeit stellt Ereignismuster t7 John art2 egyptian 0.6 (X6 = t7 ) als geeignetes Mittel vor, um Ableitungsformeln mittels ei- ArteMat nes RBDMS verwalten zu können. tid method aid culture conf ETArteM at t8 XRF art1 roman 0.3 (X7 = t8 ) t9 XRF art1 greek 0.3 (X7 = t9 ) t10 ICS-MS art2 punic 0.8 (X8 = t10 ) 1. MOTIVATION t11 XRF art2 egyptian 0.5 (X9 = t11 ) Probabilistische Datenbanken standen in den letzten Jah- ren im Mittelpunkt intensiver Untersuchungen (für einen Figure 1: Datentabellen Arte, ArteExp und ArteMat Überblick verweisen wir auf [18]). In einer solchen Daten- des fortlaufenden Beispielszenarios (die unterstri- bank gehört ein Tupel lediglich mit einer gewissen Wahr- chenen Attribute kennzeichnen den jeweiligen Er- scheinlichkeit zu einer Datentabelle oder zu einem Anfrage- eignisschlüssel (siehe Kap. (2))) ergebnis. Die Wahrscheinlichkeit drückt dabei entweder eine Unsicherheit über die Datengrundlage oder die Anfrageant- wort aus. durch die Neuentwicklung des CISAR-Projektes1 [5], wel- Eine der größten Herausforderungen für probabilistische ches als internet-basiertes Geo-Informationssystem für Ar- Datenbanken ist eine effiziente Anfrageverarbeitung. Ein zen- chäologie und Gebäudegeschichte entwickelt worden ist. Die trales Konzept sind dabei Ableitungsformeln, welche kom- hier vorgestellten Techniken werden umfassend in dem Nach- plexe Tupelereignisse in Form von aussagenlogischen For- folgesystem OpenInfRA eingesetzt [17]. meln darstellen [4]. Eine direkte Abspeicherung und Verar- In dem stark vereinfachten Beispielszenario werden die de- beitung von komplexen logischen Formeln wird von relatio- terministische Tabelle Artefakte (Arte) und die zwei pro- nalen Datenbanksystemen jedoch nicht unterstützt. Diese babilistischen Tabellen Artefakte klassifiziert bei Experten 2 Arbeit stellt Ereignismuster als geeignetes Mittel vor, um (ArteExp) und Artefakte klassifiziert bei Material (ArteMat) Ableitungsformeln in einer strukturierten Form mittels ei- verwendet, siehe Abb. (1). In der Datentabelle Arte werden nes RBDMS verwalten zu können. Informationen über mehrere Artefakten gespeichert, welche Fortlaufendes Beispiel: Die grundlegenden Ideen wer- während einer archäologischen Ausgrabung gefunden wor- den in den nächsten Kapiteln anhand eines fortlaufenden den sind. Dabei wird mittels der Sondage-Nummer (Attri- Beispielszenarios aufgezeigt. Dieses Szenario ist motiviert but sond ) die geographische Fundstelle eines Artefaktes be- schrieben. Zusätzlich geben mehrere Spezialisten verschiedene Ex- pertisen über die Ursprungskultur eines Artefakts (Attribut culture) ab, siehe Tabelle ArteExp. Diese Einschätzungen werden mit einem Konfidenzwert annotiert (Attribut conf ), 1 http://www.dainst.org/en/project/cisar/ 2 Die Spalten tid, conf und ET (...) gehören nicht zu den ei- 24th GI-Workshop on Foundations of Databases (Grundlagen von Daten- gentlichen Datentabellen. Mittels der Spalte tid werden Tu- banken), 29.05.2012 - 01.06.2012, Lübbenau, Germany. pel adressiert. Die Bedeutung von conf und ET(...) wird in Copyright is held by the author/owner(s). den nächsten Abschnitten erläutert.   select aid, type, culture πaid,type,culture from ( select aid, culture from ArteExp union ./ select aid, culture from ArteMat ) origin ∪ Arte inner join ( select * from Arte πaid,culture πaid,culture ) prop on ( origin.aid = prop.aid ) ArteExp ArteM at   Figure 2: Beispielanfrage Qe als QSQL2-Anfrage und als abstrahierte Algebraanfrage welche die Wahrscheinlichkeit ausdrückt, dass das entspre- der block-independent-disjoint Datenbanken (BID) [2] be- chende Artefakt zu der bestimmten Kultur gehört. Neben nutzt, da Tupel- und Attributunsicherheit untersützt wer- den subjektiven Expertenmeinungen werden auch objekti- den soll. Eine BID ist eine probabilistische Datenbank in ve Methoden einbezogen. Diese archäometrischen Methoden der die gegebenen Tupel in Blöcke unterteilt werden. Da- (z.B. XRF und ICS-MS3 ) basieren auf einer Materialanaly- bei kann ein Block sich nicht über mehrere Relationen er- se. In Kombinationen mit den Fundstellen und dem Artefak- strecken. Es wird vereinbart, dass alle Tupel innerhalb ei- talter kann die Materialzusammensetzung wichtige Hinweise nes Blockes mit disjunkten Tupelereignissen verbunden sind. auf die Ursprungskultur geben, welche dann ebenfalls mit- Ein Tupelereignis beschreibt das Vorhandensein oder das tels Konfidenzwerten quantifiziert werden. Nicht-Vorhandensein eines Tupel in einer beliebigen Welt. Basierend auf den eingeführten Datentabellen soll exem- Wegen der Disjunktheit der Tupelereignisse kann maximal plarisch die folgende Anfrage Qe bearbeitet werden: Bestim- ein Tupel eines Blockes in einer bestimmten Welt vorhanden me alle Artefakte mit ihren jeweiligen Typ und ihren mögli- sein. Dagegen sind Tupel von verschiedenen Blöcken mit ge- chen Ursprungskulturen. Um diese Anfrage zu beantworten genseitig unabhängigen Tupelereignissen assoziiert. wird sie zunächst in der Anfragesprache QSQL2 [8] formu- Für die Definition von Blöcken werden Ereignisschlüssel in liert, siehe Abb. (2). Anschließend wird von dem eigentlichen Form von Attributmengen angewendet4 . So wird ein Block SQL-Syntax abstrahiert, indem sie in Form einer Algebraan- wird von Tupeln gebildet, welche die gleichen Werte für die frage in den nächsten Kapiteln weiter verarbeitet wird. Attribute des Schlüssel haben. Anschließend wird für jeden Die Arbeit ist wie folgt gegliedert. In Kap. (2) werden zu- Block eine unabhängige Zufallsvariable Xk eingeführt. Das nächst die Grundlagen für die weiteren Betrachtungen ge- konkrete Eintreten einer Zufallsvariable (Xk = tid ) reprä- legt. Danach steht der wesentliche Beitrag dieser Arbeit in sentiert ein Tupelereignis und wird quantifiziert mit dem Form der Ereignismuster in Kap. (3) im Mittelpunkt. In Konfidenzwert des Tupels tid , siehe die Spalten conf und den Kap. (4) und (5) wird die Arbeit mit einer Diskussion ET (...) in der Abb. (1)5 . Die kombinierte Wahrscheinlich- über verwandte Arbeiten und einer Zusammenfassung ab- keitsverteilung aller Blockvariablen bilden schließlich P. Um geschlossen. Der Beweis des Satzes (1) wird im Anhang (A) eine Algebraanfrage auf einer probabilistischen Datenbank geführt. auszuführen, wird folgende Anfragesemantik verwendet [18]. 2. GRUNDLAGEN Definition 2. Sei Q eine Algebraanfrage und D = (W, P) In einer probabilistischen Datenbanken werden mehrere eine probabilistische Datenbank. Die Menge aller möglichen möglichen Datenbankinstanzen, welche auch Welten genannt Antworttupel einer Anfrage Q ist definiert als Qposs(W) = werden, gleichzeitig verwaltet und abgefragt. Dabei wird die {t | ∃W ∈ W : t ∈ Q(W )}. Zusätzlich werden die Eintritts- reale Welt“ als unbekannt angenommen. Um diese Unsi- wahrscheinlichkeiten aller möglichen AntwortenP in der Funk- ” cherheit abzubilden wird ein Wahrscheinlichkeitsmaß über tion PrQ : Qposs(W) → (0, 1] als PrQ (t) := P(W ). der Menge aller möglichen Welten vereinbart. Konkret wird W ∈W:t∈Q(W ) hier auf die Definition von Suciu et al. [18] zurück gegriffen. berechnet. Definition 1. Angenommen werden k Relationennamen: Dies bedeutet, dass die Anfrage Q konzeptionell in jeder R1 , . . . , Rk . Eine unvollständige Datenbank ist dann eine Welt separat ausgeführt wird. Dann wird die Ergebnisrelati- endliche Menge von Dateninstanzen W = {W 1 , W 2 , . . . , W n }, on Qposs(W) gebildet, in dem alle möglichen Antworten der wobei jede Dateninstanz (Welt) durch W i = (R1i , . . . , Rki ) verschiedenen Auswertungen gesammelt werden. Zusätzlich beschrieben ist. Eine probabilistische Datenbank ist ein Wahr- wird die Eintrittswahrscheinlichkeit einer möglichen Ant- scheinlichkeitsraum D = (W, P) über einer unvollständigen wort durch das Aufsummieren der Welten, in der das Ant- Datenbanken P W. Damit ist P : W → [0, 1] eine Funktion, worttupel in der Antwort auftritt, gebildet. Offensichtlich sodass W ∈W P(W ) = 1 gilt. Es wird vorausgesetzt, dass gibt die Def. (2) nur die Semantik der Anfrageauswertung ∀W ∈ W : P(W ) > 0 gilt. vor. Eine einzelne Auswertung in allen Welten ist praktisch 4 Im Allgemeinen ist die Semantik des Wahrscheinlichkeits- In dem Beispielszenario werden die Ereignisschlüssel von maß P nicht vordefiniert. Konkret wird hier der Spezialfall Arte, ArteExp und ArteMat als {aid}, {exp, aid} und {method, aid} vereinbart, siehe Abb. (1). 3 5 XRF und ICP-MS stehen für die x-ray fluorescence und die Da die Tabelle Arte deterministisch ist, wird P(X1 = t1 ) = inductively coupled plasma mass spectrometry Methode. . . . = P(X3 = t3 ) = 1 gesetzt. nicht umsetzbar, da die Anzahl aller Welten exponentiell in Algorithm 1: gen(Φpa , t) Datengröße anwachsen kann. Data: Klauselmustermenge Φpa , Tupel t ∈ Rev Result: Formel in DNF kodiert als Φt 3. EREIGNISMUSTER 1 Φt := ∅; In diesem Kapitel wird die praktische Auswertung einer 2 foreach CP ∈ Φpa do Algebraanfrage Q auf einer probabilistischen Datenbank dis- 3 C := (true); kutiert. Dabei wird das Konzept der Ableitungsformeln vor- 4 foreach ETRi in CP do gestellt und eine neue Technik zur Verwaltung von komple- 5 if t[ETRi ] 6= null then xen Tupelereignissen eingeführt. 6 C := C • t[ETRi ]; 7 else 3.1 Ableitungsformeln 8 C := C • (false); Entsprechend Def. (2) muss zur Auswertung einer Anfra- 9 end ge die Ergbeniswahrscheinlichkeit PrQ (t) für jedes Ergeb- 10 end nistupel berechnet werden. Fuhr und Röllecke schlugen in 11 if simpl(C) 6= false then [4] vor, diese Wahrscheinlichkeiten mittels von Ableitungs- 12 Φt := Φt ∪ {simpl(C)}; formeln φt zu berechnen. Dabei werden alle Ableitungsfor- 13 end meln neben dem eigentlichen Datenanteil der Tupel verwal- 14 end tet. Prinzipiell ist eine Ableitungsformel φt durch eine aus- 15 return Φt ; sagenlogische Formel gegeben, welche mittels den Zufallsva- riablen (Xk = tid )6 und den logischen Operatoren ∧, ∨ und ¬ gebildet wird. Fuhr und Röllecke haben geschlussfolgert, dass PrQ (t) durch Wahrscheinlichkeit P(φt ≡ true) ermit- 3.2 Verwaltung von Ableitungsformeln mittels telt werden kann, d.h. PrQ (t) = P(φt ≡ true). Somit kann Ereignismustern und Basisereignismengen PrQ (t) durch P(φt ≡ true) berechnet werden, ohne dass Um eine logische Formel in einer strukturierten Form zu über alle Welten von W iteriert werden muss (siehe Def. verwalten wird sie in die bekannte disjunktive Normalform (2)). Im Folgenden wird P(φt ≡ true) durch P(φt ) abge- (DNF) transformiert. kürzt. Die Konstruktion von φt greift auf die Struktur der betrachteten Anfrage Q zurück. Definition 4. Angenommen φt ist eine Ableitungsformel. Ein Literal ist gegeben durch ein negiertes oder unnegiertes Definition 3. Angenommen Q ist eine Algebraanfrage und Basisereignis von φt , d.h. L ≡ ¬(Xk = tid ) oder L ≡ (Xk = D = (W, P) ist eine probabilistische Datenbank. Die Ablei- tid ). Eine Konjunktion von Literalen wird als Klausel C be- tungsformel φt ist dann wie folgt rekursiv definiert: zeichnet, d.h. C = L1 ∧ . . . ∧ Lm . Eine Formel φdnf t in DNF Q ≡ R : φt := (Xk = tid ), wenn t ∈ TupBl(k) ist eine Disjunktion von Klauseln, d.h. φdnf t = C1 ∨ . . . ∨ Cr , sodass φt ≡ φdnf t . Q ≡ σc (Q1 ) : φt := φt1 _ Da relationale Standardoperatoren zur Manipulation von Q ≡ πA (Q1 ) : φt := φt̂ DNF-Formeln verwendet werden sollen (siehe Def. (6) un- t̂∈Q1 ,t̂[A]=t ten), empfiehlt es sich DNF-Formeln in Form von Tupeln Q ≡ Q1 ./ Q2 : φt := φt1 ∧ φt2 und Mengen zu kodieren. Q ≡ Q1 ∪ Q2 : φt := φt1 ∨ φt2 Definition 5. Um eine Formel φdnf t in DNF zu kodieren, Q ≡ Q1 \ Q2 : φt := φt1 ∧ ¬(φt2 ) wird eine Menge von Klauseltupeln (bezeichnet als Φt ) be- nutzt, d.h. Φt := {C1 , . . . , Cr }, wobei Ci ein Klauseltu- wobei Xk eine Blockvariable ist und TupBl(k) alle Tupel pel ist. Ein Klauseltupel Ci = (L1 , . . . , Lmi ) korrespondiert eines Blockes k zurück gibt (siehe Kap. (2)). Falls ti nicht dann mit einer Klausel L1 ∧ . . . ∧ Lmi von φdnf t . in einer Eingabeanfrage existiert (d.h. ti ∈ / Qi ), wird φti := false gesetzt (siehe Vereinigung- und Differenzoperator). Die grundlegende Idee des hier vorgestellten Ansatzes lässt sich dann in folgenden vier Schritten beschreiben: Abb. (3) zeigt die Ableitungsformeln für die Ergebnistu- pel der Beispielanfrage Qe . Die Wahrscheinlichkeit P(φt ) (i) das Bilden einer Menge von Klauselmustern (gekenn- kann mit Standardalgorithmen berechnet werden (z.B. [12, zeichnet als Φpa ), welche direkt von der Algebraanfrage 6]). Wie man dort sieht, besitzen Ereignistupel im Allgemei- Q abgeleitet wird (d.h. unabhängig von den aktuellen nen unterschiedliche Ableitungsformeln. Mehrere Verfahren Daten in der Datenbank), (z.B. [4, 3, 13]) müssen eine komplexe Ableitungsformel für (ii) das Generieren einer Menge relevanter Basisereignissen jedes einzelne Tupel, welches innerhalb der Anfrageverarbei- für jedes Ergebnistupel während der relationalen An- tung entsteht, verwalten. Praktische Anwendungsszenarien frageverarbeitung (verwaltet in einer erweiterten Er- haben jedoch bereits gezeigt, dass Ableitungsformel mit ei- gebnisdatenrelation Rev ), ner Größe von 10 MB für ein Ergebnistupel auftreten können (iii) die Konstruktion einer DNF-Formel kodiert als Φt [14]. Dementsprechend folgt der hier entwickelte Ansatz der für jedes Ergebnistupel mittels des Generierungsalgo- Argumentation von Antova et al. [1] und Das Sarma et al. rithmus gen(Φpa , t), t ∈ Rev und [16], dass die Verwaltung und die Verarbeitung von komple- (iv) die Berechnung von P(φdnf t ) mit Hilfe eines Standar- xen Ableitungsformeln durch relationale Datenbanksysteme dalgorithmus (z.B. [12, 6]). nicht zielführend sind, da solche Systeme nicht für die Ver- Bevor der Generierungsalgorithmus gen(Φpa , t) diskutiert arbeitung von komplexen logischen Formeln ausgelegt sind. wird, werden zunächst die Bedeutung von Φpa und Rev nä- 6 Ein solches Ereignis wird auch als Basisereignis bezeichnet. her beleuchtet. tid aid type culture φt P(φt ) r1 (t4 , t6 , t8 , t1 ) art1 vase fragment roman ([(X4 = t4 ) ∨ (X5 = t6 )]∨ 0.706 (X7 = t8 )) ∧ (X1 = t1 ) r2 (t5 , t9 , t1 ) art1 vase fragment greek [(X4 = t5 ) ∨ (X7 = t9 )]∧ 0.58 (X1 = t1 ) r3 (t7 , t11 , t2 ) art2 spear head egyptian [(X6 = t7 ) ∨ (X9 = t11 )]∧ 0.8 (X2 = t2 ) r4 (t10 , t2 ) art2 spear head punic [(X8 = t10 ) ∨ (F alse)]∧ 0.8 (X2 = t2 ) Figure 3: Die Ergebnistupel von Qe mit ihren Ableitungsformeln (φt ) und ihren Ergebniswahrscheinlichkeiten (P(φt )) Mustermenge Φpa : Die Mustermenge Φpa besteht aus (W, P) eine probabilistischen Datenbank. Die Klauselmus- einer Menge von Klauselmustern {CP1 , . . . , CPl }. Ein Klau- termenge Φpa und die Ereignisdatenrelation Rev werden dann selmuster CP = (ETRi1 , . . . , ETRim ) ist wiederum gegeben rekursiv mittels der folgenden Regel gebildet8 : durch ein Tupel von Basisereignismustern. Dabei symboli- siert ein Muster ETRi genau ein Basisereignis (Xk = tid ) Q ≡ Ri : Φpa := {(ETRi )}, der Basisrelation Ri . Falls z.B. das Klauselmuster CP = Rev := {t • (Xk = tid ) | t ∈ Ri } (ETArteExp , ETArteM at ) betrachtet wird, verkörpert CP al- Q ≡ σc (Q1 ) : Φpa := Φpa ev := σc (R1ev ) 1 ,R le Klauseln in denen das erste Basisereignis aus der Relation ArteExp stammt und das zweite Basisereignis aus ArteM at Q ≡ πA (Q1 ) : Φpa := Φpa 1 , genommen wird. ev R := πA∪{all ETRi columns} (R1ev ) Basisereignisse in Rev : Die Ereignisdatenrelation Rev Q ≡ Q1 ./ Q2 : Φpa := Φpa pa ev := R1ev ./ R2ev 1 × Φ2 , R besteht aus allen Datentupeln, sowie aus jeweils einer Men- ge von Basisereignissen für jedes Datentupel. Dabei werden Q ≡ Q1 ∪ Q2 : Φpa := Φpa pa 1 ∪ Φ2 , genau die Basisereignisse gespeichert, welche notwendig sind Rev := R1ev ./full outer R2ev um die Ableitungsformel für ein bestimmtes Datentupel zu bilden. Zu diesem Zwecke werden die Datenrelationen durch Um die endgültige Ableitungsformel φdnft für ein Ergebni- zusätzliche Spalten erweitert, welche Basisereignisse spei- stupel t zu bilden, werden die generierten Φt -Formeln aller chern. Alle Basisereignisse einer spezifischen Zeile gehören Tupel in Rev mit den selben Datenwerten wie das Ergebni- dabei zu dem jeweiligen Datentupel. Jede neue Spalte wird stupel t disjunktiv verknüpft: mit einer Basisrelation Ri assoziiert und entsprechend mit _ einem Musternamen ETRi bezeichnet, siehe Abb. (1) und φdnf t := gen(Φpa , t̂), (4). t̂∈Rev ,t̂[datAttr]=t Algorithmus gen(Φpa , t): Nach der Konstruktion von Φpa und Rev generiert der Algoritmus gen(Φpa , t) eine Ab- wobei datAttr die Menge aller Datenattribute der Ergebnis- leitungsformel (kodiert als Φpa ) für ein Tupel der Relation datenrelation Rev repräsentiert, d.h. alle Attribut ohne die Rev . Im Wesentlichen ersetzt der Algorithmus der Basiser- jeweiligen ETRi Spalten9 . eignismuster mit den jeweiligen zuordenbaren Basisereignis- sen (siehe Zeilen 2 bis 11 in Algorithmus (1)). Die Vergleichs- Satz 1. Sei Rev und φdnf t konstruiert wie in Def. (6) an- kriterien sind durch die Musternamen ETRi und die korre- gegeben, dann gilt (i) Qposs(W) = πdatAttr (Rev ) und (ii) spondieren Bezeichnungen der Ereignisspalten von Rev ge- ∀t ∈ Qposs(W) : PrQ (t) = P(φdnf t ). geben. Der Operator • konkateniert zwei Tupel. Bevor eine erzeugte Klausel C zu der Ergebnisformel Φt hinzugenom- men wird, werden alle Klauseln C logisch vereinfacht (siehe Zeilen 12 und 13). Hierfür werden logische Gesetze wie Idem- 4. VERWANDTE ARBEITEN potenz und Kontradiktion eingesetzt. Eine umfassende Monographie über probabilistische Da- tenbank wurde kürzlich von Suciu et al. [18] veröffentlicht. Die Klauselmustermenge Φpa und die Ereignisdatenrelati- Daneben wurden in den letzten Jahren mehrere probabilis- on Rev werden rekursiv über die Struktur der betrachteten tische Datenbanksysteme erfolgreich umgesetzt (z.B. [15, 7, Algebraanfrage Q definiert. Prinzipiell wird Φpa in einer Art 19]). In vorangegangenen Arbeiten [10, 11] des Autors wurde und Weise konstruiert, dass die erzeugten Muster der grund- ein probabilistisches Daten- und Anfargemodell entworfen, legenden Semantik der Def. (3) genügt und alle möglichen welches Konzepte aus dem Gebiet des Information Retrievals Ereignisse erzeugt werden können, die nötig sind um φdnf t zu mit Technologien der Datenbankwelt kombiniert. Die dabei erzeugen. Exemplarisch wird die Ereignisdatenrelation der 8 Beispielanfrage Qe in Abb. (4) gezeigt. Um die DNF-Repräsentation von Def. (5) zu bewah- ren werden Tupel verflacht. Wenn z.B. Φpa 1 = {(L1 , L2 )} Definition 6. Sei Q eine positive Algebraanfrage7 und D = und Φpa 2 = {(L 3 , L 4 )} gegeben sind, dann ergibt sich Φpa pa pa 1 × Φ2 = {(L1 , L2 , L3 , L4 )} anstelle von Φ1 × Φ2 = pa 7 Genau wie die Systeme [15], [19] und [7] fokussiert sich {((L1 , L2 ), (L3 , L4 ))}. 9 der hier vorgestellte Ansatz momentan auf Anfragen ohne Diese Notation von datAttr wird in der restlichen Arbeit Differenzoperationen. weiter verwendet. tid aid type culture ETArteExp ETArteM at ETArte (t4 , t8 , t1 ) art1 vase fragment roman X4 = t4 X7 = t8 X1 = t1 (t5 , t9 , t1 ) art1 vase fragment greek X4 = t5 X7 = t9 X1 = t1 (t6 , t8 , t1 ) art1 vase fragment roman X5 = t6 X7 = t8 X1 = t1 (t7 , t11 , t2 ) art2 spear head egyptian X6 = t7 X9 = t11 X2 = t2 (t10 , t2 ) art2 spear head punic null X8 = t10 X2 = t2 Φpa e = {(ETArteExp , ETArte ), (ETArteM at , ETArte )} Figure 4: Die Ergebnisdatenrelation Reev für die Beispielanfrage Qe . entwickelten Techniken werden in dem erweiterten proba- • Induktionsschritt: n → n + 1 mit der Induktionsannah- bilistischen Datenbanksystem ProQua 10 umgesetzt. Im Ge- me (IA), dass für alle Anfragen mit bis zu n Operatoren gilt: gensatz zu anderen Systemen (z.B. [15, 7, 19]) unterstützt ProQua logik-basierte Ähnlichkeitsanfragen, sowie die Ge- (i) t ∈ R1ev ⇔ t ∈ W Q1 und wichtung von Teilanfragen innerhalb seiner Anfragesprache (ii) ∀t ∈ Q1 : gen(Φpa 1 , t̂) ≡ φt1 . ev , QSQL2 [8, 9]. t̂∈R1 t̂[datAttr]=t • Operator: Q ≡ σsc (Q1 ), d.h. zu zeigen 5. ZUSAMMENFASSUNG ? In dieser Arbeit wurde ein Konzept vorgestellt, welches (i) t ∈ πdatAttr (σsc (R1ev )) ⇔ t ∈ σsc (Q1 ), ? mit der Hilfe von Ereignismustern und Basisereignismen- gen(Φpa W (ii) ∀t ∈ σsc (Q1 ) : 1 , t̂) ≡ φt1 gen komplexe Tupelereignisse verwalten kann. Diese Tupe- t̂∈σsc (R1ev ), t̂[datAttr]=t lereignisse entstehen bei der Auswertung einer komplexen positiven Algebraanfrage auf einer probabilistischen BID- Beweis: Datenbank. Der wesentliche Vorteil dieser Methode liegt in dem natürlichen Ablegen von Ableitungsformeln in einer (i) t ∈ πdatAttr (σsc (R1ev )) ⇔ ∃t̂ ∈ R1ev ∧ t̂[datAttr] = t ∧ strukturierten Form innerhalb einer erweiterten Datenrelati- IA sc(t) = true ⇔ t̂[datAttr] ∈ Q1 ∧ t̂[datAttr] = t ∧ sc(t) = on. Dadurch können die Tupelereignisse direkt mittels eines true ⇔ t ∈ σsc (Q1 ) X RDBMS verarbeitet werden. (Bed. sc(t) ist nur über Attribute von datAttr definiert) Danksagung: Sebastian Lehrack wurde innerhalb der Pro- jekte SCHM 1208/11-1 und SCHM 1208/11-2 von der Deut- (ii) ∀t ∈ σsc (Q1 ) ⇒ sc(t) = true ∧(t̂[datAttr] = t ⇒ sc(t̂) = schen Forschungsgesellschaft unterstützt. true) ⇒ gen(Φpa W ∀t ∈ σsc (Q1 ) : 1 , t̂) = t̂∈σsc (R1ev ), APPENDIX t̂[datAttr]=t IA gen(Φpa W A. BEWEIS FüR SATZ (1) 1 , t̂) ≡ φt1 X ev , t̂∈R1 Es wird angenommen, dass PrQ (t) = P(φt ), falls φt gebil- t̂[datAttr]=t det wurde wie in Def. (3) spezifiziert (siehe [4]). Somit muss (Bed. t̂[datAttr] = t ist strenger als sc(t)) gezeigt werden, dass (i) Qposs(W) = πdatAttr (Rev ) und (ii) ∀t ∈ Qposs(W) : φt ≡ φdnf t . • Operator: Q ≡ πA (Q1 ), d.h. zu zeigen Induktion über die Anzahl der Operatoren n von Q ? (i) t ∈ πdatAttr (πA∪{all ETs} (R1ev )) ⇔ t ∈ πA (Q1 ), • Induktionsanfang: n = 1 : Q = Ri , d.h. zu zeigen ? gen(Φpa W W ? (ii) ∀t ∈ πA (Q1 ) : 1 , t̂) ≡ φt̂ , (i) t ∈ πdatAttr ({t • (Xk = tid ) | t ∈ Ri }) ⇔ t ∈ Ri , ev ), t̂∈πA∪{all ETs} (R1 t̂∈Q1 , W ? t̂[A]=t (ii) ∀t ∈ Ri : gen(ETRi , t̂) ≡ (Xk = tid ), t̂[datAttr]=t t̂∈{t•(Xk =tid )|t∈Ri }, Beweis: t̂[datAttr]=t Beweis: (i) t ∈ πdatAttr (πA∪{all ETs} (R1ev )) ⇔ t ∈ πA (R1ev ) ⇔ ∃t̂ : IA (i) πdatAttr ({t • (Xk = tid ) | t ∈ Ri }) = Ri X t̂[A] = t∧ t̂ ∈ R1ev ⇔ ∃t̂ : t̂[A] = t ∧ t̂ ∈ Q1 ⇔ t ∈ πA (Q1 )X (ii) ∀t̂ ∈ {t • (Xk = tid ) | t ∈ Ri } : nach Konstruktion gibt es eineindeutiges t ∈ Ri , sodass t̂ = t • (Xk = tid ) (A besteht nur aus Datenattributen, d.h. A = datAttr) gen(Φpa W ⇒ ∀t ∈ Ri : W gen(ETRi , t̂) ≡ (ii) ∀t ∈ πA (Q1 ) : 1 , t̂) = ev ), t̂∈πA∪{all ETs} (R1 t̂∈{t•(Xk =tid )|t∈Ri }, t̂[datAttr]=t t̂[datAttr]=t 0 1 gen(ETRi , t • (Xk = tid )) ≡ (Xk = tid ) X C IA gen(Φpa W W 1 , ṫ)A = B @ ev ), t̂∈πA∪{all ETs} (R1 ev , ṫ∈R1 10 http://dbis.informatik.tu-cottbus.de/ProQua/ t̂[A]=t ṫ[datAttr1 ]=t̂ B. REFERENCES W W φt̂ = φt̂ X ev ), t̂∈πA∪{all ETs} (R1 t̂∈Q1 , t̂[A]=t t̂[A]=t [1] L. Antova, T. Jansen, C. Koch, and D. Olteanu. Fast and simple relational processing of uncertain data. In (da A ⊆ datAttr1 und Idempotenz gilt) ICDE, pages 983–992, 2008. [2] D. Barbará, H. Garcia-Molina, and D. Porter. The management of probabilistic data. IEEE Trans. on • Operator: Q ≡ Q1 ./ Q2 , d.h. zu zeigen Knowl. and Data Eng., 4:487–502, October 1992. ? [3] R. Fink, D. Olteanu, and S. Rath. Providing support (i) t ∈ πdatAttr (R1ev ./ R2ev ) ⇔ t ∈ Q1 ./ Q2 , ? for full relational algebra in probabilistic databases. In gen(Φpa pa W (ii) ∀t ∈ Q1 ./ Q2 : 1 × Φ2 , t̂) ≡ φt1 ∧ φt2 ICDE, pages 315–326, 2011. t̂∈R1 ev ./Rev , 2 t̂[datAttr]=t [4] N. Fuhr and T. Roelleke. A probabilistic relational algebra for the integration of information retrieval and Beweis: database systems. ACM Trans. IS, 15(1):32–66, 1997. [5] F. Henze, H. Lehmann, and W. Langer. CISAR - A (i) t ∈ πdatAttr (R1ev ./jc R2ev ) ⇔ ∃t1 , t2 : t = t1 [datAttr1 ] • Modular Database System as a Basis for Analysis and t2 [datAttr2 ] ∧ jc(t1 , t2 ) = true ⇔ t1 ∈ πdatAttr1 (R1ev ) ∧ t2 ∈ IA Documentation of Spatial Information. In CAA, pages πdatAttr2 (R2ev ) ⇔ t1 ∈ Q1 ∧ t2 ∈ Q2 ∧ jc(t1 , t2 ) = true ⇔ 228–233, 2007. t1 • t2 ∈ Q1 ./jc Q2 ⇔ t ∈ Q1 ./ Q2 X [6] R. M. Karp, M. Luby, and N. Madras. Monte-carlo approximation algorithms for enumeration problems. (Verbundbed. jc(t1 , t2 ) (nat. Verbund) bezieht sich nur auf Journal of Algorithms, 10(3):429–448, 1989. Datenattributen, da durch Konstruktion stets gilt [7] C. Koch. MayBMS: A System for Managing Large evAttr1 ∩ evAttr2 = ∅) Uncertain and Probabilistic Databases. In Managing and Mining Uncertain Data, ch. 6. Springer-Verlag, gen(Φpa pa W (ii) ∀t ∈ Q1 ./ Q2 : 1 × Φ2 , t̂) = t̂∈R1 ev ./Rev , 2008. 2 t̂[datAttr]=t [8] S. Lehrack, S. Saretz, and I. Schmitt. QSQL2: Query gen(Φpa pa W 1 × Φ2 , t 1 • t 2 ) = Language Support for Logic-Based Similarity t1 ∈R1ev ,t ∈Rev , 2 2 (t1 •t2 )[datAttr]=t Conditions on Probabilistic Databases. In RCIS, 2012 W gen(Φpa pa (to appear). 1 , t1 ) ∧ gen(Φ2 , t2 ) = t1 ∈R1ev ,t ∈Rev , 2 2 [9] S. Lehrack and I. Schmitt. QSQL: Incorporating (t1 •t2 )[datAttr]=t Logic-Based Retrieval Conditions into SQL. In IA gen(Φpa gen(Φpa W W 1 , t1 )∧ 2 , t2 ) = φt1 ∧ φt2 X DASFAA, pages 429–443, 2010. ev , t1 ∈R1 ev , t2 ∈R2 t1 [datAttr1 ]=t t2 [datAttr2 ]=t [10] S. Lehrack and I. Schmitt. A Probabilistic Interpretation for a Geometric Similarity Measure. In (da (t1 • t2 )[datAttr] = t ⇒ jc(t1 • t2 ) = true; konkate- ECSQARU, pages 749–760, 2011. nierte Muster (erzeugt durch ×) drücken Konjunktion aus [11] S. Lehrack and I. Schmitt. A Unifying Probability und Φpai enthält nur Basisereignismuster von ti ) Measure for Logic-Based Similarity Conditions on Uncertain Relational Data. In NTSS, pages 14–19, • Operator: Q ≡ Q1 ∪ Q2 , d.h. zu zeigen 2011. ? (i) t ∈ πdatAttr (R1ev ./f o R2ev ) ⇔ t ∈ Q1 ∪ Q2 , [12] D. Olteanu, J. Huang, and C. Koch. Approximate ? confidence computation in probabilistic databases. In gen(Φpa pa W (ii) ∀t ∈ Q1 ∪ Q2 : 1 ∪ Φ2 , t̂) ≡ φt1 ∨ φt2 ICDE, pages 145–156, 2010. ev ./f o Rev , t̂∈R1 2 t̂[datAttr]=t [13] D. Olteanu and H. Wen. Ranking Query Answers in Probabilistic Databases: Complexity and Efficient Beweis: Algorithms. In ICDE, 2012 (to appear). [14] C. Ré and D. Suciu. Approximate lineage for (i) t ∈ πdatAttr (R1ev ./f o R2ev ) ⇒ t ∈ πdatAttr1 (R1ev ) ∨ t ∈ IA probabilistic databases. PVLDB, 1(1):797–808, 2008. πdatAttr2 (R2ev ) ⇔ t ∈ Q1 ∨ t2 ∈ Q2 ⇔ t ∈ Q1 ∪ Q2 [15] C. Ré and D. Suciu. Managing Probabilistic Data with MystiQ: The Can-Do, the Could-Do, and the (wegen der Def. eines vollen äußeren Verbundes und datAttr = Can’t-Do. In SUM, pages 5–18, 2008. datAttr1 = datAttr2 ) [16] A. D. Sarma, O. Benjelloun, A. Y. Halevy, and J. Widom. Working models for uncertain data. In gen(Φpa pa W (ii) ∀t ∈ Q1 ∪ Q2 : 1 ∪ Φ2 , t̂) = ev ./f o Rev , t̂∈R1 ICDE, page 7, 2006. 2 t̂[datAttr]=t [17] F. Schaefer and A. Schulze. OpenInfRA – Storing and gen(Φpa pa W ` ´ 1 , t̂) ∨ gen(Φ2 , t̂) = retrieving information in a heterogenous ev ∨t̂∈Rev , t̂∈R1 2 documentation system. In CAA, 2012 (to appear). t̂[datAttr]=t IA [18] D. Suciu, D. Olteanu, C. Ré, and C. Koch. gen(Φpa gen(Φpa W W 1 , t̂) ∨ 2 , t̂) = φt1 ∨ φt2 X Probabilistic Databases. Synthesis Lectures on Data ev , t̂∈R1 ev , t̂∈R2 t̂[datAttr]=t t̂[datAttr]=t Management. Morgan & Claypool Publishers, 2011. [19] J. Widom. Trio: A system for data, uncertainty, and (wegen der Def. eines vollen äußeren Verbundes und da Φpa lineage. In Managing and Mining Uncertain Data, eine disjunktiv verknüpfte Klauselkombination beschreibt) pages 113–148. Springer, 2008.