Data Cleaning und Anfragen auf Zerlegungen von Datenbanken mit unvollständiger Information

• Antragsteller: Professor Dr. Christoph Koch
• Fachliche Zuordnung: Sicherheit und Verlässlichkeit, Betriebs-, Kommunikations- und verteilte Systeme
• Förderung: Förderung von 2006 bis 2008
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 25617221

• Erstellungsjahr: 2010

Zusammenfassung der Projektergebnisse

Obwohl unvollständig spezifizierte Datenbanken in der Praxis oft eher die Regel als eine Ausnahme darstellen - Beispiele für Datenbanken mit unvollständiger Information findet man besonders in Datenintegrationsanwendungen, Webapplikationen, und wissenschaftlichen Datensammlungen - wurde bisher sehr wenig Forschung an effizient handhabbaren Repräsentationssystemen für unvollständige Information betrieben. Eine Folge der beschriebenen Situation ist, dass die einschlägigen in der Vergangenheit erreichten Forschungsresultate zu unvollständiger Information in der Praxis nicht genützt werden. Die weitverbreiteten SQL-Datenbanksysteme bieten stattdessen nur eine sehr schwache Form von Nullwerten an. Eine darüberhinausgehende Unterstützung von Unvollständigkeit in Datenbanken wäre für die Informationssystempraxis in den obengenannten Gebieten von grossem Nutzen. Das Ziel dieses Projekts war, ein starkes und gleichzeitig skalierbares Repräsentationssystem für grosse Datenbanken mit unvollständiger Information zu entwickeln, das die effiziente Durchführung von Data Cleaning und Anfragebearbeitung ermöglicht. Tatsächlich wurde nicht nur dieses Ziel erreicht. Zusätzlich wurden Algorithmen zur effizienten Auswertung von Datenbankanfragen auf grossen unvollständigen und probabilistischen Datenbanken entwickelt und in ein vollständiges Datenbankmanagementsystem integriert. Dieses System ist nun als Open-Source-Projekt unter der Adresse http://maybms.sourceforge.net/ frei verfügbar und wurde bereits von mehreren hunderten Forschungsgruppen und Individuen heruntergeladen.

Projektbezogene Publikationen (Auswahl)

• 10^(10^6) Worlds and Beyond: Efficient Representation and Processing of Incomplete Information. ICDE 2007: 606- 615
  Lyublena Antova, Christoph Koch, Dan Olteanu
  
• From complete to incomplete information and back. SIGMOD Conference 2007: 713-724
  Lyublena Antova, Christoph Koch, Dan Olteanu
  
• MayBMS: Managing Incomplete Information with Probabilistic World-Set Decompositions. ICDE 2007: 1479-1480
  Lyublena Antova, Christoph Koch, Dan Olteanu
  
• Query language support for incomplete information in the MayBMS system. VLDB 2007: 1422-1425
  Lyublena Antova, Christoph Koch, Dan Olteanu
  
• World-Set Decompositions: Expressiveness and Efficient Algorithms. ICDT 2007: 194-208
  Lyublena Antova, Christoph Koch, Dan Olteanu
  
• Approximating Predicates and Expressive Queries on Probabilistic Databases. Proc. PODS 2008
  C. Koch
  
• Conditioning probabilistic databases. PVLDB 1(1): 313-325 (2008)
  Christoph Koch, Dan Olteanu
  
• Fast and Simple Relational Processing of Uncertain Data. ICDE 2008: 983-992
  Lyublena Antova, Thomas Jansen, Christoph Koch, Dan Olteanu
  
• On Query Algebras for Probabilistic Databases. SIGMOD Record 37(4): 78-85 (2008)
  Christoph Koch
  
• World-set decompositions: Expressiveness and efficient algorithms. Theor. Comput. Sci. 403(2-3): 265-284 (2008)
  Dan Olteanu, Christoph Koch, Lyublena Antova
  
• 10^(10^6) Worlds and Beyond: Efficient Representation and Processing of Incomplete Information. VLDB Journal 18(5): 1021-1040 (2009), Special Issue on Uncertain and Probabilistic Databases
  Lyublena Antova, Christoph Koch, and Dan Olteanu
  
• MayBMS: A System for Managing Large Uncertain and Probabilistic Databases. Chapter 6 of Charu Aggarwal, ed., Managing and Mining Uncertain Data, Springer-Verlag, 2009
  C. Koch