Query processing concepts and techniques for set containment tests

Abstract

Relational division is an operator of the relational algebra that realizes universal quantifications in queries against a relational database. Expressing a universal quantification problem in SQL is cumbersome. If the division operator would have a counterpart in a query language, a more intuitive formulation of universal quantification problems would be possible. Although division is a derived operator - it can be expressed using other basic algebra operators - the performance of queries involving a division problem can be significantly increased if it is implemented as a separate operator in a query processor.

In this work, we study relational division as well as operators related to it like set containment join. We present a classification of division algorithms and define algebraic laws to enable query optimization for queries involving division. A natural generalization of the division operator, called set containment division, is proposed and algorithms that realize it are discussed, including an algorithm that uses a new in-memory index data structure. Furthermore, we study strategies for parallelizing set containment division algorithms.

The most popular data mining sub-task called frequent itemset discovery, where one tries to find the number of transactions that contain a given set of items, is an excellent example of a problem that requires efficient set containment tests. In this work, we focus on frequent itemset discovery algorithms that exploit the query processing capabilities of a relational database system. After reviewing the best algorithms based on SQL-92, we suggest a new approach, called Quiver, that can be executed with the help of set containment division.

We report on performance results that cover experiments with frequent itemset discovery algorithms running on commercial database systems as well as experiments that highlight the most important properties of set containment test algorithms using a query processor prototype implemented in Java.

Die Division ist ein Operator der relationalen Algebra zur Realisierung der All-Quantifizierung innerhalb einer Anfrage an ein relationales Datenbanksystem. Die Division ist ein abgeleiteter Operator, wie zum Beispiel auch der Verbundoperator (Join), das heißt eine Division kann mit Hilfe anderer Operatoren der Algebra ausgedrückt werden. Da in der Anfragesprache SQL kein adäquates Sprachkonstrukt für die relationale Division existiert, ist es nicht möglich, eine SQL-Anfrage, die ein All-Quantifizierungsproblem enthält, auf intuitive Weise zu formulieren. Für den ebenfalls abgeleiteten Verbundoperator hingegen gibt es adäquate Sprachkonstrukte in SQL. In der Literatur wurden Divisionsalgorithmen vorgestellt, die deutlich effizienter sind als Realisierungen des Operators mit Hilfe von Basisoperatoren.

Diese Arbeit befasst sich sowohl mit der relationalen Division als auch mit verwandten Operatoren, wie beispielsweise dem Set Containment Join. Dabei steht die Frage im Zentrum, durch welche effizienten Algorithmen die logischen Operatoren realisiert werden können. Dazu gehören auch Überlegungen zur Integration der Operatoren in ein Datenbanksystem. So benötigt ein Datenbanksystem Transformationsregeln für Ausführungspläne während der Anfrageoptimierung und Strategien zur Parallelisierung der Pläne. Diese und weitere Fragen werden in dieser Dissertation erörtert, die in die nachfolgend skizzierten drei Teilbereiche gegliedert ist.

Erstens, schlage ich eine Klassifikation der Eingabedatencharakteristika für die Division vor und ordne jeder Klasse Algorithmen zu, die die jeweiligen Datencharakteristika für eine effiziente Verarbeitung voraussetzen. Darüber hinaus werden mehrere algebraische Gesetze (Transformationsregeln) formuliert, die einen algebraischen Ausdruck mit Divisionsoperator in einen äquivalenten Ausdruck überführen. Die Klassifikation der Eingabedaten mit dazugehörigen in Frage kommenden Divisionsrealisierungen ist zusammen mit den algebraischen Gesetzen die Voraussetzung dafür, dass ein Anfrageoptimierer einen effizienten Ausführungsplan einer Anfrage mit Division finden kann.

Zweitens, stelle ich einen erweiterten Divisionsoperators vor, Set-Containment-Division-Operator genannt, der nicht auf einem einzigen Divisor, sondern auf mehreren Gruppen von Divisoren operiert. Der Operator realisiert dabei eine Vereinigung von mehreren Divisionsausführungen. Wir zeigen die Äquivalenz dieses Operators mit anderen Vorschlägen aus der Literatur und stellen die Ähnlichkeit zum Set-Containment-Join-Operator heraus, dessen Verbundbedingung auf mengenwertigen Attributen basiert. Für all diese Operatoren werden verschiedene Algorithmen untersucht, es werden neue Ansätze für die Set Containment Division vorgeschlagen und Strategien zur parallelen Ausführung des Operators diskutiert. Zu den neuen Ansätzen gehört der Algorithmus Subset Index Set Containment Division, der auf einer Datenstruktur beruht, die die Ober- und Untermengenbeziehung zwischen den Mengen in einer Relation effizient verwaltet.

Drittens, untersuche ich als Einsatzgebiet für die relationale Division und ähnliche Operatoren die klassische Data-Mining-Technik Frequent Itemset Discovery, bei der häufig auftretende Kombinationen von Elementen (Frequent Itemsets) in einer großen Anzahl von Mengen (Transaktionen) gesucht wird. Insbesondere wird überprüft, welche Transaktionen eine Obermenge von bestimmten Itemsets sind. Dieses Problem wird zum Beispiel idealerweise durch den Set-Containment-Division-Operator gelöst. Wir stellen einen neuen Frequent-Itemset-Discovery-Algorithmus genannt Quiver vor, der von einem solchen Operator profitiert. Die Besonderheit des Algorithmus liegt darin, dass sowohl die Transaktionen als auch die Itemsets in Relationen verwaltet werden, bei denen ein Tupel ein Menge-Element-Paar repräsentiert. Üblicherweise werden in allen anderen Ansätzen, die auf SQL-92 beruhen, vollständige Itemsets durch ein einziges Tupel repräsentiert. Neben diesem neuen Algorithmus werden SQL-basierte Algorithmen analyisert und das Leistungsverhalten der Algorithmen sowohl an Hand von Messungen mit kommerziellen Datenbanksystemen als auch mit einer eigenen Implementierung von Anfrageausführungsplänen aufgezeigt.