|
|
|
@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}
}
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.
