Instituts-Logo Logik in der Informatik
Prof. Dr. Martin Grohe 		Humboldt-Logo

Seminar: Grundlagen der Datenintegration
und des Datenaustauschs
(Sommersemester 2012)

Aktuelles   Einführung   Organisation   Themen   Literatur

Aktuelles

Einführung

Informationsintegration hat zum Ziel, Informationen verschiedener Datenquellen zusammenzufassen und in einem einheitlichen Format zur Verfügung zu stellen. Konkrete Beispiele sind etwa (Meta-)suchmaschinen, Google's Fusion Tables oder Metadatenbanken für biologische Daten wie beispielsweise SOURCE. Laut einem Artikel von Bernstein und Haas aus dem Jahr 2008 investieren große Unternehmen viel Geld und Zeit in Informationsintegration. Allerdings ist sie aufgrund der Verfügbarkeit zahlloser Datenquellen im Internet nicht nur für große Unternehmen interessant. Gerade für die Forschung gewinnt sie zunehmend an Bedeutung, etwa bei der Integration von Daten unterschiedlicher Forschungslaboratorien bzw. -gruppen.

Zwei der wichtigsten Kernaufgaben der Informationsintegration sind Datenintegration und Datenaustausch. Während Datenintegration die virtuelle Integration der Datenquellen anstrebt, die eigentliche globale Sicht auf die Datenquellen also nicht wirklich materialisiert und Anfragen an die globale Sicht zur Laufzeit mit Hilfe der Datenquellen beantwortet, steht beim Datenaustausch eine Berechnung einer Datenbank im Vordergrund, die die Datenquellen bestmöglichst integriert. Wir werden uns in diesem Seminar mit grundlegenden konzeptionellen als auch algorithmischen Fragestellungen bezüglich Datenintegration und Datenaustausch auseinandersetzen.

Grundlegende Kenntnisse der Logik erster Stufe sind vorteilhaft.

Organisation

Zeit und Raum:  Mittwochs 13-15 Uhr, Erwin Schrödinger-Zentrum (Rudower Chausee 26), Raum 1'308
Veranstalter:  André Hernich

Vortragsthemen

Hier ist eine Liste der Vortragsthemen. Möglicherweise wird sich diese noch etwas ändern.

  1. Datenaustausch I
    1. Einführung und Semantik [FKMP, Kapitel 1–3]
    2. Beantwortung von Anfragen [FKMP, Kapitel 4–5]
  2. Query Rewriting und Views
    1. Umschreiben von Anfragen mit Hilfe von Views [LMSS, siehe auch H]
    2. Der MiniCon-Algorithmus [HP, siehe auch H]
    3. Skalierbares Query Rewriting [KA]
    4. Beantwortung von Anfragen mit Views [AD]
  3. Datenaustausch II
    1. Minimale allgemeinste Lösungen [FKP, Kapitel 3–5]
    2. Wie schwer ist es, Lösungen zu berechnen? [KPT]
    3. Die Chase-Prozedur und universelle Modelle [DNR]
    4. Chase-Termination [GS1]
    5. Grenzen der Anfrageverarbeitung [ABFL]
  4. Datenintegration und Ontologien
    1. Effiziente Beantwortung von Anfragen unter guarded Datalog +/- [CGL]
    2. Kleinere Rewritings von Anfragen via Datalog-Rewritings [GS2]
  5. Ableiten von Schema-Mappings aus Beispielen
    1. Charakterisierung von Schema-Mappings mit Beispielen [ACKT1, Abschnitte 1–5 und 7]
    2. Design und Verfeinerung von Schema-Mappings mit Beispielen [ACKT2]

Literatur

Zum Herunterladen der meisten der unten aufgeführten Arbeiten über die Download-Links müssen Sie sich im Universitäts-Netzwerk befinden. Vorabversionen finden Sie in fast allen Fällen auf den Webseiten der entsprechenden Autoren.

Zu den Vortragsthemen:

