Seminar „Benutzerzentrierte Datenbankanfragen“

Information
Classification: 
Master Informatik, Master Wirtschaftsinformatik
Credits: 
4
Exam: 
Vortrag, aktive Beteiligung, Anwesenheit
Regular Dates: 
donnerstags, 16.45–18.15 Uhr, ab 30. Oktober 2008 – Raum IZ 251
Contents
Contents: 

Immer mehr Menschen greifen im täglichen Leben auf in Datenbanksystemen gespeicherte stark strukturierte Informationen zu, typische Beispiele sind Onlineshops und Preisvergleichsdienste. Die Interaktion mit derartigen Systemen erfolgt in der Regel mittels klassischer Anfragesprachen wie SQL oder davon abgeleiteter Benutzerschnittstellen. Diese Form der Anfragestellung über harte Suchkriterien ist jedoch für viele praktische Anwendungen ungeeignet. Häufig sind sich Benutzer ihrer Wünsche unsicher, werden vom System aber zu klaren und expliziten Suchanfragen gezwungen. Ein weiteres typisches Problem ist fehlendes Hintergrundwissen über die gespeicherten Daten. Ohne derartiges Wissen ist es nur schwer möglich, sinnvolle Anfragen zu formulieren oder die Qualität von Anfrageergebnissen zu beurteilen.

Seit einigen Jahren wird an neuartigen Anfragesprachen gearbeitet, die eine Brücke zwischen Anwendern und Datenbanksystemen schlagen sollen. Um derartige Anfragesprachen und zugehörige Auswertungsmethoden geht es in diesem Seminar.

Summary: 

Jeder Seminarteilnehmer bearbeitet eines der unten aufgeführten Themen anhand von Originalliteratur. Jedes dieser Themen beleuchtet einen anderen Aspekt benutzerzentrierter Datenbankanfragen. Im Rahmen des Seminars stellt jeder Teilnehmer in einem wissenschaftlichen Vortrag das gewählte Seminarthemas vor. Das Seminar findet in der Regel wöchentlich statt, an jedem Termin trägt genau ein Teilnehmer vor. Dieser Vortrag stellt die dem Seminar zugeordnete Prüfungsleistung dar.

Für eine erfolgreiche Teilnahme ist zudem eine Mindestanwesenheit erforderlich. Jeder Teilnehmer darf höchstens einen Seminartermin versäumen, zwischen entschuldigtem und unentschuldigtem Fernbleiben wird dabei nicht unterschieden.

Jeder Vortrag dauert zwischen 30 und 45 Minuten. Im Anschluss erhält der Vortragende von den übrigen Seminarteilnehmern Rückmeldung zu seiner Vortragsweise. Das Ziel ist es, auf diese Weise den eigenen Vortragsstil zu verbessern.

Achten Sie bei Ihrem Vortrag insbesondere auf sachliche Richtigkeit, nachvollziehbare Erklärungen, inhaltliche Struktur und die Einordnung der vorgestellten Ergebnisse in den Kontext des Seminarthemas. Wichtiger als Vollständigkeit ist dabei Verständlichkeit! Bitte geben Sie sich größte Mühe, alle Sachverhalte klar und verständlich zu präsentieren. Lange technische Beweise und komplizierte Algorithmen gehören nicht in einen Seminarvortrag. Nutzen Sie die zur Verfügung stehenden Medien in angemessener Weise.

Am ersten Seminartermin findet eine kurze Einführung in Rhetorik und Präsentationstechnik statt, in der Grundregeln und typische Fehler thematisiert werden.

Für eine erfolgreiche Teilnahme ist zusätzlich folgendes zu beachten: Es ist eine Gliederung des Vortrags anzufertigen, die spätestens zwei Wochen vor dem Vortrag mit dem Betreuer zu besprechen ist.

Materials

Termine

  Datum Inhalt/Thema Folien
1 30.10.2008 Vorbesprechung, Organisatorisches  
2 6.11.2008 Wie halte ich einen guten Vortrag? Checkliste
3 4.12.2008 Anna-Lena Berndt: Präferenzgestütztes Datenbank-Retrieval I Folien
4 11.12.2008 Axel Schön: Präferenzgestütztes Datenbank-Retrieval II Folien
5 18.12.2008 ENTFÄLLT  
6 8.1.2008 Marco Gahlich: Top-k-Retrieval I  
7 15.1.2008 ENTFÄLLT  
8 22.1.2008 Stefanie Breske: Top-k-Retrieval IV Folien
9 29.1.2008 Stefan Hansmann: Skylines I Folien
10 5.2.2008 Timo Schulz: Skylines II  
11 12.2.2008 Christian Nieke: Skylines III Folien

