[Back]

A. Hubmer, R. Pichler, V. Savenkov, S. Skritek:
"Efficient Updates of Uncertain Databases";
Talk: 7th Alberto Mendelzon International Workshop on Foundations of Data Management 2013, Puebla/Cholula, Mexico; 2013-05-21 - 2013-05-23; in: "Proceedings of the 7th Alberto Mendelzon International Workshop on Foundations of Data Management Puebla/Cholula, Mexico, May 21-23, 2013", L. Bravo, M. Lenzerini (ed.); CEUR-WS, Vol-1087 (2013), ISSN: 1613-0073; Paper ID 9, 7 pages.

Uncertain databases have evolved as an active area of database research. The possible worlds semantics is commonly used to deal with uncertain data. Antova et al. introduced so-called U-relations as an efficient representation formalism for uncertain databases. This formalism guarantees polynomial-time data complexity for queries of positive relational algebra.

As in the case of certain databases, we clearly also want to update uncertain databases and pose queries of unrestricted relational algebra. Relatively little work has been done in this direction. The goal of our paper is to start the investigation of the update problem of U-relations and to tackle the problem of evaluating queries with anti-joins (i.e., "not-exists") over this formalism. To this end, we first define the anti-join operator for U-relations and show how to use it to model updates. It will turn out that updates of U-relations lead to a decompression of the succinct representation of possible worlds, which may indeed be a performance problem. We will therefore introduce an extension of the U-relation representation system and show that our new formalism may lead to an exponential decrease in the representation of an updated uncertain database.

Database updates, Uncertainty, Database algorithms

http://ceur-ws.org/Vol-1087/paper9.pdf

Project Head Reinhard Pichler:
Heterogene Information Integration