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.