Themen

Das Seminar gliedert sich in drei Teile. Zunächst werfen wir einen Blick auf verschiedene Ansätze zur Erweiterung relationaler Datenbanken um Präferenzanfragen. Hierbei handelt es sich um Anfragen, bei denen der Benutzer nicht über harte logische Kriterien spezifiziert, welche Datensätze er zurückgeliefert bekommen möchte. Stattdessen wird angegeben, welche Eigenschaften von Datensätzen „besser“ und welche „schlechter“ sind. Auf diese Weise ist es möglich, dem System graduelle Informationen über die Qualität von Datensätzen zu vermitteln.

Zwei besonders populäre Anfrageparadigmen sind dabei sogenannte Top-k-Anfragen und Skyline-Anfragen. Bei Top-k-Anfragen wird dem System eine reellwertige Funktion übergeben, die jedem Datensatz abhängig von seinen Attributen eine Punktzahl zuordnet. Diese Punktzahl entspricht der Qualität des jeweiligen Datensatz. Zudem wird dem System eine ganze Zahl k übergeben. Das Ergebnis dieser Anfrage besteht aus den k Datensätze mit den höchsten Punktzahlen.

Leider ist eine genaue Angabe der Qualitätsfunktion bei Top-k-Anfragen häufig unmöglich. Allerdings fällt es den meisten Benutzern sehr leicht, qualitative Präferenzaussagen auf Attributebene zu machen, typische Beispiele sind „blaue Autos sind besser als rote“ und „je billiger desto besser“. Derartige Informationen bilden die Basis für Skyline-Anfragen. Zurückgeliefert werden alle Datensätze, die bezüglich der angegebenen Präferenzaussagen nicht offensichtlich schlechter sind als ein anderer Datensatz. Diese Menge von Datensätzen nennt man Skyline.

Thema 1: Präferenzgestütztes Datenbank-Retrieval I

Bereits Ende der 80er-Jahre gab es erste Versuche, benutzerzentrierte Anfragen in relationalen Datenbanken zu ermöglichen. Breites Interesse an dieser Problemstellung gab es jedoch erst über 10 Jahre später. Dieses Thema beschäftigt sich mit den frühen Ideen.

[LL87]
Michel Lacroix and Pierre Lavency. Preferences: Putting more knowledge into queries. In Peter M. Stocker, William Kent, and Peter Hammersley, editors, Proceedings of the 13th International Conference on Very Large Data Bases (VLDB 1987), pages 217-225. Morgan Kaufmann, 1987. [ .html ]
[Mot88]
Amihai Motro. VAGUE: A user interface to relational databases that permits vague queries. ACM Transactions on Information Systems, 6(3):187-214, 1988. [ DOI ]
[AW00]
Rakesh Agrawal and Edward L. Wimmers. A framework for expressing and combining preferences. In Weidong Chen, Jeffrey F. Naughton, and Philip A. Bernstein, editors, Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data (SIGMOD 2000), pages 297-306. ACM Press, 2000. [ DOI ]

Thema 2: Präferenzgestütztes Datenbank-Retrieval II

Preference SQL ist eine systematische Formalisierung für Menschen typischer Präferenzaussagen sowie die Formulierung von Regeln, wie derartige Anfragen in klassische SQL-Anfragen umgewandelt werden können. Ein ähnlicher Ansatz von Jan Chomicki beruht auf aussagenlogischen Formeln.

[Kie02a]
Werner Kießling. Foundations of preferences in database systems. In Proceedings of the 28th International Conference on Very Large Data Bases (VLDB 2002), pages 311-322. Morgan Kaufmann, 2002. [ .pdf ]
[Kie02b]
Werner Kießling and Gerhard Köstler. Preference SQL - design, implementation, experiences. In Proceedings of the 28th International Conference on Very Large Data Bases (VLDB 2002), pages 990-1001. Morgan Kaufmann, 2002. [ .pdf ]
[Cho03]
Jan Chomicki. Preference formulas in relational queries. ACM Transactions on Database Systems, 28(4):427-466, 2003. [ DOI ]

Thema 3: Präferenzgestütztes Datenbank-Retrieval III

Koutrika und Ioannidis haben untersucht, wie sich die implizit durch ein Datenbankschema gegebenen sktrukturellen Informationen für Präferenzanfragen nutzen lassen.

[KI04]
George Koutrika and Yannis Ioannidis. Personalization of queries in database systems. In Proceedings of the 20th International Conference on Data Engineering (ICDE 2004), pages 597-608. IEEE Computer Society, 2004. [ DOI ]
[KI05]
George Koutrika and Yannis Ioannidis. Personalized queries under a generalized preference model. In Proceedings of the 21st International Conference on Data Engineering (ICDE 2005), pages 841-852. IEEE Computer Society, 2005. [ DOI ]

