Vorträge

Mit einer Woche Verspätung stelle ich nun Ihnen die Themen in unserem Seminar vor. Zunächst einmal möchte ich mich bei Ihnen für diese Verzögerung entschuldigen und hoffe, daß Sie trotzdem noch motiviert sind, bei unserem Seminar sich zu beteiligen. Als Basisliteratur zum Seminar empfiehlt sich der Artikel [CD 97]. Es wird vorausgesetzt, daß alle Studierende des Seminars diesen Artikel kennen. Die Vortragenden können also insebesondere beim Aufschreiben der Zusammenfassung und beim Vortrag von diesen Vorkenntnissen ausgehen. Neben diesem Artikel wird auch das Skript Datenbanksysteme I vorausgesetzt, das insbesondere ein Kapitel zum Thema Datawarehousing enthält. Empfehlenswert ist darüberhinaus [Man 97], der eine Übersicht zum Thema Data Mining gibt. Im folgenden möchte ich nun die einzelnen Vorträge vorstellen.

Integration von heterogenen Datenquellen

Ein DW führt Daten aus verschiedenen Quellsystemen zusammen. Diese Quellsysteme sind autark und wissen nicht, daß ihre Daten in ein DW aufgenommen werden sollen. Eines der wichtigsten Probleme ist deshalb, wie nun ein Abgleich der Daten z. B. Adressen durchgeführt werden kann. Dieses grundlegende Problem wird in [CohA 98] diskutiert und in [CohB 98] ein entsprechendes System vorgestellt.

Mengenorientiertes Einfügen

In diesem Vortrag geht es um ein grundlegendes Problem: wie kann in einer Indexstruktur wie z. B. einem B+-Baum eine Menge von Datensätzen effizient eingefügt werden. Offensichtlich läßt sich dies dadurch bewerkstelligen, daß die zur Indexstruktur gehörende Methode zum Einfügen einzelner Datensätze pro einzufügenden Datensatz einmal aufgerufen wird. Dies ist aber nicht sehr effizient. In den Artikeln [BHS 98] und [JNS+ 97] werden zwei verschiedene Ansätze vorgestellt, die eine schnellere Verarbeitung beim mengenorientierten Einfügen ermöglichen. Mengenorientiertes Einfügen ist einem DW wichtig, da i. a. die Änderungen aus den Quellsystemen erst gesammelt und dann im Pulk in das DW propagiert werden.

Implementierung des Datenwürfels durch eine multidimensionale Indexstruktur

Die Datenwürfel eines DW können auf zwei verschiedene Weisen implementiert werden. Eine Möglichkeit besteht darin eine relationale Datenbanksystem hierfür zu verwenden. Die andere Möglichkeit liegt in der Verwendung einer speziellen Speicherstruktur. Auf Grund des mehrdimensionalen Charakters der Daten empfiehlt sich hierbei eine mehrdimensionale Datenstruktur zu verwenden. Die dabei auftretenden Probleme - insbesondere das Problem des mengenorientierten Einfügen - werden in [RKR 97] und [KR 98] betrachtet.

Bitmap-Indizes (1 oder 2 Vorträge)

Mit den neuen Anforderungen im Bereich des DW wurde vor wenigen Jahren eine neue Indexstruktur entwickelt, die sogenannte Bitmap-Join Indexstruktur, die innerhalb kürzester Zeit auch bereits in einigen kommerziellen Systemen wie z. B. ORACLE implementiert wurde und dem Benutzer zur Verfügung steht. Verschiedene Varianten dieser Klasse von Indexstrukturen werden in [OQ 97] und [WB 98] diskutiert. In [CI 98] wurde das Problem der Leistungsbeurteilung von Bitmap-Indexstrukturen betrachtet. Wir haben uns noch nicht entschieden, ob auf Grund des großen Stoffumfangs in diesem Bereich nicht zwei Vorträge gehalten werden sollen.

Auswahl von materialisierten Sichten

Eine der wichtigsten Problemstellungen in einem DW stellt die Auswahl der sogenannten materialisierten Sichten des Datenwürfels dar, die physisch redundant abgelegt werden. Ziel dabei ist es, Anfragen im Datenwürfel möglichst effizient zu unterstützen unter der Nebenbedingung, daß die Nebenkosten bei Änderungsoperationen niedrig sind. Da die Anzahl möglicher Sichten exponentiel in der Anzahl der Dimensionen des Würfels ansteigt, muß man sich bei der Auswahl auf wenige Sichten beschränken. Wie findet man nun geeignete Sichten? Erste Antworten dazu wurden in [HRU 96] gegeben. Eine ausführliche Behandlung des Problems unter weitaus realistischeren Annahmen als in dem oben referenzierten Bericht findet man in [BPT 97].

