Artikel in Zeitschrift ART-2003-02

Rantzau, Ralf; Shapiro, Leonard; Mitschang, Bernhard; Wang, Quan: Algorithms and Applications for Universal Quantification in Relational Databases.
In: Christian S. Jensen (Hrsg): Information Systems. Vol. 28(1-2).
Universität Stuttgart, Fakultät Informatik.
S. 3-32, englisch.
Elsevier, Januar 2003.
Artikel in Zeitschrift.
KörperschaftBest Papers from EDBT 2002
CR-Klassif.H.2.4 (Database Management Systems)
Keywordsquery operators; relational division; grouping; set containment join; frequent itemset discovery

Queries containing universal quantification are used in many applications, including business intelligence applications and in particular data mining. We present a comprehensive survey of the structure and performance of algorithms for universal quantification. We introduce a framework that results in a complete classification 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. Thus, for the first time, we are able to identify the optimal algorithm to use for any given input dataset.

These two classifications of optimal algorithms and input data are important for query optimization. They allow a query optimizer to make the best selection when optimizing at intermediate steps for the quantification problem.

In addition to the classification, we show the relationship between relational division and the set containment join and we illustrate the usefulness of employing universal quantifications by presenting a novel approach for frequent itemset discovery.

Volltext und
andere Links
Information Systems Journal
Abteilung(en)Universität Stuttgart, Institut für Parallele und Verteilte Höchstleistungsrechner, Anwendersoftware
Eingabedatum9. Dezember 2002
   Publ. Abteilung   Publ. Institut   Publ. Informatik