Thema 4: Top-k-Retrieval I

Dieses Thema behandelt Basisalgorithmen zum Top-k-Retrieval.

[Fag99]
Ronald Fagin. Combining fuzzy information from multiple systems. Journal of Computer and System Sciences, 58(1):83-99, 1999. [ DOI ]
[GBK00]
Ulrich Güntzer, Wolf-Tilo Balke, and Werner Kießling. Optimizing multi-feature queries for image databases. In Amr El Abbadi, Michael L. Brodie, Sharma Chakravarthy, Umeshwar Dayal, Nabil Kamel, Gunter Schlageter, and Kyu-Young Whang, editors, Proceedings of the 26th International Conference on Very Large Data Bases (VLDB 2000), pages 419-428. Morgan Kaufmann, 2000. [ .pdf ]

Thema 5: Top-k-Retrieval II

Die obigen Top-k-Basisalgorithmen sind nicht für alle Anwendungsszenarien gleich gut geeignet. Spezielle, aber realistische Probleme erfordern die in diesem Thema behandelten Algorithmen.

[GBK01]
Ulrich Güntzer, Wolf-Tilo Balke, and Werner Kießling. Towards efficient multi-feature queries in heterogeneous environments. In Proceedings of the 2001 International Conference on Information Technology: Coding and Computing (ITCC 2001), pages 622-628. IEEE Computer Society, 2001. [ DOI ]
[BGK02]
Wolf-Tilo Balke, Ulrich Güntzer, and Werner Kießling. On real-time top k querying for mobile services. In Robert Meersman and Zahir Tari, editors, On the Move to Meaningful Internet Systems 2002. Proceedings of the 2002 Confederated International Conferences CoopIS, DOA, and ODBASE, volume 2519 of Lecture Notes in Computer Science, pages 125-143. Springer, 2002. [ DOI ]
[FLN03]
Ronald Fagin, Amnon Lotem, and Moni Naor. Optimal aggregation algorithms for middleware. Journal of Computer and System Sciences, 66(4):614-656, 2003. [ DOI ]

Thema 6: Top-k-Retrieval III

Kevin Chen-Chuan Chang und Seung-won Hwang haben sich mit der Frage beschäftigt, wie man verschiedene Top-k-Algorithmen zu einem hybriden Algorithmus kombinieren kann. Ziel ist es, automatisch den für den vorliegenden Anwendungsfall oder Datensatz passenden Top-k-Algorithmus auszuwählen. Dies soll auch adaptiv geschehen können. Stellt sich etwa im Laufe der Anfragebearbeitung heraus, daß bisherige Annahmen falsch waren und ein ungeeigneter Algorithmus verwendet wurde, so sollte ein rascher Wechsel ohne Verlust der bisherigen Zwischenergebnisse möglich sein.

[HC07a]
Seung-won Hwang and Kevin Chen-Chuan Chang. Probe minimization by schedule optimization: Supporting top-k queries with expensive predicates. IEEE Transactions on Knowledge and Data Engineering, 19(5):646-662, 2007. [ DOI ]
[HC07b]
Seung-won Hwang and Kevin Chen-Chuan Chang. Optimizing top-k queries for middleware access: A unified cost-based approach. ACM Transactions on Database Systems, 32(1), 2007. [ DOI ]

Thema 7: Top-k-Retrieval IV

Aus Marktanalysen weiß man, daß Menschen sich bezüglich ihrer Präferenzen in größere Gruppen einteilen lassen. Dieses Wissen kann zur Beschleunigung der Beantwortung von Top-k-Anfragen verwendet werden. Die Grundidee ist dabei die Vorberechnung von besonders populären Anfragen und die Nutzung dieser Informationen bei der Beantwortung von Anfragen, die diesen sehr ähnlich sind.

[CBCLLS00]
Yuan-Chi Chang, Lawrence Bergman, Vittorio Castelli, Chung-Sheng Li, Ming-Ling Lo, and John R. Smith. The onion technique: Indexing for linear optimization queries. ACM SIGMOD Record, 29(2):391-402, 2000. [ DOI ]
[HP04]
Vagelis Hristidis. Algorithms and applications for answering ranked queries using ranked views. The VLDB Journal, 13(1):49-70, 2004. [ DOI ]

Thema 8: Skylines I

Dieses Thema beschäftigt sich mit der Frage, wie Skylines effizient berechnet werden können. Verglichen werden dabei insbesondere Algorithmen, die nur die Laufzeit optimieren, und solche, die zudem auch möglichst effizient mit Speicherzugriffen umgehen. Gerade letztere Algorithmen sind für den Einsatz in Datenbanken von zentraler Bedeutung.

