Query processing concepts and techniques for set containment tests [Elektronische Ressource] / vorgelegt von Ralf Rantzau

QUERY PROCESSINGCONCEPTS AND TECHNIQUESFOR SET CONTAINMENT TESTSVon der Fakultat¨ Informatik, Elektrotechnik und Informationstechnikder Universitat¨ Stuttgartzur Erlangung der Wurde¨ einesDoktors der Naturwissenschaften (Dr. rer. nat.)genehmigte AbhandlungVorgelegt vonRALF RANTZAUaus DetmoldHauptberichter: Univ.-Prof. Dr.-Ing. habil. Bernhard MitschangMitberichter: Univ Rudolf Bayer, Ph. D.Tag der mundlichen¨ Prufung:¨ 22. Dezember 2003Institut fur¨ Parallele und Verteilte Systeme (IPVS)der Universitat¨ Stuttgart,Bundesrepublik Deutschland2003ii“[...] the division operator does not have thesame importance as the other operators—it isnot needed as often, and database systems donot try to exploit the semantics of division byimplementing it as a distinct operator (as, forexample, is done with the join operator).”R. Ramakrishnan, J. Gehrke [RG00]PrefaceThe above citation is a good commentary on the division operator. This work investigates thedivision operator and related operators that all help to solve the set containment test problem. Wedo not try to show that division is as important as the other operators of the relational algebra,but we hope that we are able to demonstrate that it is nevertheless a truly useful operator.AcknowledgementsI would like to thank several people who contributed to this work in special ways.First, I thank Prof.