New representations of uncertain databases for efficient updates

Abstract

Ungewisse Daten entstehen in vielen Anwendungen, beispielsweise in Sensornetzwerken, bei der Informationsextraktion und bei der Datenintegration.<br />Während gewöhnliche relationale Datenbanken keine Möglichkeit bieten diese Daten zu verarbeiten, verwalten ungewisse Datenbanken die Ungewissheit auf geeignete Weise.<br />Sie modellieren eine Vielzahl an möglichen Welten.<br />Die Herausforderung besteht darin, ungewisse Datenbanken möglichst Platz sparend darzustellen, und gleichzeitig eine effiziente Abfragebeantwortung zu ermöglichen.<br />U-Relationen sind ein ein äußerst Platz sparendes Darstellungssystem für ungewisse Datenbanken. Abfragen in positiver relationaler Algebra, erweitert um einen Operator für mögliche Antworten, können in polynomieller Zeit (Datenkomplexität) bearbeitet werden.<br />In dieser Arbeit gehen wir der Frage nach, wie U-Relationen aktualisiert werden können. Wir zeigen, dass positive relationale Algebra nicht ausreicht, um beliebige Updates durchzuführen, und reduzieren das Aktualisierungsproblem auf das Problem der Mengendifferenz zwischen zwei U-Relationen.<br />Wir stellen zwei Methoden dar: Dekompression und Negation. Während die Dekompression eine hohe Komplexität aufweist, berücksichtigt die Negation auch die Struktur der U-Relationen und erzielt dadurch bessere Ergebnisse.<br />Zusätzlich erweitern wir U-Relationen und beschreiben zwei neue Darstellungssysteme für ungewisse Datenbanken: Ui-Relationen und Uint-Relationen. Sie behalten die Vorteile von U-Relationen bei und reduzieren die Komplexität für die Mengendifferenz um einen exponentiellen Faktor.<br />Nach einer Aktualisierung werden U-Relationen möglicherweise nicht optimal dargestellt. Daher untersuchen wir das diesbezügliche Minimierungsproblem. Wir beweisen, dass das Minimierungsproblem NP-schwer ist und erläutern zwei Optimierungsheuristiken. Eine der beiden kann in die Berechnung der Mengendifferenz integriert werden, wodurch wir eine bessere obere Schranke für die Komplexität der Mengendifferenz zeigen können.<br />Um die praktische Anwendbarkeit der beschriebenen theoretischen Konzepte zu belegen, haben wir einen Prototyp entwickelt.<br />Unsere Experimente zeigen, dass unsere Lösungen gut mit der Größe der Datenbanken skalieren. Außerdem zeigt ein Vergleich, dass sowohl Ui-Relationen als auch Uint-Relationen deutlich den U-Relationen überlegen sind.<br />

Uncertain data arises in many applications, for example from sensor networks, information extraction and data integration. While ordinary relational databases do not have the capabilities to process uncertain data, uncertain databases conveniently manage the uncertainty.<br />They model a multitude of possible worlds.<br />The challenge is to represent uncertain databases succinctly, and at the same time allow for efficient query evaluation.<br />U-relations are a very succinct representation system for uncertain databases, which have polynomial time data complexity for positive relational algebra queries extended by an operator for computing possible answers.<br />In this work we study the problem of updating U-relations. We show that positive relational algebra does not suffice to model arbitrary updates and reduce the problem of updating U-relations to computing set difference on U-relations. We present two approaches: decompression and negation. While decompression has a rather high complexity, negation considers the structure of a U-relation and thus gives much better results.<br />Additionally we extend U-relations and present two new representation systems for uncertain databases: Ui-relations and Uint-relations. They keep the advantages of U-relations and lower the complexity of set difference exponentially.<br />As updating U-relations can lead to a suboptimal representation of the uncertain database, we investigate the problem of optimizing U-relations. We prove that finding the minimal representation is intractable and present two optimization heuristics. We integrate one of them into the computation of set difference, which gives a better bound for the complexity of set difference.<br />To show the practicability of our theoretical concepts we have created a prototype.<br />Our experiments show that it scales well with increasing database sizes, and a comparison makes clear that Ui-relations and Uint-relations are an improvement over U-relations.