Processing Queries By Linear Constraints.

@inproceedings{DBLP:conf/pods/GoldsteinRSY97,
  author    = {Jonathan Goldstein and
               Raghu Ramakrishnan and
               Uri Shaft and
               Jie-Bing Yu},
  title     = {Processing Queries By Linear Constraints},
  booktitle = {Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 12-14, 1997, Tucson, Arizona},
  publisher = {ACM Press},
  year      = {1997},
  isbn      = {0-89791-910-6},
  pages     = {257-267},
  ee        = {http://doi.acm.org/10.1145/263661.263689, db/conf/pods/GoldsteinRSY97.html},
  crossref  = {DBLP:conf/pods/97},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The emergence of several new application domains for databases has introduced the need for more efficient complex query handling than databases currently support. These application domains include On-Line Analytica Processing (OLAP), Geographical Information Systems (GIS), and scientific databases.

This paper focuses attention on a form of selection query, expressible in SQL but not evaluated efficiently by current DBMSs, with wide applicability in these new problem domains. We introduce a processing strategy for this class of queries, which we call queries by linear constraints (QBLC). This processing strategy can be implemented with a wide variety of multidimensional indexing structures that include the R-Tree variants, the k-d-B-Tree, the Buddy-Tree, and many more. Note that any processing strategy meant for general database use must guarantee that all correct answers are returned. Therefore, all numerical techniques we employ uphold this guarantee. Thus the most distinguishing characteristic of this processing strategy is its safe handling of numerical error (which can result in the dismissal of valid answers).

This paper presents several theoretical results about our processing strategy, and the results of several experiments which show that the processing cost of selection queries by linear constraints can be reduced dramatically by using our processing strategy.

Copyright © 1997 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

[1]

Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331 BibTeX

[2]

...

[3]

David J. DeWitt, Navin Kabra, Jun Luo, Jignesh M. Patel, Jie-Bing Yu: Client-Server Paradise. VLDB 1994: 558-569 BibTeX

[4]

...

[5]

...

[6]

...

[7]

Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX

[8]

Hans-Peter Kriegel, Michael Schiwietz: Performance Comparison of Point and Spatial Access Methods. SSD 1989: 89-114 BibTeX

[9]

Bernhard Seeger, Hans-Peter Kriegel: The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems. VLDB 1990: 590-601 BibTeX

[10]

...

[11]

...

[12]

Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) BibTeX

[13]

...

[14]

John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18 BibTeX

[15]

Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 BibTeX

Referenced by

1. Haifeng Yu, Amin Vahdat: Efficient Numerical Error Bounding for Replicated Network Services. VLDB 2000: 123-133
2. Simonas Saltenis, Christian S. Jensen, Scott T. Leutenegger, Mario A. Lopez: Indexing the Positions of Continuously Moving Objects. SIGMOD Conference 2000: 331-342
3. Yuan-Chi Chang, Lawrence D. Bergman, Vittorio Castelli, Chung-Sheng Li, Ming-Ling Lo, John R. Smith: The Onion Technique: Indexing for Linear Optimization Queries. SIGMOD Conference 2000: 391-402
4. George Kollios, Dimitrios Gunopulos, Vassilis J. Tsotras: On Indexing Mobile Objects. PODS 1999: 261-272
5. Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paolo Giulio Franciosa, Jeffrey Scott Vitter: Efficient Searching with Linear Constraints. PODS 1998: 169-178