Abstract
Users of database applications, especially in the e-commerce domain, often resort to exploratory “trial-and-error” queries since the underlying data space is huge and unfamiliar, and there are several alternatives for search attributes in this space. For example, scouting for cheap airfares typically involves posing multiple queries, varying flight times, dates, and airport locations. Exploratory queries are problematic from the perspective of both the user and the server. For the database server, it results in a drastic reduction in effective throughput since much of the processing is duplicated in each successive query. For the client, it results in a marked increase in response times, especially when accessing the service through wireless channels.
In this paper, we investigate the design of automated techniques to minimize the need for repetitive exploratory queries. Specifically, we present SAUNA, a server-side query relaxation algorithm that, given the user’s initial range query and a desired cardinality for the answer set, produces a relaxed query that is expected to contain the required number of answers. The algorithm incorporates a range-query-specific distance metric that is weighted to produce relaxed queries of a desired shape (e.g., aspect ratio preserving), and utilizes multi-dimensional histograms for query size estimation. A detailed performance evaluation of SAUNA over a variety of multi-dimensional data sets indicates that its relaxed queries can significantly reduce the costs associated with exploratory query processing.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Shafer, J., Agrawal, R.: Continuous querying in database-centric web applications. Computer Networks 33(1-6), 519–531 (2000)
Travelocity, http://www.travelocity.com
Carey, M., Kossmann, D.: On saying "enough already!" in SQL. In: Proc. of SIGMOD Conf., pp. 219–230 (1997)
64K Inc. DBGuide introduction and technology overview (1997)
Bruno, N., Chaudhuri, S., Gravano, L.: Top-k selection queries over relational databases: Mapping strategies and performance evaluation. ACM TODS 27(2) (2002)
Muralikrishna, M., DeWitt, D.: Equi-depth histograms for estimating selectivity factors for multi-dimensional queries. Proc. of SIGMOD Conf., 28–36 (1998)
Poosala, V., Ioannidis, Y., Haas, P., Shekita, E.: Improved histograms for selectivity estimation of range predicates. In: Proc. of SIGMOD, pp. 294–305 (1996)
Aboulnaga, A., Chaudhuri, S.: Self-tuning histograms: Building histograms without looking at data. In: Proc. of SIGMOD Conf., pp. 181–192 (1999)
Gradshteyn, I., Ryzhik, I.: Tables of Integrals, Series and Products. Academic Press, London (2000)
Kadlag, A., Wanjari, A., Freire, J., Haritsa, J.: Supporting Exploratory Queries in Databases. Technical Report, TR-2003-02, DSL/SERC (2003), http://dsl.serc.iisc.ernet.in/pub/TR/TR-2003-02.pdf
Press, W., et al.: Numerical Recipes in C: The Art of Scientific Computing. Cambridge University Press, Cambridge (1993)
UCI knowledge discovery in databases archive, http://kdd.ics.uci.edu/summary.data.type.html
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kadlag, A., Wanjari, A.V., Freire, J., Haritsa, J.R. (2004). Supporting Exploratory Queries in Databases. In: Lee, Y., Li, J., Whang, KY., Lee, D. (eds) Database Systems for Advanced Applications. DASFAA 2004. Lecture Notes in Computer Science, vol 2973. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24571-1_54
Download citation
DOI: https://doi.org/10.1007/978-3-540-24571-1_54
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21047-4
Online ISBN: 978-3-540-24571-1
eBook Packages: Springer Book Archive