Answering Queries Using Limited External Processors.

@inproceedings{DBLP:conf/pods/LevyRU96,
  author    = {Alon Y. Levy and
               Anand Rajaraman and
               Jeffrey D. Ullman},
  title     = {Answering Queries Using Limited External Processors},
  booktitle = {Proceedings of the Fifteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 3-5, 1996, Montreal,
               Canada},
  publisher = {ACM Press},
  year      = {1996},
  isbn      = {0-89791-781-2},
  pages     = {227-237},
  ee        = {http://doi.acm.org/10.1145/237661.237716, db/conf/pods/LevyRU96.html},
  crossref  = {DBLP:conf/pods/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

When answering queries using external information sources, their contents can be described by views. To answer a query, we must rewrite it using the set of views presented by the sources. When the external information sources also have the ability to answert some (perhaps limited) sets of queries that require performing operations on their data, the set of views presented by the source may be infinite (albeit encoded in some finite fashion). Previous work on answering queries using views has only considered the cases where the set of views is finite. In order to exploit the ability of information sources to answer more complex queries, we consider the problem of answering conjunctive queries using infinite sets of views. Our first result is that an infinite set of views can be partitioned into a finite number of equivalence classes, such that picking one view from every nonempty class is sufficient to determine whether the query can be answered using the views. Second, we show how to compute the set of equivalence classes for sets of views encoded by a datalog program. Furthermore, we extend our results to the case when the query and the views use the built-in predicates <, <=, =, and !=, and they are interpreted over a dense domain.

Finally, we extend our results to conjunctive queries and views with the built-in predicates <, <=, and = interpreted over the integers. In doing so we present a result of independent interest, namely, an algorithm to minimize such queries.

Copyright © 1996 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

References

[ACHK94]

Yigal Arens, Chin Y. Chee, Chun-Nan Hsu, Craig A. Knoblock: Retrieving and Integrating Data from Multiple Information Sources. Int. J. Cooperative Inf. Syst. 2(2): 127-158(1993)

[BI94]

Daniel Barbará, Tomasz Imielinski: Sleepers and Workaholics: Caching Strategies in Mobile Environments. SIGMOD Conference 1994: 1-12

[CGMH+94]

Sudarshan S. Chawathe, Hector Garcia-Molina, Joachim Hammer, Kelly Ireland, Yannis Papakonstantinou, Jeffrey D. Ullman, Jennifer Widom: The TSIMMIS Project: Integration of Heterogeneous Information Sources. IPSJ 1994: 7-18

[CKPS95]

Surajit Chaudhuri, Ravi Krishnamurthy, Spyros Potamianos, Kyuseok Shim: Optimizing Queries with Materialized Views. ICDE 1995: 190-200

[CM77]

Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90

[EW94]

Oren Etzioni, Daniel S. Weld: A Softbot-Based Interface to the Internet. Commun. ACM 37(7): 72-76(1994)

[GMR95]

Ashish Gupta, Inderpal Singh Mumick, Kenneth A. Ross: Adapting Materialized Views after Redefinitions. SIGMOD Conference 1995: 211-222

[GSUW94]

Ashish Gupta, Yehoshua Sagiv, Jeffrey D. Ullman, Jennifer Widom: Constraint Checking with Partial Information. PODS 1994: 45-55

[HSW94]

Yixiu Huang, A. Prasad Sistla, Ouri Wolfson: Data Replication for Mobile Computers. SIGMOD Conference 1994: 13-24

[Klu88]

Anthony C. Klug: On conjunctive queries containing inequalities. J. ACM 35(1): 146-160(1988)

[LMSS95]

Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava: Answering Queries Using Views. PODS 1995: 95-104

[LRO95]

...

[LRO96]

Alon Y. Levy, Anand Rajaraman, Joann J. Ordille: Query-Answering Algorithms for Information Agents. AAAI/IAAI, Vol. 1 1996: 40-47

[LS92]

Alon Y. Levy, Yehoshua Sagiv: Constraints and Redundancy in Datalog. PODS 1992: 67-80

[LS93]

Alon Y. Levy, Yehoshua Sagiv: Queries Independent of Updates. VLDB 1993: 171-181

[LSK95]

Alon Y. Levy, Divesh Srivastava, Thomas Kirk: Data Model and Query Evaluation in Global Information Systems. J. Intell. Inf. Syst. 5(2): 121-143(1995)

[PGGMU95]

Yannis Papakonstantinou, Ashish Gupta, Hector Garcia-Molina, Jeffrey D. Ullman: A Query Translation Scheme for Rapid Implementation of Wrappers. DOOD 1995: 161-186

[RSU95]

Anand Rajaraman, Yehoshua Sagiv, Jeffrey D. Ullman: Answering Queries Using Templates with Binding Patterns. PODS 1995: 105-112

[SAB+95]

...

[TSI94]

Odysseas G. Tsatalos, Marvin H. Solomon, Yannis E. Ioannidis: The GMAP: A Versatile Tool for Physical Data Independence. VLDB 1994: 367-378

[vdM92]

Ron van der Meyden: The Complexity of Querying Indefinite Data about Linearly Ordered Domains. PODS 1992: 331-345

[YL87]

H. Z. Yang, Per-Åke Larson: Query Transformation for PSJ-Queries. VLDB 1987: 245-254