Projects per year
Abstract
A query Q in a language L has a bounded rewriting using a set of L-definable views if there exists a query Q′ in L such that given any dataset D, Q(D) can be computed by Q′ that accesses only cached views and a small fraction DQ of D. We consider datasets D that satisfy a set of access constraints, which are a combination of simple cardinality constraints and associated indices, such that the size |DQ| of DQ and the time to identify DQ are independent of |D|, no matter how big D is.
This paper studies the problem for deciding whether a query has a bounded rewriting given a set V of views and a set A of access constraints. We establish the complexity of the problem for various query languages L, from Σp3-complete for conjunctive queries (CQ), to undecidable for relational algebra (FO). We show that the intractability for CQ is rather robust even for acyclic CQ with fixed V and A, and characterize when the problem is in PTIME. To make practical use of bounded rewriting, we provide an effective syntax for FO queries that have a bounded rewriting. The syntax characterizes a core subclass of such queries without sacrificing the expressive power, and can be checked in PTIME. Finally, we investigate L1-to-L2 bounded rewriting, when Q in L1 is allowed to be rewritten into a query Q′ in another language L2. We show that this relaxation does not simplify the analysis of bounded query rewriting using views.
This paper studies the problem for deciding whether a query has a bounded rewriting given a set V of views and a set A of access constraints. We establish the complexity of the problem for various query languages L, from Σp3-complete for conjunctive queries (CQ), to undecidable for relational algebra (FO). We show that the intractability for CQ is rather robust even for acyclic CQ with fixed V and A, and characterize when the problem is in PTIME. To make practical use of bounded rewriting, we provide an effective syntax for FO queries that have a bounded rewriting. The syntax characterizes a core subclass of such queries without sacrificing the expressive power, and can be checked in PTIME. Finally, we investigate L1-to-L2 bounded rewriting, when Q in L1 is allowed to be rewritten into a query Q′ in another language L2. We show that this relaxation does not simplify the analysis of bounded query rewriting using views.
Original language | English |
---|---|
Article number | 6 |
Number of pages | 46 |
Journal | ACM Transactions on Database Systems |
Volume | 43 |
Issue number | 1 |
DOIs | |
Publication status | Published - 23 Mar 2018 |
Fingerprint
Dive into the research topics of 'Bounded Query Rewriting Using Views'. Together they form a unique fingerprint.Projects
- 2 Finished
-
GRACE-Resource Bounded Graph Query Answering
Fan, W. (Principal Investigator)
1/11/15 → 31/10/21
Project: Research
-
VADA: Value Added Data Systems: Principles and Architecture
Libkin, L. (Principal Investigator), Buneman, P. (Co-investigator), Fan, W. (Co-investigator) & Pieris, A. (Co-investigator)
1/04/15 → 30/09/20
Project: Research
Profiles
-
Wenfei Fan
- School of Informatics - Personal Chair in Web Data Management
- Laboratory for Foundations of Computer Science
- Foundations of Computation
Person: Academic: Research Active