ppt - Institut für Informationssysteme

 Documents

 42 views
of 37
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
Non-Standard-Datenbanken First-n- und Top-k-Anfragen Prof. Dr. Ralf Möller Universität zu Lübeck Institut für Informationssysteme Non-Standard-Datenbanken…
Share
Transcript
Non-Standard-Datenbanken First-n- und Top-k-Anfragen Prof. Dr. Ralf Möller Universität zu Lübeck Institut für Informationssysteme Non-Standard-Datenbanken First-n und Top-k-Anfragen Anwendungen First-n-Anfragen Optimierung Schlussakkord Top-k-Anfragen Fagins Algorithmus Danksagung an Felix Naumann für Material aus VL Informationsintegration, WS 05/06 Beispiel SELECT h.name, h.adresse, h.tel FROM hotels h, flughäfen f WHERE f.name = ‚LBC‘ ORDER BY distance(h.ort, f.ort) 20.000 1.000 1 • Naive Auswertung: 20.000 Hotels mit aufsteigender Entfernung zu LBC • Zur Sortierung: mind. 20.000 Mal distance() ausführen M.J. Carey, Donald Kossmann: On Saying "Enough Already!" in SQL. SIGMOD Conference: 219-230, 1997 3 Problem • Was machen wir, wenn nur 5 Hotels gezeigt werden sollen? – Auswahl im Anwendungsprogramm • Großer Aufwand Eventuell werden sehr viele Daten kommuniziert – Auswahl durch Programmiersprache auf Seiten der DB angewendet auf Anfrageergebnis • Keine Optimierung – Gewünschte Anzahl in Anfrage spezifizieren • Optimierungsmöglichkeiten 4 STOP AFTER – Syntax Projektion Relationen Selektion und Join- Bedingungen SELECT ... FROM ... WHERE ... GROUP BY ... HAVING ... ORDER BY ... STOP AFTER ... Gruppierung Sortierung Selektion nach Gruppierung Neu: Beschränkung der Ergebniskardinalität M.J. Carey, Donald Kossmann: On Saying "Enough Already!" in SQL. SIGMOD Conference: 219-230, 1997 5 STOP AFTER – Semantik • Ohne Sortierung – Willkürlich n Tupel aus dem SQL-Ergebnis • Mit Sortierung – Erste n Tupel aus dem SQL-Ergebnis (sortiert) – Bei Gleichheit bzgl. des Sortierprädikats willkürliche Auswahl falls n+1-tes Tupel usw. gleich n-tem Tupel • Daraus folgt: Falls Ergebnis nur bis zu n Tupel  keine Wirkung 6 STOP AFTER – Beispiel SELECT h.name, h.adresse, h.tel FROM hotels h, flughäfen f WHERE f.name = ‚LBC‘ ORDER BY distance(h.ort, f.ort) STOP AFTER 5 • Ergebnis: 5 Hotels mit aufsteigender Entfernung zu LBC • Können wir Indexstrukturen für distance() nutzen? 7 STOP-AFTER: Berechnete Anzahl • Liste Name und Umsatz der 10% umsatzstärksten Softwareprodukte SELECT p.name, v.umsatz FROM Produkte p, Verkäufe V WHERE p.typ = ‚software‘ AND p.id = v.prod_id ORDER BY v.umsatz DESC STOP AFTER ( )8 Praktische Ausprägung in PostgreSQL 9.3 SELECT ... FROM ... ... LIMIT { count | ALL } OFFSET start •Verwendung in Kombination mit ORDER-BY möglich und sinnvoll •Falls der Ausdruck count sich zu NULL evaluiert, wird ALL angenommen. •Falls der Ausdruck start sich zu NULL evaluiert, wird 0 angenommen. 9 Non-Standard-Datenbanken First-n und Top-k-Anfragen Anwendungen First-n-Anfragen Optimierung Schlussakkord Top-k-Anfragen Fagins Algorithmus Danksagung an Felix Naumann für Material aus VL Informationsintegration, WS 05/06 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“ 11 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. • Operatoren, die Tupel filtern, müssen also früher ausgeführt werden. 12 STOP AFTER: Optimierung SELECT * FROM mitarbeiter m, abteilung a WHERE m.abt_id = a.id ORDER BY m.gehalt DESC STOP AFTER 10 • Wie würden Sie den Anfragebeantwortungsplan gestalten? • Unter welchen Bedinungen ist eine Optimierung möglich? 13 Optimierung mit Stop-Operator SELECT * FROM mitarbeiter m, abteilung a WHERE m.abt_id = a.id ORDER BY m.gehalt DESC STOP AFTER 10 Stop(10) sortStop ⋈m.abt_id = a.id m.abt_id NOT NULL Unter welchen m.abt_id ist Fremdschlüssel Bedingungen? Stop(10) ⋈m.abt_id = a.id sortStop Mitarbeiter m Abteilung a Mitarbeiter m Abteilung a 14 Optimierung mit Stop-Operator SELECT * FROM mitarbeiter m, abteilung a WHERE m.abt_id = a.id AND a.name = ‚Verkauf‘ ORDER BY m.gehalt DESC STOP AFTER 10 Stop(10) sortStop ⋈m.abt_id = a.id Nein! Erlaubt? ⋈m.abt_id = a.id Stop(10) sortStop a.Name = ‚Verkauf‘ a.Name = ‚Verkauf‘ Mitarbeiter m Abteilung a Mitarbeiter m Abteilung a 15 Optimierung mit Stop-Operator (aggressiv) SELECT * FROM mitarbeiter m, abteilung a, reisen r Stop(10) WHERE m.abt_id = a.id AND r.konto = m.reisekonto ⋈m.abt_id = a.id ORDER BY m.gehalt DESC STOP AFTER 10 Restart Abteilung a ⋈m.rkonto = r.konto Stop(20) Reise r sortStop Mitarbeiter m 16 Non-Standard-Datenbanken First-n und Top-k-Anfragen Anwendungen First-n-Anfragen Optimierung Schlussakkord Top-k-Anfragen Fagins Algorithmus Danksagung an Felix Naumann für Material aus VL Informationsintegration, WS 05/06 Top-k Ergebnisse: Motivation • First-n beschränkt Ergebnismenge bzgl. eines Attributs – Bei Verwendung mehrerer Attribute (Sekundärschlüssel) bleibt erstes Attribut dominant • Top-k beschränkt Ergebnismenge bzgl. mehrerer Attribute – Sortierung nach einem (komplexen) Maß – Maße sind oft unscharf – Maße haben oft mehrere gleichberechtigte Attribute als Input 18 Top-k in Multimedia DBMS • Beatles „Red Album“ Als Standard-Prädikat • Anfrage: Antwort ist (unsortierte) Menge – Farbe = ‚rot‘  Name = ‚Beatles‘ Als unscharfes Prädikat: Antwort ist sortierte Liste 19 Top-k: 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] 20 Top-k: 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 • gAA(x) = gA(x) • gA(B C)(x) = g(AB)  (A  C)(x) – Monotonie: gA(x)  gA(y), gB(x)  gB(y)  gAB(x)  gA B(y) 21 Top-k: Benotete Mengen • Vorschlag – Konjunktionsregel: • gAB(x) = min{gA(x), gB(x)} – Disjunktionsregel: • gAB(x) = max{gA(x), gB(x)} Lotfi A. Zadeh: Fuzzy Sets. Information and Control 8(3): 338-353, 1965 22 Top-k: Benotete Mengen • gAB(x) = min{gA(x), gB(x)}, gAB(x) = max{gA(x), gB(x)} • Standardlogik (g  {0,1}) – 0  1 = min{0,1} = 0 – 0  1 = max{0,1} = 1 • Äquivalenz – gAA(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(AB)  (A  C)(x) • Monotonie – gA(x)  gA(y), gB(x)  gB(y)  gAB(x)  gA B(y) – gA(x)  gA(y), gB(x)  gB(y)  min{gA(x), gB(x)}  min{gA(y), gB(y)} 23 Anfragebeantwortung • Gegeben: Konjunktive Anfrage mit teilweise unscharfen Prädikaten. • Gesucht: Benotete Menge, so dass k beste Elemente identifiziert werden können • Zugriffsmodell auf MMDBMS – Sorted access: Cursor auf sortierte Liste – Random access: Note eines bestimmten Objekts • Kostenmodell: – Jedes angefragte Objekt kostet 1 • Optimierung: – Minimiere Kosten 24 Top-k: Beispiel • Anfrage: – Name = ‚Beatles‘  Farbe = ‚rot‘ G = min{1,gFarbe = ‚rot‘(x)} ⋈s.id = p.id random access Name = ‚Beatles‘ Kosten? DBMS MMDBMS Schallplatten Plattencover 25 Top-k: 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 Ronald Fagin. Combining Fuzzy Information from Multiple Systems. PODS-96, 216-226., 1996 Ronald Fagin: Fuzzy Queries in Multimedia Database Systems. Proc. PODS-98, 1-10, 1998 26 Top-k: 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. ⋈id ... MMDBMS_1 MMDBMS_2 MMDBMS_m 27 Top-k: Fagins Algorithmus Objekte aus MMDBMS_2 Objekte aus mit gA2(x) MMDBMS_1 mit gA1(x) k k Objekte aus allen Objekte aus MMDBMS mit MMDBMS_2 allen gAi(x) und also auch mit MMDBMS_ Gesamt-Note m mit gA2(x) und gAm(x) ... MMDBMS_1 MMDBMS_2 MMDBMS_m 28 Top-k: Fagins Algorithmus Der Clou: Unter Wichtig: Dies allen gesehenen sind nicht Objekten befinden unbedingt die sich auch die Top-k Top-k Objekte! Objekte. Beweis später. k ... MMDBMS_1 MMDBMS_2 MMDBMS_m 29 Top-k: Fagins Algorithmus • Phase 2: Random access Ergebnis: Nun – Hole alle unbekannten gAi(x) ein. kennen wir alle Noten aller gesehenen Objekte. k ... MMDBMS_1 MMDBMS_2 MMDBMS_m 30 Top-k: 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 k Objekte. – Ausgabe dieser Top-k Objekte. 31 Fagins Algorithmus – Beispiel • Anfrage: – Form = ‚rund‘  Farbe = ‚rot‘  Stil = ‚Modern‘ – k=2 MMDBMS_1 MMDBMS_2 MMDBMS_3 ID Form Rundheit ID Stil Modernität ID Farbe Rotheit 1 oval 0.8 3 modern 1 3 rot 1 2 achteck 0.6 2 rock 0.7 2 orange 0.5 3 viereck 0.15 4 barock 0.2 1 gelb 0.3 4 dreieck 0.1 1 keltisch 0.1 4 blau 0.01 5 strich 0 5 uralt 0.01 5 grün 0 32 Fagins Algorithmus – Beispiel 4:(??; 0.2; ??) 4 3:(0.15; 1; 1) 3 1 2 2:(0.6; 0.7; 0.5) 1:(0.8; ??; 0.3) ID Form Rundheit ID Stil Modernität ID Farbe Rotheit 1 oval 0.8 3 modern 1 3 rot 1 2 achteck 0.6 2 rock 0.7 2 orange 0.5 3 viereck 0.15 4 barock 0.3 1 gelb 0.3 4 dreieck 0.1 1 keltisch 0.2 4 blau 0.01 33 5 strich 0 5 uralt 0.01 5 grün 0 Top-k: 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-k 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: Wichtig: Wir können gA1  A2  ...  Am(y)  gA1  A2  ...  Am(x). dies nicht für andere – Es gibt mindestens k solcher Objekte x gesehene Objekte (Abbruch-Kriterium Phase 1). zeigen. – Schlussfolgerung: Es gibt kein y, das besser ist als die besten N x. 34 Top-k: Fagins Algorithmus • Aufwand: O(n(m-1)/mk1/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 Ronald Fagin. Combining Fuzzy Information from Multiple Systems. PODS-96, 216-226., 1996 35 Top-k-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 • In der Literatur verfolgter Ansatz: Wandele Top-k-Anfragen in herkömmliche Anfragen um Surajit Chaudhuri, Luis Gravano: Evaluating Top-k Selection Queries. VLDB 1999: 397-410, 1999 36 Non-Standard-Datenbanken First-n und Top-k-Anfragen Anwendungen First-n-Anfragen Optimierung Schlussakkord Top-k-Anfragen Fagins Algorithmus Danksagung an Felix Naumann für Material aus VL Informationsintegration, WS 05/06
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks