Computer Science – Databases
Scientific paper
2005-06-08
Computer Science
Databases
In the proceedings of the the Logic and Computational Complexity Workshop, in conjunction with of the Logic in Computer Scienc
Scientific paper
In this paper we study the problem of reducing the evaluation costs of queries on finite databases in presence of integrity constraints, by designing and materializing views. Given a database schema, a set of queries defined on the schema, a set of integrity constraints, and a storage limit, to find a solution to this problem means to find a set of views that satisfies the storage limit, provides equivalent rewritings of the queries under the constraints (this requirement is weaker than equivalence in the absence of constraints), and reduces the total costs of evaluating the queries. This problem, database reformulation, is important for many applications, including data warehousing and query optimization. We give complexity results and algorithms for database reformulation in presence of constraints, for conjunctive queries, views, and rewritings and for several types of constraints, including functional and inclusion dependencies. To obtain better complexity results, we introduce an unchase technique, which reduces the problem of query equivalence under constraints to equivalence in the absence of constraints without increasing query size.
Chirkova Rada
Genesereth Michael R.
No associations
LandOfFree
Database Reformulation with Integrity Constraints (extended abstract) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Database Reformulation with Integrity Constraints (extended abstract), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Database Reformulation with Integrity Constraints (extended abstract) will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-170359