Artikel in Tagungsband INPROC-2006-32

Bibliograph.
Daten
Rantzau, Ralf; Mangold, Christoph: Laws for Rewriting Queries Containing Division Operators.
In: Liu, Ling (Hrsg); Reuter, Andreas (Hrsg); Whang, Kyu-Young (Hrsg); Zhang, Jianjun (Hrsg): Proceedings of the 22nd International Conference on Data Engineering, ICDE 2006.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik.
S. 21-21, englisch.
IEEE Computer Society, April 2006.
Artikel in Tagungsband (Konferenz-Beitrag).
CR-Klassif.F.4.1 (Mathematical Logic)
H.2.3 (Database Management Languages)
Kurzfassung

Relational division, also known as small divide, is a derived operator of the relational algebra that realizes a many-to-one set containment test, where a set is represented as a group of tuples: Small divide discovers which sets in a dividend relation contain all elements of the set stored in a divisor relation. The great divide operator extends small divide by realizing many-to-many set containment tests. It is also similar to the set containment join operator for schemas that are not in first normal form.

Neither small nor great divide has been implemented in commercial relational database systems although the operators solve important problems and many efficient algorithms for them exist. We present algebraic laws that allow rewriting expressions containing small or great divide, illustrate their importance for query optimization, and discuss the use of great divide for frequent itemset discovery, an important data mining primitive.

A recent theoretic result shows that small divide must be implemented by special purpose algorithms and not be simulated by pure relational algebra expressions to achieve efficiency. Consequently, an efficient implementation requires that the optimizer treats small divide as a first-class operator and possesses powerful algebraic laws for query rewriting.

Volltext und
andere Links
PDF (233689 Bytes)
CopyrightIEEE Computer Society
Abteilung(en)Universität Stuttgart, Institut für Parallele und Verteilte Systeme, Anwendersoftware
Projekt(e)ORBIT
Eingabedatum29. Mai 2006
   Publ. Abteilung   Publ. Institut   Publ. Informatik