Ereignismuster für die Verwaltung von komplexen Tupelereignissen in Probabilistischen Datenbanken

Abstract

Probabilistische Datenbanken haben sich als adaquate Technik zur Verwaltung und Verarbeitung von umfangreichen unsicheren Datenmengen etabliert. Eine der gro ten Herausforderungen fur probabilistische Datenbanken ist eine efziente Anfrageverarbeitung. Eine zentrale Rolle spielen dabei Ableitungsformeln, welche komplexe Tupelereignisse in Form von aussagenlogischen Formeln verkorpern. Eine direkte Abspeicherung und Verarbeitung von komplexen logischen Formeln wird von relationalen Datenbanksystemen jedoch nicht unterstutzt. Diese Arbeit stellt Ereignismuster als geeignetes Mittel vor, um Ableitungsformeln mittels eines RBDMS verwalten zu konnen.

MOTIVATION

3 10 4 aid art1 art1 art1 art2 aid art1 art1 art2 art2

ArteExp culture roman greek roman egyptian ArteMat culture roman greek punic egyptian age conf conf (X1 = t1) (X2 = t2) (X3 = t3) (X4 = t4) (X4 = t5) (X5 = t6) (X6 = t7) ETArteMat (X7 = t8) (X7 = t9) (X8 = t10) (X9 = t11) durch die Neuentwicklung des CISAR-Projektes1 [ 5 ], welches als internet-basiertes Geo-Informationssystem fur Archaologie und Gebaudegeschichte entwickelt worden ist. Die hier vorgestellten Techniken werden umfassend in dem Nachfolgesystem OpenInfRA eingesetzt [ 17 ].

In dem stark vereinfachten Beispielszenario werden die deterministische Tabelle Artefakte (Arte) und die zwei probabilistischen Tabellen Artefakte klassi ziert bei Experten2 (ArteExp) und Artefakte klassi ziert bei Material (ArteMat ) verwendet, siehe Abb. (1). In der Datentabelle Arte werden Informationen uber mehrere Artefakten gespeichert, welche wahrend einer archaologischen Ausgrabung gefunden worden sind. Dabei wird mittels der Sondage-Nummer (Attribut sond ) die geographische Fundstelle eines Artefaktes beschrieben.

Zusatzlich geben mehrere Spezialisten verschiedene Expertisen uber die Ursprungskultur eines Artefakts (Attribut culture) ab, siehe Tabelle ArteExp. Diese Einschatzungen werden mit einem Kon denzwert annotiert (Attribut conf ), 1http://www.dainst.org/en/project/cisar/ 2Die Spalten tid, conf und ET (:::) gehoren nicht zu den eigentlichen Datentabellen. Mittels der Spalte tid werden Tupel adressiert. Die Bedeutung von conf und ET(:::) wird in den nachsten Abschnitten erlautert. select aid, type, culture from ( select aid, culture

from ArteExp union select aid, culture from ArteMat ) origin inner join ( select *

from Arte ) prop on ( origin.aid = prop.aid ) aid,type,culture

