English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

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 heist eine Division kann mit Hilfe anderer Operatoren der Algebra ausgedruckt werden. Da in der Anfragesprache SQL kein adaquates Sprachkonstrukt fur die relationale Division existiert, ist es nicht moglich, eine SQL-Anfrage, die ein All-Quantifizierungsproblem enthalt, auf intuitive Weise zu formulieren. Fur den ebenfalls abgeleiteten Verbundoperator hingegen gibt es adaquate 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 konnen. Dazu gehoren auch Uberlegungen zur Integration der Operatoren in ein Datenbanksystem. So benotigt ein Datenbanksystem Transformationsregeln fur Ausfuhrungsplane wahrend der Anfrageoptimierung und Strategien zur Parallelisierung der Plane. Diese und weitere Fragen werden in dieser Dissertation erortert, die in die nachfolgend skizzierten drei Teilbereiche gegliedert ist.  Erstens, schlage ich eine Klassifikation der Eingabedatencharakteristika fur die Division vor und ordne jeder Klasse Algorithmen zu, die die jeweiligen Datencharakteristika fur eine effiziente Verarbeitung voraussetzen. Daruber hinaus werden mehrere algebraische Gesetze (Transformationsregeln) formuliert, die einen algebraischen Ausdruck mit Divisionsoperator in einen aquivalenten Ausdruck uberfuhren. Die Klassifikation der Eingabedaten mit dazugehorigen in Frage kommenden Divisionsrealisierungen ist zusammen mit den algebraischen Gesetzen die Voraussetzung dafur, dass ein Anfrageoptimierer einen effizienten Ausfuhrungsplan 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 Divisionsausfuhrungen. Wir zeigen die Aquivalenz dieses Operators mit anderen Vorschlagen aus der Literatur und stellen die Ahnlichkeit zum Set-Containment-Join-Operator heraus, dessen Verbundbedingung auf mengenwertigen Attributen basiert. Fur all diese Operatoren werden verschiedene Algorithmen untersucht, es werden neue Ansatze fur die Set Containment Division vorgeschlagen und Strategien zur parallelen Ausfuhrung des Operators diskutiert. Zu den neuen Ansatzen gehort 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 fur die relationale Division und ahnliche Operatoren die klassische Data-Mining-Technik Frequent Itemset Discovery, bei der haufig auftretende Kombinationen von Elementen (Frequent Itemsets) in einer grosen Anzahl von Mengen (Transaktionen) gesucht wird. Insbesondere wird uberpruft, welche Transaktionen eine Obermenge von bestimmten Itemsets sind. Dieses Problem wird zum Beispiel idealerweise durch den Set-Containment-Division-Operator gelost. 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 reprasentiert. Ublicherweise werden in allen anderen Ansatzen, die auf SQL-92 beruhen, vollstandige Itemsets durch ein einziges Tupel reprasentiert. 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 Anfrageausfuhrungsplanen aufgezeigt.

Query processing concepts and techniques for set containment tests