|
Title
|
|
|
|
Bounded query rewriting using views
| |
|
Author
|
|
|
|
| |
|
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 D-Q 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 |D-Q| of D-Q and the time to identify D-Q are independent of |D|, no matter how big D is. In this article, we study 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 Sigma(p)(3)-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 key subclass of such queries without sacrificing the expressive power, and can be checked in PTIME. Finally, we investigate L-1-to-L-2 bounded rewriting, when Q in L-1 is allowed to be rewritten into a query Q' in another language L-2. We show that this relaxation does not simplify the analysis of bounded query rewriting using views. |
| |
|
Language
|
|
|
|
English
| |
|
Source (journal)
|
|
|
|
ACM transactions on database systems. - New York, N.Y., 1976, currens
| |
|
Publication
|
|
|
|
New York, N.Y.
:
2018
| |
|
ISSN
|
|
|
|
0362-5915
1557-4644
[online]
| |
|
DOI
|
|
|
|
10.1145/3183673
| |
|
Volume/pages
|
|
|
|
43
:1
(2018)
, 46 p.
| |
|
Article Reference
|
|
|
|
6
| |
|
ISI
|
|
|
|
000430302000006
| |
|
Medium
|
|
|
|
E-only publicatie
| |
|
Full text (Publisher's DOI)
|
|
|
|
| |
|