Bounded Query Rewriting Using Views

Yang Cao, Wenfei Fan, Floris Geerts, Ping Lu

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

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.
Original languageEnglish
Article number6
Number of pages46
JournalACM Transactions on Database Systems
Issue number1
Publication statusPublished - 23 Mar 2018


Dive into the research topics of 'Bounded Query Rewriting Using Views'. Together they form a unique fingerprint.

Cite this