./ [

Arte

aid,culture aid,culture

ArteExp

ArteM at

welche die Wahrscheinlichkeit ausdruckt, dass das entsprechende Artefakt zu der bestimmten Kultur gehort. Neben den subjektiven Expertenmeinungen werden auch objektive Methoden einbezogen. Diese archaometrischen Methoden (z.B. XRF und ICS-MS3) basieren auf einer Materialanalyse. In Kombinationen mit den Fundstellen und dem Artefaktalter kann die Materialzusammensetzung wichtige Hinweise auf die Ursprungskultur geben, welche dann ebenfalls mittels Kon denzwerten quanti ziert werden.

Basierend auf den eingefuhrten Datentabellen soll exemplarisch die folgende Anfrage Qe bearbeitet werden: Bestimme alle Artefakte mit ihren jeweiligen Typ und ihren moglichen Ursprungskulturen. Um diese Anfrage zu beantworten wird sie zunachst in der Anfragesprache QSQL2 [ 8 ] formuliert, siehe Abb. (2). Anschlie end wird von dem eigentlichen SQL-Syntax abstrahiert, indem sie in Form einer Algebraanfrage in den nachsten Kapiteln weiter verarbeitet wird.

Die Arbeit ist wie folgt gegliedert. In Kap. (2) werden zunachst die Grundlagen fur die weiteren Betrachtungen gelegt. Danach steht der wesentliche Beitrag dieser Arbeit in Form der Ereignismuster in Kap. (3) im Mittelpunkt. In den Kap. (4) und (5) wird die Arbeit mit einer Diskussion uber verwandte Arbeiten und einer Zusammenfassung abgeschlossen. Der Beweis des Satzes (1) wird im Anhang (A) gefuhrt.

GRUNDLAGEN

In einer probabilistischen Datenbanken werden mehrere moglichen Datenbankinstanzen, welche auch Welten genannt werden, gleichzeitig verwaltet und abgefragt. Dabei wird die c"hreearlheeiWtealbt\zuablislduennbwekiradnnetinanWgeanhorsmchmeeinnl.icUhkmeitdsimesae Uunbseirder Menge aller moglichen Welten vereinbart. Konkret wird hier auf die De nition von Suciu et al. [ 18 ] zuruck gegri en.

De nition 1. Angenommen werden k Relationennamen: R1; : : : ; Rk. Eine unvollstandige Datenbank ist dann eine endliche Menge von Dateninstanzen W = fW 1; W 2; : : : ; Wing, wobei jede Dateninstanz (Welt) durch W i = (R1i; : : : ; Rk) beschrieben ist. Eine probabilistische Datenbank ist ein Wahrscheinlichkeitsraum D = (W; P) uber einer unvollstandigen Datenbanken W. Damit ist P : W ! [0; 1] eine Funktion, sodass PW 2W P(W ) = 1 gilt. Es wird vorausgesetzt, dass 8W 2 W : P(W ) > 0 gilt.

Im Allgemeinen ist die Semantik des Wahrscheinlichkeitsma P nicht vorde niert. Konkret wird hier der Spezialfall 3XRF und ICP-MS stehen fur die x-ray uorescence und die inductively coupled plasma mass spectrometry Methode. der block-independent-disjoint Datenbanken (BID) [ 2 ] benutzt, da Tupel- und Attributunsicherheit untersutzt werden soll. Eine BID ist eine probabilistische Datenbank in der die gegebenen Tupel in Blocke unterteilt werden. Dabei kann ein Block sich nicht uber mehrere Relationen erstrecken. Es wird vereinbart, dass alle Tupel innerhalb eines Blockes mit disjunkten Tupelereignissen verbunden sind. Ein Tupelereignis beschreibt das Vorhandensein oder das Nicht-Vorhandensein eines Tupel in einer beliebigen Welt. Wegen der Disjunktheit der Tupelereignisse kann maximal ein Tupel eines Blockes in einer bestimmten Welt vorhanden sein. Dagegen sind Tupel von verschiedenen Blocken mit gegenseitig unabhangigen Tupelereignissen assoziiert.

Fur die De nition von Blocken werden Ereignisschlussel in Form von Attributmengen angewendet4. So wird ein Block wird von Tupeln gebildet, welche die gleichen Werte fur die Attribute des Schlussel haben. Anschlie end wird fur jeden Block eine unabhangige Zufallsvariable Xk eingefuhrt. Das konkrete Eintreten einer Zufallsvariable (Xk = tid) reprasentiert ein Tupelereignis und wird quanti ziert mit dem Kon denzwert des Tupels tid, siehe die Spalten conf und ET (:::) in der Abb. (1)5. Die kombinierte Wahrscheinlichkeitsverteilung aller Blockvariablen bilden schlie lich P. Um eine Algebraanfrage auf einer probabilistischen Datenbank auszufuhren, wird folgende Anfragesemantik verwendet [ 18 ]. berechnet.

De nition 2. Sei Q eine Algebraanfrage und D = (W; P) eine probabilistische Datenbank. Die Menge aller moglichen Antworttupel einer Anfrage Q ist de niert als Qposs(W) = ft j 9W 2 W : t 2 Q(W )g: Zusatzlich werden die Eintrittswahrscheinlichkeiten aller moglichen Antworten in der Funktion PrQ : Qposs(W) ! (0; 1] als PrQ(t) := P P(W ): W 2W:t2Q(W )

Dies bedeutet, dass die Anfrage Q konzeptionell in jeder Welt separat ausgefuhrt wird. Dann wird die Ergebnisrelation Qposs(W) gebildet, in dem alle moglichen Antworten der verschiedenen Auswertungen gesammelt werden. Zusatzlich wird die Eintrittswahrscheinlichkeit einer moglichen Antwort durch das Aufsummieren der Welten, in der das Antworttupel in der Antwort auftritt, gebildet. O ensichtlich gibt die Def. (2) nur die Semantik der Anfrageauswertung vor. Eine einzelne Auswertung in allen Welten ist praktisch 4In dem Beispielszenario werden die Ereignisschlussel von Arte, ArteExp und ArteMat als faidg, fexp; aidg und fmethod; aidg vereinbart, siehe Abb. (1). 5Da die Tabelle Arte deterministisch ist, wird P(X1 = t1) = : : : = P(X3 = t3) = 1 gesetzt. nicht umsetzbar, da die Anzahl aller Welten exponentiell in Datengro e anwachsen kann.

EREIGNISMUSTER

In diesem Kapitel wird die praktische Auswertung einer Algebraanfrage Q auf einer probabilistischen Datenbank diskutiert. Dabei wird das Konzept der Ableitungsformeln vorgestellt und eine neue Technik zur Verwaltung von komplexen Tupelereignissen eingefuhrt. 3.1

Ableitungsformeln

Entsprechend Def. (2) muss zur Auswertung einer Anfrage die Ergbeniswahrscheinlichkeit PrQ(t) fur jedes Ergebnistupel berechnet werden. Fuhr und Rollecke schlugen in [ 4 ] vor, diese Wahrscheinlichkeiten mittels von Ableitungsformeln t zu berechnen. Dabei werden alle Ableitungsformeln neben dem eigentlichen Datenanteil der Tupel verwaltet. Prinzipiell ist eine Ableitungsformel t durch eine aussagenlogische Formel gegeben, welche mittels den Zufallsvariablen (Xk = tid)6 und den logischen Operatoren ^; _ und : gebildet wird. Fuhr und Rollecke haben geschlussfolgert, dass PrQ(t) durch Wahrscheinlichkeit P( t true) ermittelt werden kann, d.h. PrQ(t) = P( t true). Somit kann PrQ(t) durch P( t true) berechnet werden, ohne dass uber alle Welten von W iteriert werden muss (siehe Def. (2)). Im Folgenden wird P( t true) durch P( t) abgekurzt. Die Konstruktion von t greift auf die Struktur der betrachteten Anfrage Q zuruck.

De nition 3. Angenommen Q ist eine Algebraanfrage und D = (W; P) ist eine probabilistische Datenbank. Die Ableitungsformel t ist dann wie folgt rekursiv de niert:

Abb. (3) zeigt die Ableitungsformeln fur die Ergebnistupel der Beispielanfrage Qe. Die Wahrscheinlichkeit P( t) kann mit Standardalgorithmen berechnet werden (z.B. [ 12, 6 ]). Wie man dort sieht, besitzen Ereignistupel im Allgemeinen unterschiedliche Ableitungsformeln. Mehrere Verfahren (z.B. [ 4, 3, 13 ]) mussen eine komplexe Ableitungsformel fur jedes einzelne Tupel, welches innerhalb der Anfrageverarbeitung entsteht, verwalten. Praktische Anwendungsszenarien haben jedoch bereits gezeigt, dass Ableitungsformel mit einer Gro e von 10 MB fur ein Ergebnistupel auftreten konnen [ 14 ]. Dementsprechend folgt der hier entwickelte Ansatz der Argumentation von Antova et al. [ 1 ] und Das Sarma et al. [ 16 ], dass die Verwaltung und die Verarbeitung von komplexen Ableitungsformeln durch relationale Datenbanksysteme nicht zielfuhrend sind, da solche Systeme nicht fur die Verarbeitung von komplexen logischen Formeln ausgelegt sind. 6Ein solches Ereignis wird auch als Basisereignis bezeichnet. Algorithm 1: gen( pa; t) pdaelnnistm.EitineinKelrauKslealutusepleLlC1^i=: :(:L^1L;:m: :i ;vLomni ) tdknof.rrespondiert

Die grundlegende Idee des hier vorgestellten Ansatzes lasst sich dann in folgenden vier Schritten beschreiben: (i) das Bilden einer Menge von Klauselmustern (gekennzeichnet als pa), welche direkt von der Algebraanfrage Q abgeleitet wird (d.h. unabhangig von den aktuellen Daten in der Datenbank), (ii) das Generieren einer Menge relevanter Basisereignissen fur jedes Ergebnistupel wahrend der relationalen Anfrageverarbeitung (verwaltet in einer erweiterten Ergebnisdatenrelation Rev), (iii) die Konstruktion einer DNF-Formel kodiert als t fur jedes Ergebnistupel mittels des Generierungsalgo(iv) driitehmBeursecghennu(ngpav;to)n, tP2( Rtdnevf) umndit Hilfe eines Standardalgorithmus (z.B. [ 12, 6 ]).

Bevor der Generierungsalgorithmus gen( pa; t) diskutiert wird, werden zunachst die Bedeutung von pa und Rev naher beleuchtet.

Mustermenge pa: Die Mustermenge pa besteht aus einer Menge von Klauselmustern fCP1; : : : ; CPlg. Ein Klauselmuster CP = (ETRi1 ; : : : ; ETRim ) ist wiederum gegeben durch ein Tupel von Basisereignismustern. Dabei symbolisiert ein Muster ETRi genau ein Basisereignis (Xk = tid) der Basisrelation Ri. Falls z.B. das Klauselmuster CP = (ETArteExp; ETArteMat) betrachtet wird, verkorpert CP alle Klauseln in denen das erste Basisereignis aus der Relation ArteExp stammt und das zweite Basisereignis aus ArteM at genommen wird.

Basisereignisse in Rev: Die Ereignisdatenrelation Rev besteht aus allen Datentupeln, sowie aus jeweils einer Menge von Basisereignissen fur jedes Datentupel. Dabei werden genau die Basisereignisse gespeichert, welche notwendig sind um die Ableitungsformel fur ein bestimmtes Datentupel zu bilden. Zu diesem Zwecke werden die Datenrelationen durch zusatzliche Spalten erweitert, welche Basisereignisse speichern. Alle Basisereignisse einer spezi schen Zeile gehoren dabei zu dem jeweiligen Datentupel. Jede neue Spalte wird mit einer Basisrelation Ri assoziiert und entsprechend mit einem Musternamen ETRi bezeichnet, siehe Abb. (1) und (4).

Algorithmus gen( pa; t): Nach der Konstruktion von pa und Rev generiert der Algoritmus gen( pa; t) eine Ableitungsformel (kodiert als pa) fur ein Tupel der Relation Rev. Im Wesentlichen ersetzt der Algorithmus der Basisereignismuster mit den jeweiligen zuordenbaren Basisereignissen (siehe Zeilen 2 bis 11 in Algorithmus (1)). Die Vergleichskriterien sind durch die Musternamen ETRi und die korrespondieren Bezeichnungen der Ereignisspalten von Rev gegeben. Der Operator konkateniert zwei Tupel. Bevor eine erzeugte Klausel C zu der Ergebnisformel t hinzugenommen wird, werden alle Klauseln C logisch vereinfacht (siehe Zeilen 12 und 13). Hierfur werden logische Gesetze wie Idempotenz und Kontradiktion eingesetzt.

Die Klauselmustermenge pa und die Ereignisdatenrelation Rev werden rekursiv uber die Struktur der betrachteten Algebraanfrage Q de niert. Prinzipiell wird pa in einer Art und Weise konstruiert, dass die erzeugten Muster der grundlegenden Semantik der Def. (3) genugt und alle moglichen Ereignisse erzeugt werden konnen, die notig sind um tdnf zu erzeugen. Exemplarisch wird die Ereignisdatenrelation der Beispielanfrage Qe in Abb. (4) gezeigt.

De nition 6. Sei Q eine positive Algebraanfrage7 und D = 7Genau wie die Systeme [ 15 ], [ 19 ] und [ 7 ] fokussiert sich der hier vorgestellte Ansatz momentan auf Anfragen ohne Di erenzoperationen. (W; P) eine probabilistischen Datenbank. Die Klauselmustermenge pa und die Ereignisdatenrelation Rev werden dann rekursiv mittels der folgenden Regel gebildet8:

Q Q

Q

Ri : c(Q1) :

A(Q1) : Q Q

Q1 ./ Q2 : Q1 [ Q2 :

pa := f(ETRi )g; Rev := ft (Xk = tid) j t 2 Rig pa := 1pa; Rev := c(R1ev) pa :=

1pa; Rev := A[fall ETRi columnsg(R1ev) pa := 1pa pa := 1pa [ 2pa; Rev := R1ev ./full outer R2ev 2pa; Rev := R1ev ./ R2ev Um die endgultige Ableitungsformel dnf fur ein Ergebnit stupel t zu bilden, werden die generierten t-Formeln aller Tupel in Rev mit den selben Datenwerten wie das Ergebnistupel t disjunktiv verknupft: tdnf :=

_ t^2Rev;t^[datAttr]=t gen( pa; t^); wobei datAttr die Menge aller Datenattribute der Ergebnisdatenrelation Rev reprasentiert, d.h. alle Attribut ohne die jeweiligen ETRi Spalten9.

Satz 1. Sei Rev und tdnf konstruiert wie in Def. (6) angegeben, dann gilt (i) Qposs(W) = datAttr(Rev) und (ii) 8t 2 Qposs(W) : PrQ(t) = P( tdnf). 4.

VERWANDTE ARBEITEN

Eine umfassende Monographie uber probabilistische Datenbank wurde kurzlich von Suciu et al. [ 18 ] vero entlicht. Daneben wurden in den letzten Jahren mehrere probabilistische Datenbanksysteme erfolgreich umgesetzt (z.B. [ 15, 7, 19 ]). In vorangegangenen Arbeiten [ 10, 11 ] des Autors wurde ein probabilistisches Daten- und Anfargemodell entworfen, welches Konzepte aus dem Gebiet des Information Retrievals mit Technologien der Datenbankwelt kombiniert. Die dabei 8Um die DNF-Reprasentation von Def. (5) zu bewahruennd werpdaen=Tufp(eLl3;vLer4)agchgte.gWebeennn szin.Bd., d1paann= efrg(Lib1t; Ls2ic)hg 1pa 2 2pa = f(L1; L2; L3; L4)g anstelle von 1pa 2pa = f((L1; L2); (L3; L4))g. 9Diese Notation von datAttr wird in der restlichen Arbeit weiter verwendet. epa = f(ETArteExp; ETArte); (ETArteMat; ETArte)g entwickelten Techniken werden in dem erweiterten probabilistischen Datenbanksystem ProQua10 umgesetzt. Im Gegensatz zu anderen Systemen (z.B. [ 15, 7, 19 ]) unterstutzt ProQua logik-basierte A hnlichkeitsanfragen, sowie die Gewichtung von Teilanfragen innerhalb seiner Anfragesprache QSQL2 [ 8, 9 ].

5. ZUSAMMENFASSUNG

In dieser Arbeit wurde ein Konzept vorgestellt, welches mit der Hilfe von Ereignismustern und Basisereignismengen komplexe Tupelereignisse verwalten kann. Diese Tupelereignisse entstehen bei der Auswertung einer komplexen positiven Algebraanfrage auf einer probabilistischen BIDDatenbank. Der wesentliche Vorteil dieser Methode liegt in dem naturlichen Ablegen von Ableitungsformeln in einer strukturierten Form innerhalb einer erweiterten Datenrelation. Dadurch konnen die Tupelereignisse direkt mittels eines RDBMS verarbeitet werden.

Danksagung: Sebastian Lehrack wurde innerhalb der Projekte SCHM 1208/11-1 und SCHM 1208/11-2 von der Deutschen Forschungsgesellschaft unterstutzt.

APPENDIX

A. BEWEIS FüR SATZ (1)

Es wird angenommen, dass PrQ(t) = P( t), falls t gebildet wurde wie in Def. (3) spezi ziert (siehe [ 4 ]). Somit muss gezeigt werden, dass (i) Qposs(W) = datAttr(Rev) und (ii) 8t 2 Qposs(W) : t tdnf.

Induktion uber die Anzahl der Operatoren n von Q Induktionsanfang: n = 1 : Q = Ri, d.h. zu zeigen (ii) 8t 2 Ri : gen(ETRi ; t^) t^2ft (Xk=tid)jt2Rig;

t^[datAttr]=t (i) t 2 datAttr(ft (Xk = tid) j t 2 Rig) ,? t 2 Ri, W ? (Xk = tid),

Beweis:

(i) datAttr(ft (Xk = tid) j t 2 Rig) = Ri X (ii) 8t^ 2 ft (Xk = tid) j t 2 Rig : nach Konstruktion gibt es eineindeutiges t 2 Ri, sodass t^ = t (Xk = tid) ) 8t 2 Ri :

W gen(ETRi ; t^) t^2ft (Xk=tid)jt2Rig;

t^[datAttr]=t gen(ETRi ; t (Xk = tid)) (Xk = tid) X 10http://dbis.informatik.tu-cottbus.de/ProQua/ Induktionsschritt: n ! n + 1 mit der Induktionsannahme (IA), dass fur alle Anfragen mit bis zu n Operatoren gilt: (i) t 2 R1ev , t 2 Q1 und (ii) 8t 2 Q1 : W gen( 1pa; t^)

t^2R1ev; t^[datAttr]=t Operator: Q

sc(Q1), d.h. zu zeigen (i) t 2 datAttr( sc(R1ev)) ,? t 2 sc(Q1), t1 : (ii) 8t 2 sc(Q1) :

Beweis:

W t^2 sc(R1ev); t^[datAttr]=t gen( 1pa; t^) ? t1 (i) t 2 datAttr( sc(R1ev)) , 9t^ 2 R1ev ^ t^[datAttr] = t ^ sc(t) = true I,A t^[datAttr] 2 Q1 ^ t^[datAttr] = t ^ sc(t) = true , t 2 sc(Q1) X (Bed. sc(t) ist nur uber Attribute von datAttr de niert) (ii) 8t 2 sc(Q1) ) sc(t) = true ^(t^[datAttr] = t ) sc(t^) = true) ) 8t 2 sc(Q1) : gen( 1pa; t^) =

