Answering queries using views with arithmetic comparisons

Foto Afrati; Chen Li; Prasenjit Mitra

doi:10.1145/543613.543641

Answering queries using views with arithmetic comparisons

Foto Afrati
, Chen Li
, Prasenjit Mitra

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

33 Scopus citations

Abstract

We consider the problem of answering queries using views, where queries and views are conjunctive queries with arithmetic comparisons (CQACs) over dense orders. Previous work only considered limited variants of this problem, without giving a complete solution. We have developed a novel algorithm to obtain maximally-contained rewritings (MCRs) for queries having left (or right) semi-interval-comparison predicates. For semi-interval queries, we show that the language of finite unions of CQAC rewritings is not sufficient to find a maximally-contained solution, and identify cases where datalog is sufficient. Finally, we show that it is decidable to obtain equivalent rewritings for CQAC queries.

Original language	English (US)
Title of host publication	Proceedings of the 21st ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, PODS 2002
Publisher	Association for Computing Machinery (ACM)
Pages	209-220
Number of pages	12
ISBN (Electronic)	9781581135077
DOIs	https://doi.org/10.1145/543613.543641
State	Published - Jun 3 2002
Event	21st ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, PODS 2002 - Madison, WI, United States Duration: Jun 3 2002 → Jun 5 2002

Publication series

Name	Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
ISSN (Print)	1055-6338

Conference

Conference	21st ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, PODS 2002
Country/Territory	United States
City	Madison, WI
Period	6/3/02 → 6/5/02

All Science Journal Classification (ASJC) codes

General Engineering

Access to Document

10.1145/543613.543641

Cite this

Afrati, F., Li, C., & Mitra, P. (2002). Answering queries using views with arithmetic comparisons. In Proceedings of the 21st ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, PODS 2002 (pp. 209-220). (Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems). Association for Computing Machinery (ACM). https://doi.org/10.1145/543613.543641

@inproceedings{fce0f2ac42694ca289a6d8b58c476b15,

title = "Answering queries using views with arithmetic comparisons",

abstract = "We consider the problem of answering queries using views, where queries and views are conjunctive queries with arithmetic comparisons (CQACs) over dense orders. Previous work only considered limited variants of this problem, without giving a complete solution. We have developed a novel algorithm to obtain maximally-contained rewritings (MCRs) for queries having left (or right) semi-interval-comparison predicates. For semi-interval queries, we show that the language of finite unions of CQAC rewritings is not sufficient to find a maximally-contained solution, and identify cases where datalog is sufficient. Finally, we show that it is decidable to obtain equivalent rewritings for CQAC queries.",

author = "Foto Afrati and Chen Li and Prasenjit Mitra",

year = "2002",

month = jun,

day = "3",

doi = "10.1145/543613.543641",

language = "English (US)",

series = "Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems",

publisher = "Association for Computing Machinery (ACM)",

pages = "209--220",

booktitle = "Proceedings of the 21st ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, PODS 2002",

address = "United States",

note = "21st ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, PODS 2002 ; Conference date: 03-06-2002 Through 05-06-2002",

}

Afrati, F, Li, C & Mitra, P 2002, Answering queries using views with arithmetic comparisons. in Proceedings of the 21st ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, PODS 2002. Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Association for Computing Machinery (ACM), pp. 209-220, 21st ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, PODS 2002, Madison, WI, United States, 6/3/02. https://doi.org/10.1145/543613.543641

Answering queries using views with arithmetic comparisons. / Afrati, Foto; Li, Chen; Mitra, Prasenjit.
Proceedings of the 21st ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, PODS 2002. Association for Computing Machinery (ACM), 2002. p. 209-220 (Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems).

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

TY - GEN

T1 - Answering queries using views with arithmetic comparisons

AU - Afrati, Foto

AU - Li, Chen

AU - Mitra, Prasenjit

PY - 2002/6/3

Y1 - 2002/6/3

N2 - We consider the problem of answering queries using views, where queries and views are conjunctive queries with arithmetic comparisons (CQACs) over dense orders. Previous work only considered limited variants of this problem, without giving a complete solution. We have developed a novel algorithm to obtain maximally-contained rewritings (MCRs) for queries having left (or right) semi-interval-comparison predicates. For semi-interval queries, we show that the language of finite unions of CQAC rewritings is not sufficient to find a maximally-contained solution, and identify cases where datalog is sufficient. Finally, we show that it is decidable to obtain equivalent rewritings for CQAC queries.

AB - We consider the problem of answering queries using views, where queries and views are conjunctive queries with arithmetic comparisons (CQACs) over dense orders. Previous work only considered limited variants of this problem, without giving a complete solution. We have developed a novel algorithm to obtain maximally-contained rewritings (MCRs) for queries having left (or right) semi-interval-comparison predicates. For semi-interval queries, we show that the language of finite unions of CQAC rewritings is not sufficient to find a maximally-contained solution, and identify cases where datalog is sufficient. Finally, we show that it is decidable to obtain equivalent rewritings for CQAC queries.

UR - https://www.scopus.com/pages/publications/0036041424

UR - https://www.scopus.com/pages/publications/0036041424#tab=citedBy

U2 - 10.1145/543613.543641

DO - 10.1145/543613.543641

M3 - Conference contribution

AN - SCOPUS:0036041424

T3 - Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

SP - 209

EP - 220

BT - Proceedings of the 21st ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, PODS 2002

PB - Association for Computing Machinery (ACM)

T2 - 21st ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, PODS 2002

Y2 - 3 June 2002 through 5 June 2002

ER -

Afrati F, Li C, Mitra P. Answering queries using views with arithmetic comparisons. In Proceedings of the 21st ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, PODS 2002. Association for Computing Machinery (ACM). 2002. p. 209-220. (Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems). doi: 10.1145/543613.543641

Answering queries using views with arithmetic comparisons

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this