Informationsintegration
Top-N Anfragen
13.12.2005
Felix Naumann
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 2
Überblick
Anfragen nach den ERSTEN Ergebnissen (First-N) “Es reicht!“ in SQL [CK97]
Syntax und Semantik Optimierung
Anfragen nach den BESTEN Ergebnissen (Top-N) Motivation Fagin‘s Algorithm
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 3
Motivation für First-N 1. Anfragen
Semantik: Korrektheit Vollständigkeit D.h. alle Ergebnisse erwünscht
Bsp.: Aggregation Anwendungen:
DBMS Data Warehouses
2. Browsen Semantik:
So korrekt wie möglich So vollständig wie gewünscht D.h. einige, bespielhafte
Ergebnisse Bsp: Life Sciences Anwendungen
GUI
3. Suchen Semantik
So korrekt wie möglich Nur die besten Ergebnisse D.h. Ein oder wenige passende
Ergebnisse Bsp: Dokumente Anwendungen:
Digital Library Systeme Content Management Systeme Google
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 4
Informationsintegration und Browsen Warum sind First-N Techniken für die Informationsintegration
interessant? Für Nutzer
Art der Daten unbekannt Umfang der Daten unbekannt Browsen Nutzen/Qualität der Daten sowieso zweifelhaft Anfragen nur fuzzy formuliert Verfeinerung der Anfrage in weiteren Schritten
Query refinement Für System
Datenbeschaffung oft langsam und teuer Deshalb: Großes Optimierungspotential
Lokale Optimierung Globale Optimierung: Netzwerkkosten
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 5
Anfragebearbeitung in DBMS
1. SQL Anfrage formulieren2. System nimmt SQL Anfrage entgegen
1. Parsen2. Optimieren
3. System führt Anfrage aus1. Tupel-pipeline aufbauen2. Ergebnistupel in temporäre Tabelle schreiben
4. Rückgabe eines Cursors auf erstes Ergebnistupel5. Sukzessives next() auf Cursor durch Anwendung
1. GUI (z.B. AquaDataStudio)2. Programm (z.B. mittels JDBC)
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 6
Anfragebearbeitung in DBMS
Problem DBMS berechnet vollständiges Ergebnis Anwendung holt eventuell nur wenige Tupel
z.B. ein Fenster voll z.B. Top-N Ergebnisse entsprechend einer Sortierung
Anwendung spart Aufwand, DBMS jedoch nicht!
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 7
Überblick
Anfragen nach den ERSTEN Ergebnissen (First-N) “Es reicht!“ in SQL [CK97]
Syntax und Semantik Optimierung
Anfragen nach den BESTEN Ergebnissen (Top-N) Motivation Fagin‘s Algorithm
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 8
Gruppierung
SQL
SELECT ... FROM ... WHERE ...GROUP BY ... HAVING ...ORDER BY ...
Projektion Relationen Selektion und Join-Bedingungen
Selektion nach Gruppierung
Sortierung
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 9
20.000 1.000 1
Teures SQL – Beispiel
Ergebnis: 20.000 Hotels mit aufsteigender Entfernung zu TXL
Zudem: 20.000x distance() ausführen
SELECT h.name, h.adresse, h.telFROM hotels h, flughäfen fWHERE f.name = ‚TXL‘ORDER BY distance(h.ort, f.ort)
Beispiele nach [CK97]
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 10
Neu: Beschränkung der Ergebniskardinalität
Gruppierung Sortierung
STOP AFTER – Syntax
SELECT ... FROM ... WHERE ...GROUP BY ... HAVING ...ORDER BY ...STOP AFTER ...
Projektion Relationen Selektion und Join-Bedingungen
Selektion nach Gruppierung
STOP AFTER nach [CK97]Wichtig: Nicht SQL Standard!
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 11
STOP AFTER – Semantik
Semantik:1. Führe sämtliches Standard-SQL in der Anfrage aus.2. Beschränke Ergebnis auf erste Tupel.
Keine Sortierung Genaue Ergebnismenge nicht spezifiziert
Sortierung Genaue Ergebnismenge spezifiziert, außer bei Duplikaten in Sortierungsattributen: Genaue
Ergebnismenge nicht spezifiziert Weniger als N Tupel im Ergebnis: Kein Einfluss
durch STOP AFTER
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 12
STOP AFTER – Beispiel
Ergebnis: 5 Hotels mit aufsteigender Entfernung zu TXL
Einsparungen bei distance()?
SELECT h.name, h.adresse, h.telFROM hotels h, flughäfen fWHERE f.name = ‚TXL‘ORDER BY distance(h.ort, f.ort)STOP AFTER 5
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 13
STOP AFTER – Beispiel
SELECT p.name, v.umsatzFROM Produkte p, Verkäufe VWHERE p.typ = ‚software‘AND p.id = v.prod_idORDER BY v.umsatz DESCSTOP AFTER ( SELECT count(*)/10
FROM Produkte p WHERE p.typ = ‚software‘)
Liste Name und Umsatz der 10% umsatzstärksten Softwareprodukte.
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 14
STOP AFTER – Updates
UPDATE SpielerSET Gehalt = 0.5 * GehaltWHERE id IN ( SELECT s.id FROM Spieler s ORDER BY s.tore
STOP AFTER 3 )
Hertha BSC: - Kürze die Gehälter der 3 schlechtesten Spieler um 50%.
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 15
STOP AFTER – Implementierung Implementierung in der Anwendung
Keine Veränderung des DBMS Optimierungspotential nicht ausgeschöpft
Implementierung in DBMS als äußere Schicht Einsparungen bei Datenübertragung Optimierungspotential nicht voll ausgeschöpft
Implementierung im DBMS Kern Volles Optimierungspotential Schwieriger
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 16
Rückblick: Anfrageoptimierung
Umwandlung von SQL in interne Repräsentation Interne Operatoren
Scan, Sort, Select, Project,...
Interpretation als Baum Transformationsschritte im Baum Wahl des Schrittes gemäß Kostenmodell
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 17
Rückblick: Anfragebearbeitung
SELECT m.nameFROM mitarbeiter m, abteilung aWHERE m.abt_id = a.idAND a.name = ‚Verkauf‘ORDER BY m.gehalt
m.name(sortm.gehalt(m.abt_id = a.id, a.name = ‚Verkauf‘ (m x a)))
In Worten?
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 18
Einsparung
Rückblick: Anfragebearbeitung
m.name(sortm.gehalt(m.abt_id = a.id, a.name = ‚Verkauf‘ (m x a)))
Mitarbeiter m Abteilung a
X
m.abt_id = a.id
a.Name = ‚Verkauf‘
Sort(m.gehalt)
(m.name)
[1.000] [100]
[100.000]
[990]
[20]
Mitarbeiter m Abteilung a
a.Name = ‚Verkauf‘
Sort(m.gehalt)
(m.name)
[1.000] [100]
[990]
[20]
⋈m.abt_id = a.id
[20]
[20]
[20]
[20]
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 19
Rückblick: Anfragebearbeitung
Mitarbeiter m Abteilung a
a.Name = ‚Verkauf‘
Sort(m.gehalt)
(m.name)
[1.000] [100]
[990]
[20]
⋈m.abt_id = a.id
Mitarbeiter m Abteilung a
a.Name = ‚Verkauf‘
Sort(m.gehalt)
(m.name)
[1.000] [100]
[5]
[20]⋈m.abt_id = a.id
[20]
[20]
[20]
[20]
?
Einsparung
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 20
Neuer Operator
Logischer Operator Stop(N, Sortierungsrichtung, Sortierungsausdruck)
N: maximale Ergebnisgroesse Sortierungsrichtung: asc, desc, none Sortierungsausdruck: meist wie ORDER BY
Physikalische Operatoren Implementierungsvarianten des logischen Operators
1. Scan-Stop
2. Sort-StopJetzt!
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 21
Scan-Stop
Falls Sortierungsrichtung = ‚none‘ Schließt Input-Strom nach N Tupeln Kostenmodell
p = Plan unterhalb (im Baum) Stop Operator s = Plan inkl. Stop Operator Cost(1) = Kosten für erstes Tupel (Latenz, latency) Costp(ALL) = Kosten für alle Tupel von p
ALL
NCostALLCostCostNCost ppps
1))1()(()1()(
Pipelines werden bevorzugt! Warum?
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 22
Sort-Stop
Falls Sortierungsrichtung = ‚asc/desc‘ Falls schon entsprechend sortiert: Schließt Input-
Strom nach N Tupeln Kosten wie Scan-Stop
Sonst sortieren: Erste N Tupel in priority-heap (Haufen) Nächste Tupel gegen Heap testen
)log()()()( NiCNALLALLCostNCost ps
Input-Strom komplett erzeugen
Test gegen Heap-Grenzen
i Einfügungen in Heap
N i ALL
Kosten eines Vergleichs
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 23
Überblick
Anfragen nach den ERSTEN Ergebnissen (First-N) “Es reicht!“ in SQL [CK97]
Syntax und Semantik Optimierung
Anfragen nach den BESTEN Ergebnissen (Top-N) Motivation Fagin‘s Algorithm
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 24
Optimierung mit Stop-Operator
Platzierung des Stop Operators im Anfrageplan
Fundamentales Problem: Frühe Platzierung vorteilhaft aber risikoreich Vorteil: Kleine Zwischenergebnisse geringe
Kosten Risiko: Endergebnis nicht groß genug Erneute
Ausführung Zwei Strategien
„Konservativ“ und „aggressiv“
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 25
Optimierung mit Stop-Operator
Konservative Strategie Kostenminimal: Platziere Stop so früh wie möglich
in Plan. Korrekt: Platziere Stop nie so, dass Tupel entfernt
werden, die später eventuell gebraucht werden. D.h.: Wende Stop nur auf Input-Ströme an, deren
Input-Tupel jeweils mindestens ein Output-Tupel erzeugen. Operatoren, die Tupel filtern, müssen also früher
ausgeführt werden.
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 26
Optimierung mit Stop-Operator
SELECT *FROM mitarbeiter m, abteilung aWHERE m.abt_id = a.idORDER BY m.gehalt DESCSTOP AFTER 10
Mitarbeiter m Abteilung a
Stop(10)sortStop
⋈m.abt_id = a.id
Mitarbeiter m Abteilung a
Stop(10)sortStop
⋈m.abt_id = a.idm.abt_id NOT NULLm.abt_id ist FremdschlüsselUnter welchenBedingungen?
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 27
Nein!
Optimierung mit Stop-OperatorSELECT *FROM mitarbeiter m, abteilung aWHERE m.abt_id = a.idAND a.name = ‚Verkauf‘ORDER BY m.gehalt DESCSTOP AFTER 10
Mitarbeiter m Abteilung a
Stop(10)sortStop
⋈m.abt_id = a.id
Mitarbeiter m Abteilung a
Stop(10)sortStop
⋈m.abt_id = a.id
Erlaubt?
a.Name = ‚Verkauf‘ a.Name = ‚Verkauf‘
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 28
Optimierung mit Stop-Operator
Aggressive Strategie Platziere Stop so früh wie möglich in Plan. Wähle (hoffentlich) hinreichend großes N:
Füge „Reserve“ hinzu (z.B. 20%). Platziere weiteres, endgültiges Stop(N) später im Plan. Platziere geeignete „Restart“ Operatoren.
NALL
ALLN subplanstop
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 29
Optimierung mit Stop-Operator
SELECT *FROM mitarbeiter m,
abteilung a, reisen rWHERE m.abt_id = a.idAND r.konto = m.reisekontoORDER BY m.gehalt DESCSTOP AFTER 10
Mitarbeiter m
Abteilung a
⋈m.rkonto = r.konto
Restart
Reise rStop(20)sortStop
⋈m.abt_id = a.id
Stop(10)
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 30
Implementierungen von First N SQL:
select name, salary from employee A where 50 > (select count(*) from employee B
where B.salary > A.salary) ...WHERE rownum < N
MySQL: SELECT ...FROM ... LIMIT 10
DB2: FETCH FIRST N ROWS ONLY OPTIMIZE FOR N ROWS
MS SQL Server SELECT TOP N ... FROM ...
Oracle: OPTIMIZER_MODE = FIRST_ROWS_N
Optimierung jeweils unklar! Weitere Optimierung („Bremsweg verkleinern“) z.B. in [CK98]
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 31
Überblick
Anfragen nach den ERSTEN Ergebnissen (First-N) “Es reicht!“ in SQL [CK97]
Syntax und Semantik Optimierung
Anfragen nach den BESTEN Ergebnissen (Top-N) Motivation Fagin‘s Algorithm
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 32
Anfragen nach den Top-N Ergebnissen – Motivation
First-N beschränkt Ergebnismenge aber nicht (unbedingt) Eigenschaften des Ergebnisses Ausnahme: Sortierung auf einem Attribut
Top-N beschränkt Ergebnismenge und Eigenschaften Sortierung nach einem (beliebigen) Maß Maße sind oft fuzzy. Maße haben oft mehrere Attribute als Input.
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 33
Anfragen nach den Top-N Ergebnissen – Beispiele
Suchmaschinen Maß: Vorkommen des Suchworts & „authority“
Information Retrieval Maß: Relevanz
In DBMS 4-Zimmer Wohnungen, unter $30,000 Bisher nicht unterstützt
In Multimedia DBMS Bilder mit roten und runden Objekten
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 34
Top-N in Multimedia DBMS Farb-Ähnlichkeit
Z.B. Anfrage: Farbe = ‚rot‘ Berechnung der „Röte“ oft komplex (viele Farbdimensionen, viele
Pixel) MMDBMS liefert top-N roteste (röteste?) Objekte
Multidimensionale Indices Form-Ähnlichkeit
Z.B. Anfrage: Form = ‚rund‘ Berechnung der „Rundheit“ oft komplex MMDBMS liefert top-N rundeste Objekte
Entspricht First-N Semantik (Maß auf einem Attribut) Aber wie kombinieren?
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 35
Top-N in Multimedia DBMS
Beatles „Red Album“ Anfrage:
Farbe = ‚rot‘ Name = ‚Beatles‘
Was als Antwort: Menge? Sortierte Liste?
Fuzzy PrädikatAntwort ist sortierte Liste
Non-Fuzzy PrädikatAntwort ist (unsortierte) Menge
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 36
Top-N in Multimedia DBMS
Anfrage: Farbe = ‚rot‘ Name =
‚Beatles‘
Antwort: Menge? Sortierte Liste?
Anfrage: Farbe = ‚rot‘ Form =
‚rund‘
Antwort: Menge? Sortierte Liste?
Idee [Fa96]: Antwort ist „benotete Menge“ („graded set“)
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 37
Top-N – benotete Mengen
Benotete Menge: Menge aus Paaren (x,g) x ist ein Objekt g [0,1] ist eine Note (grade)
Anfrage: Name = ‚Beatles‘ Antwort: benotete Menge mit g {0,1}
Anfrage: Farbe = ‚rot‘ Antwort: benotete Menge mit g [0,1]
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 38
Top-N – benotete Mengen Anfrage:
Name = ‚Beatles‘ Farbe = ‚rot‘ Name = ‚Beatles‘ Farbe = ‚rot‘
Problem: Maß: Benotung der Objekte in Antwort
Sei gA(x) die Note von Objekt x unter Anfrage A. Erwünschte Eigenschaften
Falls g {0,1} sollte Standard-Logik gelten. Bewahrung der logischen Äquivalenz
gAA(x) = gA(x) gA(B C)(x) = g(AB) (A C)(x)
Monotonie: gA(x) gA(y), gB(x) gB(y) gAB(x) gA B(y)
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 39
Top-N – benotete Mengen
Vorschlag Konjunktionsregel [Za65]:
gAB(x) = min{gA(x), gB(x)} Disjunktionsregel [Za65]:
gAB(x) = max{gA(x), gB(x)}
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 40
Top-N – benotete Mengen gAB(x) = min{gA(x), gB(x)}, gAB(x) = max{gA(x), gB(x)} Standardlogik (g {0,1})
0 1 = min{0,1} = 0 0 1 = max{0,1} = 1
Äquivalenz gAA(x)= min{gA(x), gA(x)} = gA(x) gA(B C)(x) = min{gA(x), max{gB(x), gC(x)}} = max{min{gA(x),
gB(x)}, min{gA(x), gC(x)}} = g(AB) (A C)(x) Monotonie
gA(x) gA(y), gB(x) gB(y) gAB(x) gA B(y) gA(x) gA(y), gB(x) gB(y) min{gA(x), gB(x)} min{gA(y), gB(y)}
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 41
Andere Maße?
AVG gAB(x) = avg{gA(x), gB(x)}, gAB(x) = max{gA(x), gB(x)}
0 1 = avg{0,1} = 0.5 0 1 = max{0,1} = 1
gAA(x)= avg{gA(x), gA(x)} = gA(x)
gA(B C)(x) = avg{gA(x), max{gB(x), gC(x)}} = max{avg{gA(x),
gB(x)}, avg{gA(x), gC(x)}} = g(AB) (A C)(x) gA(x) gA(y), gB(x) gB(y) avg{gA(x), gB(x)} avg{gA(y), gB(y)}
D.h. Standardlogik bleibt nicht erhalten. Name = ‚Beatles‘ Farbe = ‚rot‘ Album (Santana, Supernatural) hat score > 0 Fast jedes andere Album hat auch score > 0
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 42
Top-N – Fagin‘s Algorithmus Gegeben: Konjunktive Anfrage mit teilweise fuzzy
Prädikaten. Gesucht: Benotete Menge mit mindesten Top-N
Objekten
Zugriffsmodell auf MMDBMS Sorted access: Cursor auf sortierte Liste Random access: Note eines bestimmten Objekts
Kostenmodell: Jedes angefragte Objekt kostet 1.
Optimierung: Minimiere Kosten
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 43
Top-N – Beispiel
Anfrage: Name = ‚Beatles‘ Farbe = ‚rot‘
DBMSSchallplatten
MMDBMSPlattencover
Name = ‚Beatles‘
⋈s.id = p.id random access
G = min{1,gFarbe = ‚rot‘(x)}
Kosten?
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 44
Top-N – Naiver Algorithmus Anfrage:
Form = ‚rund‘ Farbe = ‚rot‘
1. Sorted access auf alle Objekte (mit Note für Form = ‚rund‘)2. Sorted access auf alle Objekte (mit Note für Farbe = ‚rot‘)3. Join über alle Objekte x4. Jeweils Berechnung der minimalen Note
min{grund(x),grot(x)}
5. Sortierung für Top-N
Kosten 2n (2x sorted access)
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 45
Top-N – Beispiel
Anfrage: Form = ‚rund‘ Farbe = ‚rot‘
MMDBMS_1Plattencover (Formen)
MMDBMS_2Plattencover (Farben)
⋈s.id = p.idsorted access/random accesssorted access
G = min{gForm = ‚rund‘(x),gFarbe = ‚rot‘(x)}
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 46
Überblick
Anfragen nach den ERSTEN Ergebnissen (First-N) “Es reicht!“ in SQL [CK97]
Syntax und Semantik Optimierung
Anfragen nach den BESTEN Ergebnissen (Top-N) Motivation Fagin‘s Algorithm
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 47
Top-N – Fagins Algorithmus
Allgemeineres Problem: Anfrage statt A B nun
A1 A2 ... Am
Für jedes Prädikat eine Quelle. bzw. Zugriffsmöglichkeit durch sorted und random
access
Phase 1: Sorted access Phase 2: Random access Phase 3: Berechnung und Sortierung
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 48
Top-N – Fagins Algorithmus
A1 A2 ... Am
Phase 1: Sorted access Für jedes i: Schicke Ai an Quelle i Schreite sukzessive voran, bis Join über alle
Teilergebnisse die Größe N hat.
MMDBMS_1 MMDBMS_2 MMDBMS_m
⋈id
...
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 49
Top-N – Fagins Algorithmus
MMDBMS_1 MMDBMS_2 MMDBMS_m...
N
Objekte aus MMDBMS_1
mit gA1(x)
Objekte aus MMDBMS_2
und MMDBMS_mmit gA1(x) und
gAm(x)
Objekte aus MMDBMS_2
mit gA2(x)
N Objekte aus allen
MMDBMS mit allen gAi(x)
also auch mit Gesamt-Note
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 50
Top-N – Fagins Algorithmus
MMDBMS_1 MMDBMS_2 MMDBMS_m...
N
Wichtig: Dies sind nicht unbedingt die Top-N Objekte!
Der Clou: Unter allen gesehenen Objekten befinden sich auch die Top-N Objekte.Beweis später.
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 51
Top-N – Fagins Algorithmus Phase 2: Random access
Hole alle unbekannten gAi(x) ein.
MMDBMS_1 MMDBMS_2 MMDBMS_m...
N
Ergebnis: Nun kennen wir alle Noten aller gesehenen Objekte.
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 52
Top-N – Fagins Algorithmus
Phase 3: Berechnung und Sortierung Berechne für jedes Objekt
gA1 A2 ... Am(x) = min{gA1(x), gA2(x),..., gAm(x)}
Sortiere alle Objekte nach gA1 A2 ... Am(x) Selektierte die höchsten N Objekte. Ausgabe dieser Top-N Objekte.
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 53
Fagins Algorithmus – Beispiel
Anfrage: Form = ‚rund‘ Farbe = ‚rot‘ Stil = ‚Modern‘ N = 2
ID Form Rundheit
1 oval 0.8
2 achteck 0.6
3 viereck 0.15
4 dreieck 0.1
5 strich 0
ID Farbe Rotheit
3 rot 1
2 orange 0.5
1 gelb 0.3
4 blau 0.01
5 grün 0
ID Stil Modernität
3 modern 1
2 rock 0.7
4 barock 0.2
1 keltisch 0.1
5 uralt 0.01
MMDBMS_1 MMDBMS_2 MMDBMS_3
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 54
Fagins Algorithmus – Beispiel
1
3
2
4
ID Form Rundheit
1 oval 0.8
2 achteck 0.6
3 viereck 0.15
4 dreieck 0.1
5 strich 0
ID Farbe Rotheit
3 rot 1
2 orange 0.5
1 gelb 0.3
4 blau 0.01
5 grün 0
ID Stil Modernität
3 modern 1
2 rock 0.7
4 barock 0.3
1 keltisch 0.2
5 uralt 0.01
1:(0.8; ??; 0.3)
4:(??; 0.2; ??)
2:(0.6; 0.7; 0.5)
3:(0.15; 1; 1)
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 55
Top-N – Fagins Algorithmus Korrektheit:
Fagins Algorithmus findet die Top-N Objekte gemäß gA(x). Beweis:
Idee: Wir zeigen für jedes ungesehene Objekt y, dass es nicht unter den Top-N sein kann:
Notation x: gesehene Objekte y: ungesehene Objekte
Für jedes x der Joinmenge nach Phase 1 und jedes Prädikat Ai gilt: gAi(y) gAi(x).
Wegen Monotonie von min{} gilt: gA1 A2 ... Am(y) gA1 A2 ... Am(x).
Es gibt mindesten N solcher Objekte x (Abbruch-Kriterium Phase 1).
Schlussfolgerung: Es gibt kein y, das besser ist als die besten N x.
Wichtig: Wir können dies nicht für andere gesehene Objekte zeigen.
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 56
Top-N – Fagins Algorithmus
Aufwand: O(n(m-1)/mN1/m) (Beweis: siehe [Fa96]) n = DB-Größe; m = Anzahl der DBs
Beispiel: 10000 Objekte, 3 Prädikate, Top 10 10.0002/3 x 101/3 = 1.000
Gilt falls Ai unabhängig. Gilt mit beliebig hoher Wahrscheinlichkeit.
D.h.: Für jedes ε>0 c, so dass die Wahrscheinlichkeit dass der Aufwand höher ist als angegeben < ε ist.
Zum Vergleich: Naiver Algorithmus in O(nm) Im Beispiel: 10.000 x 3 = 30.000
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 57
Fagins Algorithmus in der Praxis
Probleme aus [WHTB99] Monotonie
Vorgabe einer festen Menge (monotoner) Maße oder Nutzerimplementation erlauben?
WHERE Klausel oder ORDER BY Klausel Charakter des Algorithmus
Join über mehrere Quellen Objektidentifikation
Kostenmodell schwierig
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 58
Top-N Anfragen – Herausforderungen
Beliebige Maße Je nach Nutzer bzw. Anwendung
Effiziente Ausführung in bestehenden DBMS Unter Ausnutzung vorhandener Datenstrukturen und
Metadaten Korrektheit und Vollständigkeit
Idee: Wandele Top-N Anfragen in herkömmliche Anfragen um [CG99].
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 59
Rückblick
First-N Syntax und Semantik Optimierung
Top-N Motivation Fagins Algorithmus
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 60
Informationsintegration
13.12.2005 Felix Naumann, VL Informationsintegration, WS 05/06 61
Literatur First-N
[CK97] Michael J. Carey, Donald Kossmann: On Saying "Enough Already!" in SQL. SIGMOD Conference 1997: 219-230
[CK98] Michael J. Carey, Donald Kossmann: Reducing the Braking Distance of an SQL Query Engine. VLDB 1998: 158-169
Top-N [Fa98] Ronald Fagin: Fuzzy Queries in Multimedia Database Systems. PODS 1998: 1-
10 Weitere
[CG99] Surajit Chaudhuri, Luis Gravano: Evaluating Top-k Selection Queries. VLDB 1999: 397-410
[DR99] Donko Donjerkovic, Raghu Ramakrishnan: Probabilistic Optimization of Top N Queries. VLDB 1999: 411-422
[Za65] Lotfi A. Zadeh: Fuzzy Sets. Information and Control 8(3): 338-353 (1965) [DP84] D, Dubois and H. Prade, Criteria Aggregation and Ranking of Alternatives in
the Framework of Fuzzy Set Theory, in Fuzzy Sets and Decision Analysis, TIMS Studies in Management Sciences 20 (1984), pp. 209-240.
[WHTB99] Edward L. Wimmers, Laura M. Haas, Mary Tork Roth, Christoph Braendli: Using Fagin's Algorithm for Merging Ranked Results in Multimedia Middleware. CoopIS 1999: 267-278