Bounded Query Rewriting Using Views

Yang Cao, Wenfei Fan, Floris Geerts, Ping Lu

Research output: Chapter in Book/Report/Conference proceedingConference contribution


A query Q has a bounded rewriting using a set of views if there exists a query Q′ expressed in the same language as Q, such that given a 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, a combination of 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, 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.
Original languageEnglish
Title of host publicationPODS '16 Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
PublisherACM Press
Number of pages13
ISBN (Print)978-1-4503-4191-2
Publication statusPublished - 2016
Event35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems - San Francisco, United States
Duration: 26 Jun 20161 Jul 2016


Conference35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
Abbreviated titleSIGMOD PODS 2016
CountryUnited States
CitySan Francisco
Internet address

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

Cite this