Title: New representations of uncertain databases for efficient updates
Language: English
Authors: Hubmer, Andreas 
Qualification level: Diploma
Keywords: Ungewisse Datenbanken; Aktualisierung; Mengendifferenz; U-Relationen
Uncertain Database; Updates; Set Difference; U-relations
Advisor: Pichler, Reinhard 
Issue Date: 2011
Number of Pages: 101
Qualification level: Diploma
Abstract: 
Ungewisse Daten entstehen in vielen Anwendungen, beispielsweise in Sensornetzwerken, bei der Informationsextraktion und bei der Datenintegration.
Während gewöhnliche relationale Datenbanken keine Möglichkeit bieten diese Daten zu verarbeiten, verwalten ungewisse Datenbanken die Ungewissheit auf geeignete Weise.
Sie modellieren eine Vielzahl an möglichen Welten.
Die Herausforderung besteht darin, ungewisse Datenbanken möglichst Platz sparend darzustellen, und gleichzeitig eine effiziente Abfragebeantwortung zu ermöglichen.
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.
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.
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.
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.
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.
Um die praktische Anwendbarkeit der beschriebenen theoretischen Konzepte zu belegen, haben wir einen Prototyp entwickelt.
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.

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.
They model a multitude of possible worlds.
The challenge is to represent uncertain databases succinctly, and at the same time allow for efficient query evaluation.
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.
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.
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.
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.
To show the practicability of our theoretical concepts we have created a prototype.
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.
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-40663
http://hdl.handle.net/20.500.12708/9252
Library ID: AC07811248
Organisation: E184 - Institut für Informationssysteme 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:

Show full item record

Page view(s)

11
checked on Feb 21, 2021

Download(s)

51
checked on Feb 21, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.