[ABFL] M. Arenas, P. Barceló, R. Fagin, L Libkin. Locally Consistent Transformations and Query Answering in Data Exchange. Proceedings of the 23th ACM Symposium on Principles of Database Systems (PODS'04), S. 229–240, 2004. [Download]
[ACKT1] B. Alexe, B. ten Cate, P. G. Kolaitis, W.-C. Tan. Characterizing Schema Mappings via Data Examples. ACM Transactions on Database Systems 36(4), Article 23, 2011. [Download]
[ACKT2] B. Alexe, B. ten Cate, P. G. Kolaitis, W.-C. Tan. Designing and Refining Schema Mappings via Data Examples. Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD'11), S. 113–144, 2011. [Download]
[AD] S. Abiteboul, O. M. Duschka. Complexity of Answering Queries Using Materialized Views. Proceedings of the 17th ACM Symposium on Principles of Database Systems (PODS'98), S. 254–263, 1998. [Download]
[AHV] S. Abiteboul, R. Hull, V. Vianu. Foundations of Databases. Addison-Wesley, 1995.
[CGL] A. Calì, G. Gottlob, T. Lukasiewicz. A General Datalog-Based Framework for Tractable Query Answering over Ontologies. Proceedings of the 28th ACM Symposium on Principles of Database Systems (PODS'09), S. 77–86, 2009. [Download]
[DNR] A. Deutsch, A. Nash, J. Remmel. The Chase Revisited. Proceedings of the 27th ACM Symposium on Principles of Database Systems (PODS'08), S. 149–158, 2008. [Download]
[FKMP] R. Fagin, P. G. Kolaitis, R. Miller, L. Popa. Data exchange: Semantics and Query Answering. Theoretical Computer Science 336(1), S. 89–124, 2005. [Download]
[FKP] R. Fagin, P. G. Kolaitis, L. Popa. Data exchange: Getting to the Core. ACM Transactions on Database Systems 30(1), S. 174–210, 2005. [Download]
[GS1] S. Greco, F. Spezzano. Chase Termination: A Constraints Rewriting Approach. Proceedings of the VLDB Endowment 3(1), S. 93–104, 2010. [Download]
[GS2] G. Gottlob, T. Schwentick. Rewriting Ontological Queries into Small Nonrecursive Datalog Programs. Erscheint in Proceedings of 13th International Conference on Principles of Knowledge Representation and Reasoning (KR'12), 2012. [Download]
[HP] A. Y. Halevy, R. Pottinger. MiniCon: A Scalable Algorithm for Answering Queries using Views. VLDB Journal 10(2–3), S. 182–198, 2001. [Download]
[KA] G. Konstantinidis, J. L. Ambite. Scalable Query Rewriting: A Graph-Based Approach. Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD'11), S. 97–108, 2011. [Download]
[KPT] P. G. Kolaitis, J. Panttaja, W.-C. Tan. The Complexity of Data Exchange. Proceedings of the 25th ACM Symposium on Principles of Database Systems (PODS'06), S. 30–39, 2006. [Download]
[LMSS] A. Y. Levy, A. O. Mendelzon, Y. Sagiv, D. Srivastava. Answering Queries Using Views. Proceedings of the 14th ACM Symposium on Principles of Database Systems (PODS'95), S. 95–104, 1995. [Download]

Übersichtsartikel:

[B] P. Barceló. Logical Foundations of Relational Data Exchange. SIGMOD Record 38(1), S. 49–58, 2009. [Download]
[BH] P. A. Bernstein, L. M. Haas. Information Integration in the Enterprise. Communications of the ACM 51(9), S. 72–79, 2008. [Download]
[H] A. Y. Halevy. Answering Queries using Views: A Survey. The VLDB Journal 10, S. 270–294, 2001. [Download]
[L] M. Lenzerini. Data Integration: A Theoretical Perspective. Proceedings of the 21st ACM Symposium on Principles of Database Systems (PODS'02), S. 233–246, 2002. [Download]

zuletzt geändert: 11. April 2012
André Hernich