Approximate rewriting of queries using views

Foto Afrati; Manik Chandrachud; Rada Chirkova; Prasenjit Mitra

doi:10.1007/978-3-642-03973-7_13

Approximate rewriting of queries using views

Foto Afrati, Manik Chandrachud, Rada Chirkova, Prasenjit Mitra

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Scopus citations

Abstract

We study approximate, that is contained and containing, rewritings of queries using views. We consider conjunctive queries with arithmetic comparisons (CQACs), which capture the full expressive power of SQL select-project-join queries. For contained rewritings, we present a sound and complete algorithm for constructing, for CQAC queries and views, a maximally-contained rewriting (MCR) whose all CQAC disjuncts have up to a predetermined number of view literals. For containing rewritings, we present a sound and efficient algorithm pruned-MiCR, which computes a CQAC containing rewriting that does not contain any other CQAC containing rewriting (i.e., computes a minimally containing rewriting, MiCR) and that has the minimum possible number of relational subgoals. As a result, the MiCR rewriting produced by our algorithm may be very efficient to execute. Both algorithms have good scalability and perform well in many practical cases, due to their extensive pruning of the search space, see [1].

Original language	English (US)
Title of host publication	Advances in Databases and Information Systems - 13th East European Conference, ADBIS 2009, Proceedings
Pages	164-178
Number of pages	15
DOIs	https://doi.org/10.1007/978-3-642-03973-7_13
State	Published - 2009
Event	13th East European Conference on Advances in Databases and Information Systems, ADBIS 2009 - Riga, Latvia Duration: Sep 7 2009 → Sep 10 2009

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5739 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	13th East European Conference on Advances in Databases and Information Systems, ADBIS 2009
Country/Territory	Latvia
City	Riga
Period	9/7/09 → 9/10/09

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-03973-7_13

Cite this

Afrati, F., Chandrachud, M., Chirkova, R., & Mitra, P. (2009). Approximate rewriting of queries using views. In Advances in Databases and Information Systems - 13th East European Conference, ADBIS 2009, Proceedings (pp. 164-178). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5739 LNCS). https://doi.org/10.1007/978-3-642-03973-7_13

@inproceedings{78065174b1e64a68829c9e291ce229fc,

title = "Approximate rewriting of queries using views",

abstract = "We study approximate, that is contained and containing, rewritings of queries using views. We consider conjunctive queries with arithmetic comparisons (CQACs), which capture the full expressive power of SQL select-project-join queries. For contained rewritings, we present a sound and complete algorithm for constructing, for CQAC queries and views, a maximally-contained rewriting (MCR) whose all CQAC disjuncts have up to a predetermined number of view literals. For containing rewritings, we present a sound and efficient algorithm pruned-MiCR, which computes a CQAC containing rewriting that does not contain any other CQAC containing rewriting (i.e., computes a minimally containing rewriting, MiCR) and that has the minimum possible number of relational subgoals. As a result, the MiCR rewriting produced by our algorithm may be very efficient to execute. Both algorithms have good scalability and perform well in many practical cases, due to their extensive pruning of the search space, see [1].",

author = "Foto Afrati and Manik Chandrachud and Rada Chirkova and Prasenjit Mitra",

note = "Copyright: Copyright 2012 Elsevier B.V., All rights reserved.; 13th East European Conference on Advances in Databases and Information Systems, ADBIS 2009 ; Conference date: 07-09-2009 Through 10-09-2009",

year = "2009",

doi = "10.1007/978-3-642-03973-7_13",

language = "English (US)",

isbn = "3642039723",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "164--178",

booktitle = "Advances in Databases and Information Systems - 13th East European Conference, ADBIS 2009, Proceedings",

}

Afrati, F, Chandrachud, M, Chirkova, R & Mitra, P 2009, Approximate rewriting of queries using views. in Advances in Databases and Information Systems - 13th East European Conference, ADBIS 2009, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5739 LNCS, pp. 164-178, 13th East European Conference on Advances in Databases and Information Systems, ADBIS 2009, Riga, Latvia, 9/7/09. https://doi.org/10.1007/978-3-642-03973-7_13

Approximate rewriting of queries using views. / Afrati, Foto; Chandrachud, Manik; Chirkova, Rada et al.
Advances in Databases and Information Systems - 13th East European Conference, ADBIS 2009, Proceedings. 2009. p. 164-178 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5739 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Approximate rewriting of queries using views

AU - Afrati, Foto

AU - Chandrachud, Manik

AU - Chirkova, Rada

AU - Mitra, Prasenjit

PY - 2009

Y1 - 2009

N2 - We study approximate, that is contained and containing, rewritings of queries using views. We consider conjunctive queries with arithmetic comparisons (CQACs), which capture the full expressive power of SQL select-project-join queries. For contained rewritings, we present a sound and complete algorithm for constructing, for CQAC queries and views, a maximally-contained rewriting (MCR) whose all CQAC disjuncts have up to a predetermined number of view literals. For containing rewritings, we present a sound and efficient algorithm pruned-MiCR, which computes a CQAC containing rewriting that does not contain any other CQAC containing rewriting (i.e., computes a minimally containing rewriting, MiCR) and that has the minimum possible number of relational subgoals. As a result, the MiCR rewriting produced by our algorithm may be very efficient to execute. Both algorithms have good scalability and perform well in many practical cases, due to their extensive pruning of the search space, see [1].

AB - We study approximate, that is contained and containing, rewritings of queries using views. We consider conjunctive queries with arithmetic comparisons (CQACs), which capture the full expressive power of SQL select-project-join queries. For contained rewritings, we present a sound and complete algorithm for constructing, for CQAC queries and views, a maximally-contained rewriting (MCR) whose all CQAC disjuncts have up to a predetermined number of view literals. For containing rewritings, we present a sound and efficient algorithm pruned-MiCR, which computes a CQAC containing rewriting that does not contain any other CQAC containing rewriting (i.e., computes a minimally containing rewriting, MiCR) and that has the minimum possible number of relational subgoals. As a result, the MiCR rewriting produced by our algorithm may be very efficient to execute. Both algorithms have good scalability and perform well in many practical cases, due to their extensive pruning of the search space, see [1].

UR - http://www.scopus.com/inward/record.url?scp=70449866026&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70449866026&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-03973-7_13

DO - 10.1007/978-3-642-03973-7_13

M3 - Conference contribution

AN - SCOPUS:70449866026

SN - 3642039723

SN - 9783642039720

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 164

EP - 178

BT - Advances in Databases and Information Systems - 13th East European Conference, ADBIS 2009, Proceedings

T2 - 13th East European Conference on Advances in Databases and Information Systems, ADBIS 2009

Y2 - 7 September 2009 through 10 September 2009

ER -

Afrati F, Chandrachud M, Chirkova R, Mitra P. Approximate rewriting of queries using views. In Advances in Databases and Information Systems - 13th East European Conference, ADBIS 2009, Proceedings. 2009. p. 164-178. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-03973-7_13

Approximate rewriting of queries using views

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this