Erkennen von Assoziationsregeln (2 Vorträge)

Eines der wichtigsten Aufgaben im Bereich des Data Mining ist das Erkennen von Assoziationsregeln. Typischerweise sind z. B. Anbieter von Waren wie z. B. ALDI, LIDL, TEGUT, ... an dem typischen Verhalten eines Käufers interessiert (Warenkorbanalyse). Das Ziel der Warenkorbanalyse ist es, Mengen von Waren zu finden, die häufig zusammen im Warenkorb liegen. Eine in den USA oft genanntes Beispiel für eine (durch Data Mining entdeckte ?) Regel ist, daß Windeln und Bier oft zusammen eingekauft werden. Zu diesem Themenkomplex werden verschiedene Vorträge angeboten. Im ersten Vortrag, sollen die prinzipiellen Verfahren vorgestellt werden, um Assoziationsregeln bei der Warenkorbanalyse zu erkennen [AIS 93], [AS 94].

Im zweiten Vortrag soll die Implementierung von Assoziationsregeln diskutiert werden. In [TUA+ 98] wird auf eine Verallgemeinerung des Konzepts von Assoziationsregeln und statt SQL die Sprache Datalog [Ull 88] zur Formulierung von Regeln benutzt wird. Eine Implementierung von Assoziationsregeln mittels relationaler Datenbanktechnologie wird in [STA 98] vorgestellt.

Clusterung von großen Datenmengen

Algorithmen zur Bildung von großen Datencluster sind integraler Bestandteil beim Data Mining. Es gilt dabei aus einer Datenmenge Gruppen von möglichst ähnlichen Datensätzen zu finden. Zwei Ansätze [ZRL 96] und [GRS 98] sollen in diesem Vortrag diskutiert und verglichen werden.

Anfragen in Zeitreihen

In diesem Vortrag soll das Problem der Suche nach ähnlichen Zeitreihen untersucht werden. Als Grundlage dienen dabei [FRM 94], [YJF 98]. Beispiele von Zeitreihen sind z. B. Börsenkurse oder das Schlafverhalten von Patienten (das am Klinikum in Marburg untersucht wird). Durch das Auffinden ähnlicher Zeitreihen erhofft man sich Prognosen über zukünftige Ereignisse zu erstellen.

On-Line Berechnung von Anfragen

Die schnelle Berechnung von Aggregaten ist eine der wichtigsten Aufgaben eines OLAP Servers. Heutige DBMS unterstützen solche Anfragen in der Form, daß der Benutzer zunächst die Anfrage in SQL formuliert und dann auf das Ergebnis wartet (bzw. warten muß). Auf Grund der sehr großen Datenmengen sind bei diesem Vorgehen die Antwortzeiten nicht akzeptabel. Da der Benutzer i. a. nicht unbedingt am exakten Ergebnis interessiert ist, sondern sich auch mit einer Approximation zufrieden gibt, stellt sich die Frage, nach schnellen Verfahren zur approximativen Berechnung von Anfragen. Eine Lösung dazu wird in [HHW 97] dargestellt. Dabei werden während die Anfrage läuft, vorläufige approximative Ergebnisse dem Benutzer zur Verfügung gestellt.
Literatur
Die Berichte werden als Postscript-Dateien in  diesem Directory den Studierenden des Seminars zur Verfügung gestellt. Beachten Sie dabei, daß der Zugriff nur von einem Rechner des Fachbereichs Mathematik der Uni Marburg erlaubt ist. Es gibt im Semesterapparat auch einen Ordner, wo die Berichte eingesehen werden können.

[AAB+ 96] R. Agrawal, A. Arning, T. Bollinger, M. Mehta, J. Shafer, R. Srikant, "The Quest Data Mining System", Proc. of the 2nd Int'l Conference on Knowledge Discovery in Databases and Data Mining, Portland, Oregon, August 1996.

[AIS 93] Rakesh Agrawal, Tomasz Imielinski, Arun N. Swami: Mining Association Rules between Sets of Items in Large Databases: SIGMOD Conference 1993: 207-216

