Bibliography | Rantzau, Ralf; Shapiro, Leonard; Mitschang, Bernhard; Wang, Quan: Universal Quantification in Relational Databases: A Classification of Data and Algorithms. In: Proceedings of the International Conference on Extending Database Technology (EDBT), Prague, Czech Republic, March 2002. University of Stuttgart, Faculty of Computer Science. Lecture Notes in Computer Science; 2287, pp. 445-463, english. Springer, March 2002. ISBN: 3-540-43324-4. Article in Proceedings (Conference Paper).
|
CR-Schema | H.2.4 (Database Management Systems)
|
Keywords | query processing; relational division; physical operators |
Abstract | Queries containing universal quantification are used in many applications, including business intelligence applications. Several algorithms have been proposed to implement universal quantification efficiently. These algorithms are presented in an isolated manner in the research literature - typically, no relationships are shown between them. Furthermore, each of these algorithms claims to be superior to others, but in fact each algorithm has optimal performance only for certain types of input data. In this paper, we present a comprehensive survey of the structure and performance of algorithms for universal quantification. We introduce a framework for classifying all possible kinds of input data for universal quantification. Then we go on to identify the most efficient algorithm for each such class. One of the input data classes has not been covered so far. For this class, we propose several new algorithms. For the first time, we are able to identify the optimal algorithm to use for any given input dataset. These two classifications of input data and optimal algorithms are important for query optimization. They allow a query optimizer to make the best selection when optimizing at intermediate steps for the quantification problem.
|
Full text and other links | PostScript (1005887 Bytes) Springer LNCS
|
Copyright | Springer |
Contact | rrantzau@acm.org |
Department(s) | University of Stuttgart, Institute of Parallel and Distributed High-Performance Systems, Applications of Parallel and Distributed Systems
|
Project(s) | ORBIT
|
Entry date | December 10, 2001 |
---|