The Complexity of Evaluating Tuple Generating Dependencies

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 paper, the authors 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 paper, they 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.

Provided by: Association for Computing Machinery Topic: Data Management Date Added: Mar 2011 Format: PDF

Find By Topic