W t^2 sc(R1ev); t^[datAttr]=t

W gen( 1pa; t^) IA t^2R1ev; t^[datAttr]=t (Bed. t^[datAttr] = t ist strenger als sc(t)) t1 X Operator: Q

A(Q1), d.h. zu zeigen (i) t 2 datAttr( A[fall ETsg(R1ev)) ,? t 2 A(Q1), (ii) 8t 2 A(Q1) : W gen( 1pa; t^) ? t2 A[fall ETsg(R1ev); ^ t^[datAttr]=t (A besteht nur aus Datenattributen, d.h. A = datAttr) (ii) 8t 2 A(Q1) : W gen( 1pa; t^) = t2 A[fall ETsg(R1ev); ^ t^[datAttr]=t 0 1

W B W t^2 A[fat^[lAlE]=Ttsg(R1ev);@ t_[dat_t2ARt1etrv1;]=t^ gen( 1pa; t_)C I=A

A (da A

datAttr1 und Idempotenz gilt) (i) t 2 datAttr(R1ev ./ R2ev) ,? t 2 Q1 ./ Q2, (ii) 8t 2 Q1 ./ Q2 : W gen( 1pa t^2R1ev./R2ev; t^[datAttr]=t 2pa; t^) ? datAttr2 (R2ev) I,A t1 2 Q1 ^ t2 2 Q2 ^ jc(t1; t2) = true , t1 t2 2 Q1 ./jc Q2 , t 2 Q1 ./ Q2 X (Verbundbed. jc(t1; t2) (nat. Verbund) bezieht sich nur auf Datenattributen, da durch Konstruktion stets gilt evAttr1 \ evAttr2 = ;) (ii) 8t 2 Q1 ./ Q2 : W gen( 1pa t^2R1ev./R2ev; t^[datAttr]=t W gen( 1pa 2pa; t1 t2) = 2pa; t^) = gen( 1pa; t1) ^ gen( 2pa; t2) =

W t12R1ev; t1[datAttr1]=t gen( 1pa; t1)^W

t22R2ev; t2[datAttr2]=t

gen( 2pa; t2) I=A t1 ^ t2 X (da (t1 t2)[datAttr] = t ) jc(t1 t2) = true; konkatenierte Muster (erzeugt durch ) drucken Konjunktion aus und ipa enthalt nur Basisereignismuster von ti) Operator: Q

Q1 [ Q2, d.h. zu zeigen (i) t 2 datAttr(R1ev ./fo R2ev) ,? t 2 Q1 [ Q2, (ii) 8t 2 Q1 [ Q2 : W gen( 1pa [ 2pa; t^) ? t^2R1ev./foR2ev;

t^[datAttr]=t

Beweis:

(i) t 2 datAttr(R1ev ./fo R2ev) ) t 2 datAttr1 (R1ev) _ t 2

IA datAttr2 (R2ev) , t 2 Q1 _ t2 2 Q2 , t 2 Q1 [ Q2 (wegen der Def. eines vollen au eren Verbundes und datAttr = datAttr1 = datAttr2) (ii) 8t 2 Q1 [ Q2 : W gen( 1pa [ 2pa; t^) = t^2R1ev./foR2ev;

t^[datAttr]=t

W gen( 1pa; t^) _ gen( 2pa; t^) = t^2R1ev_t^2R2ev; t^[datAttr]=t

W gen( 1pa; t^) _ W gen( 2pa; t^) I=A t1 _ t2 X t^2R1ev; t^2R2ev; t^[datAttr]=t t^[datAttr]=t (wegen der Def. eines vollen au eren Verbundes und da pa eine disjunktiv verknupfte Klauselkombination beschreibt)

B. REFERENCES

References

[1] L. Antova , T. Jansen , C. Koch , and D. Olteanu . Fast and simple relational processing of uncertain data . In ICDE , pages 983 { 992 , 2008 .

[2] D. Barbara , H. Garcia-Molina , and D. Porter . The management of probabilistic data . IEEE Trans. on Knowl. and Data Eng ., 4 : 487 { 502 , October 1992 .

[3] R. Fink , D. Olteanu , and S. Rath . Providing support for full relational algebra in probabilistic databases . In ICDE , pages 315 { 326 , 2011 .

[4] N. Fuhr and T. Roelleke . A probabilistic relational algebra for the integration of information retrieval and database systems . ACM Trans. IS , 15 ( 1 ): 32 { 66 , 1997 .

[5] F. Henze , H. Lehmann , and W. Langer. CISAR - A Modular Database System as a Basis for Analysis and Documentation of Spatial Information . In CAA, pages 228 { 233 , 2007 .

[6] R. M. Karp , M. Luby , and N. Madras . Monte-carlo approximation algorithms for enumeration problems . Journal of Algorithms , 10 ( 3 ): 429 { 448 , 1989 .

[7] C. Koch . MayBMS: A System for Managing Large Uncertain and Probabilistic Databases . In Managing and Mining Uncertain Data, ch. 6 . Springer-Verlag, 2008 .

[8] S. Lehrack , S. Saretz , and I. Schmitt. QSQL2: Query Language Support for Logic-Based Similarity Conditions on Probabilistic Databases . In RCIS , 2012 (to appear).

[9] S. Lehrack and I. Schmitt. QSQL: Incorporating Logic-Based Retrieval Conditions into SQL . In DASFAA , pages 429 { 443 , 2010 .

[10] S. Lehrack and I. Schmitt . A Probabilistic Interpretation for a Geometric Similarity Measure . In ECSQARU , pages 749 { 760 , 2011 .

[11] S. Lehrack and I. Schmitt. A Unifying Probability Measure for Logic-Based Similarity Conditions on Uncertain Relational Data . In NTSS , pages 14 { 19 , 2011 .

[12] D. Olteanu , J. Huang , and C. Koch . Approximate con dence computation in probabilistic databases . In ICDE , pages 145 { 156 , 2010 .

[13] D. Olteanu and H. Wen . Ranking Query Answers in Probabilistic Databases: Complexity and E cient Algorithms . In ICDE, 2012 (to appear).

[14] C. Re and D. Suciu . Approximate lineage for probabilistic databases . PVLDB , 1 ( 1 ): 797 { 808 , 2008 .

[15] C. Re and D. Suciu . Managing Probabilistic Data with MystiQ: The Can-Do, the Could-Do, and the Can't-Do . In SUM , pages 5 { 18 , 2008 .

[16] A. D. Sarma , O. Benjelloun , A. Y. Halevy , and J. Widom . Working models for uncertain data . In ICDE, page 7 , 2006 .

[17] F. Schaefer and A. Schulze. OpenInfRA { Storing and retrieving information in a heterogenous documentation system . In CAA , 2012 (to appear).

[18] D. Suciu , D. Olteanu , C. Re, and C. Koch . Probabilistic Databases. Synthesis Lectures on Data Management . Morgan & Claypool Publishers, 2011 .

[19] J. Widom . Trio: A system for data, uncertainty, and lineage . In Managing and Mining Uncertain Data , pages 113 { 148 . Springer, 2008 .