Edinburgh Research Explorer

Bounded Query Rewriting Using Views

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

Related Edinburgh Organisations

Open Access permissions

Open

Documents

http://dl.acm.org/citation.cfm?id=2902294
Original languageEnglish
Title of host publicationPODS '16 Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
PublisherACM Press
Pages107-119
Number of pages13
ISBN (Print)978-1-4503-4191-2
DOIs
Publication statusPublished - 2016
Event35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems - San Francisco, United States
Duration: 26 Jun 20161 Jul 2016
http://sigmod2016.org/

Conference

Conference35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
Abbreviated titleSIGMOD PODS 2016
CountryUnited States
CitySan Francisco
Period26/06/161/07/16
Internet address

Abstract

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.

Event

35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

26/06/161/07/16

San Francisco, United States

Event: Conference

Download statistics

No data available

ID: 25032679