[GSG07]
Parke Godfrey, Ryan Shipley, and Jarek Gryz. Algorithms and analyses for maximal vector computation. The VLDB Journal, 16(1):5-28, 2007. [ DOI ]

Thema 9: Skylines II

Indexe und andere vorberechnete Informationen sind beliebte Methoden zur Leistungssteigerung in relationalen Datenbanken. Dieses Thema geht der Frage nach, ob die Vorberechnung von Informationen auch bei der dynamischen Berechnung von Skylines helfen kann.

[PTFS05]
Dimitris Papadias, Yufei Tao, Greg Fu, and Bernhard Seeger. Progressive skyline computation in database systems. ACM Transactions on Database Systems, 30(1):41-82, 2005. [ DOI ]
[PYLJELWTYZ06]
Jian Pei, Yidong Yuan, Xuemin Lin, Wen Jin, Martin Ester, Qing Liu, Wei Wang, Yufei Tao, Jeffrey Xu Yu, and Qing Zhang. Towards multidimensional subspace skyline analysis. ACM Transactions on Database Systems, 31(4):1335-1381, 2006. [ DOI ]

Thema 10: Skylines III

Leider können Skylines sehr groß werden, wenn die Datensätze aus vielen verschiedenen Attributen bestehen. Eine nahe liegende Idee ist daher die möglichst „optimale“ Approximation von Skylines durch Samples. Leider stellte sich heraus, daß die Berechnung eines solchen Samples ein NP-vollständiges Problem ist.

[God04]
Parke Godfrey. Skyline cardinality for relational processing. How many vectors are maximal? In Dietmar Seipel and José María Turull-Torres, editors, Proceedings of the 3rd International Symposium on Foundations of Information and Knowledge Systems (FoIKS 2004), volume 2942 of Lecture Notes in Computer Science, pages 78-97. Springer, 2004. [ http ]
[KP07]
Vladlen Koltun and Christos H. Papadimitriou. Approximately dominating representatives. Theoretical Computer Science, 371(3):148-154, 2007. [ DOI ]

Thema 11: Skylines IV

Sehr große Skylines können durch verschiedene Methoden handhabbar gemacht werden. Dieses Thema betrachtet beispielhaft zwei davon.

[BZG05]
Wolf-Tilo Balke, Jason Xin Zheng, and Ulrich Güntzer. Approaching the efficient frontier: Cooperative database retrieval using high-dimensional skylines. In Lizhu Zhou, Beng Chin Ooi, and Xiaofeng Meng, editors, Proceedings of the 10th International Conference on Database Systems for Advanced Applications (DASFAA 2005), volume 3453 of Lecture Notes in Computer Science, pages 64-73. Springer, 2005. [ DOI ]
[LYH07]
Jongwuk Lee, Gae-won You, and Seung-won Hwang. Telescope: Zooming to interesting skylines. In Ramamohanarao Kotagiri, P. Radha Krishna, Mukesh Mohania, and Ekawit Nantajeewarawat, editors, Advances in Databases: Concepts, Systems and Applications. Proceedings of the 12th International Conference on Database Systems for Advanced Applications (DASFAA 2007), volume 4443 of Lecture Notes in Computer Science, pages 539-550. Springer, 2007. [ DOI ]

Thema 12: Skylines V

In diesem Thema geht es ebenso um den Umgang mit großen Skylines. Hier steht jedoch eine Änderung der zugrunde liegenden Semantik im Mittelpunkt.

[BGS07b]
Wolf-Tilo Balke, Ulrich Güntzer, and Wolf Siberski. Restricting skyline sizes using weak Pareto dominance. Informatik - Forschung und Entwicklung, 21(3-4):165-178, 2007. [ DOI ]
[CJTTZ06b]
Chee-Yong Chan, Hosagrahar V. Jagadish, Kian-Lee Tan, Anthony K. H. Tung, and Zhenjie Zhang. Finding k-dominant skylines in high dimensional space. In Surajit Chaudhuri, Vagelis Hristidis, and Neoklis Polyzotis, editors, Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data (SIGMOD 2006), pages 503-514. ACM Press, 2006. [ DOI ]
AttachmentDateSize
File checkliste.pdf16/02/09 4:45 pm96.43 KB
File Hansmann.pdf16/02/09 4:48 pm1.31 MB
File Berndt.pdf16/02/09 4:57 pm243.06 KB
File Nieke.pdf16/02/09 4:57 pm1.02 MB
File Schön.pdf16/02/09 4:57 pm1.99 MB
File Breske.pdf20/02/09 9:53 am533.8 KB