[Back]

R. Pichler, S. Skritek:
"The Complexity of Evaluating Tuple Generating Dependencies";
Talk: International Conference on Database Theory (ICDT), Uppsala, Schweden; 03-21-2011 - 03-25-2011; in: "Proceedings of the 14^th International Conference on Database Theory", T. Milo (ed.); ACM, (2011), ISBN: 978-1-4503-0529-7; Paper ID 23, 12 pages.

Dependencies have played an important role in database design for
many years. More recently, they have also turned out to be central
to data integration and data exchange. In this work we concentrate
on tuple generating dependencies (tgds) which enforce the presence
of certain tuples in a database instance if certain other tuples
are already present. Previous complexity results in data integration
and data exchange mainly referred to the data complexity. In this
work, we study the query complexity and combined complexity of
a fundamental problem related to tgds, namely checking if a given
tgd is satisfied by a database instance. We also address an important
variant of this problem which deals with updates (by inserts or
deletes) of a database: Here we have to check if all previously satisfied tgds are still satisfied after an update. We show that the query complexity and combined complexity of these problems are much
higher than the data complexity. However, we also prove sufficient
conditions on the tgds to reduce this high complexity.

Project Head Reinhard Pichler:
Service-orientierte Datenintegration

Project Head Reinhard Pichler:
Theoretisch Effiziente Lösbarkeit vs. Praktische Berechnung