[AS 94] R. Agrawal and R. Srikant, "Fast Algorithms for Mining Association Rules", Proc. of the 20th Int'l Conf. on Very Large Databases, Santiago, Chile, Sep. 1994.

[BHS 98] Jochen van den Bercken, Steffen Heinz, Bernhard Seeger: On Supporting Bulk Insertions in Multidimensional Index Structures Efficiently, submitted for publication.

[BPT 97] Elena Baralis, Stefano Paraboschi, Ernest Teniente: Materialized Views Selection in a Multidimensional Database. VLDB 1997: 156-165

[CD 97] Surajit Chaudhuri, Umeshwar Dayal: An Overview of Data Warehousing and OLAP Technology. SIGMOD Record 26(1): 65-74 (1997)

[CI 98] Chee Yong Chan, Yannis E. Ioannidis: Bitmap Index Design and Evaluation. SIGMOD Conference 1998: 355-366

[CohA 98] William W. Cohen: Integration of Heterogeneous Databases Without Common Domains Using Queries Based on Textual Similarity. SIGMOD Conference 1998: 201-212

[CohB 98] William W. Cohen: The Whirl Approch to Integration: An overview. submitted to publication

[FRM 94] Christos Faloutsos, M. Ranganathan and Yannis Manolopoulos Fast Subsequence Matching in Time-Series Databases, Proc. ACM SIGMOD, Minneapolis MN, May 25-27, 1994, pp. 419-429

[GRS 98] Sudipto Guha, Rajeev Rastogi, Kyuseok Shim: CURE: An Efficient Clustering Algorithm for Large Databases. SIGMOD Conference 1998: 73-84

[HHW 97] Joseph M. Hellerstein, Peter J. Haas, Helen Wang: Online Aggregation. SIGMOD Conference 1997: 171-182

[HRU 96] Venky Harinarayan, Anand Rajaraman, Jeffrey D. Ullman: Implementing Data Cubes Efficiently. SIGMOD Conf. 1996: 205-216

[JNS+ 97] H. V. Jagadish, P. P. S. Narayan, S. Seshadri, S. Sudarshan, Rama Kanneganti: Incremental Organization for Data Recording and Warehousing. VLDB 1997: 16-25

[KJF 97] Flip Korn, H.V. Jagadish and Christos Faloutsos Efficiently Supporting Ad Hoc Queries in Large Datasets of Time Sequences ACM SIGMOD, Tucson, AZ, pp. 289-300, May 1997

[KR 98] Yannis Kotidis, Nick Roussopoulos: An Alternative Storage Organization for ROLAP Aggregate Views Based on Cubetrees. SIGMOD Conference 1998: 249-258

[LQA 97] Wilburt Labio, Dallan Quass, Brad Adelberg: Physical Database Design for Data Warehouses. ICDE 1997: 277-288

[Man 97] Heikki Mannila: Methods and problems in data mining (a tutorial). Proceedings of International Conference on Database Theory (ICDT'97), Delphi, Greece, January 1997, F. Afrati and P. Kolaitis (ed.), p. 41-55

[OQ 97] Patrick E. O'Neil, Dallan Quass: Improved Query Performance with Variant Indexes. SIGMOD Conference 1997: 38-49

[RKR 97] Nick Roussopoulos, Yannis Kotidis, Mema Roussopoulos: Cubetree: Organization of and Bulk Updates on the Data Cube. SIGMOD Conference 1997: 89-99

[TUA+ 98] Dick Tsur, Jeffrey D. Ullman, Serge Abiteboul, Chris Clifton, Rajeev Motwani, Svetlozar Nestorov, Arnon Rosenthal: Query Flocks: A Generalization of Association-Rule Mining. SIGMOD Conference 1998: 1-12

[Ull 88] Jeffrey D. Ullman: Principles of Database abd Knowledge-Base Systems, Vol. I+II, Computer Science Press, 1988

[WB 98] Ming-Chuan Wu, Alejandro P. Buchmann: Encoded Bitmap Indexing for Data Warehouses. ICDE 1998: 220-230

[YJF 98] Byoung-Kee Yi, H. V. Jagadish, Christos Faloutsos: Efficient Retrieval of Similar Time Sequences Under Time Warping. ICDE 1998: 201-208

[ZRL 96] Tian Zhang, Raghu Ramakrishnan, Miron Livny: BIRCH: An Efficient Data Clustering Method for Very Large Databases. SIGMOD Conf. 1996: 103-114