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) BibTeX

[BI94]

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

[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 BibTeX

[CKPS95]

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

[CM77]

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

[EW94]

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

[GMR95]

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

[GSUW94]

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

[HSW94]

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

[Klu88]

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

[LMSS95]

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

[LRO95]

...

[LRO96]

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

[LS92]

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

[LS93]

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

[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) BibTeX

[PGGMU95]

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

[RSU95]

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

[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 BibTeX

[vdM92]

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

[YL87]

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

Referenced by

1. Yannis Papakonstantinou, Vasilis Vassalos: Query Rewriting for Semistructured Data. SIGMOD Conference 1999: 455-466
2. Kevin Chen-Chuan Chang, Hector Garcia-Molina: Mind Your Vocabulary: Query Mapping Across Heterogeneous Information Sources. SIGMOD Conference 1999: 335-346
3. Daniela Florescu, Alon Y. Levy, Alberto O. Mendelzon: Database Techniques for the World-Wide Web: A Survey. SIGMOD Record 27(3): 59-74(1998)
4. Luis Gravano, Yannis Papakonstantinou: Mediating and Metasearching on the Internet. IEEE Data Eng. Bull. 21(2): 28-36(1998)
5. Serge Abiteboul, Oliver M. Duschka: Complexity of Answering Queries Using Materialized Views. PODS 1998: 254-263
6. Anisoara Nica, Amy J. Lee, Elke A. Rundensteiner: The CVS Algorithm for View Synchronization in Evolvable Large-Scale Information Systems. EDBT 1998: 359-373
7. Vasilis Vassalos, Yannis Papakonstantinou: Describing and Using Query Capabilities of Heterogeneous Sources. VLDB 1997: 256-265
8. Laura M. Haas, Donald Kossmann, Edward L. Wimmers, Jun Yang: Optimizing Queries Across Diverse Data Sources. VLDB 1997: 276-285
9. Oscar H. Ibarra, Jianwen Su: On the Containment and Equivalence of Database Queries with Linear Constraints. PODS 1997: 32-43
10. Richard Hull: Managing Semantic Heterogeneity in Databases: A Theoretical Perspective. PODS 1997: 51-61
11. Oliver M. Duschka, Michael R. Genesereth: Answering Recursive Queries Using Views. PODS 1997: 109-116
12. Catriel Beeri, Alon Y. Levy, Marie-Christine Rousset: Rewriting Queries Using Views in Description Logics. PODS 1997: 99-108
13. Jeffrey D. Ullman: Information Integration Using Logical Views. ICDT 1997: 19-40
14. Chandra Chekuri, Anand Rajaraman: Conjunctive Query Containment Revisited. ICDT 1997: 56-70
15. Dan Suciu: Query Decomposition and View Maintenance for Query Languages for Unstructured Data. VLDB 1996: 227-238
16. Alon Y. Levy, Anand Rajaraman, Joann J. Ordille: Querying Heterogeneous Information Sources Using Source Descriptions. VLDB 1996: 251-262