Print Email Facebook Twitter On the Equivalence of Nested Relational Languages Title On the Equivalence of Nested Relational Languages Author Prasad, G. Contributor Hidders, A.J.H. (mentor) Faculty Electrical Engineering, Mathematics and Computer Science Department Software Technology Programme Computer Science Date 2014-03-31 Abstract Query optimization has played a vital role in database research since the 1970’s and up till now. In the relational context, a prerequisite to query optimization is the study of equivalences over relational algebra expressions. Sophisticated techniques for query transformations for traditional query languages include rewriting based optimizations. Rewriting optimization transforms a query into equivalent one and can have a significant impact on execution time. Though RDF Gears is an inspiration to this work, we aim to develop rewriting based optimization strategies that can be applied to similar query languages like PigLatin and Hive. We study the various rewriting based optimizations that currently exist and identify many of the existing ideas that can be extrapolated and applied to RDF Gears. We define the syntax and semantics of Nested Relational Algebra(NRA) and Nested Relational Calculus(NRC) and use a mapping between them to transform expressions of one to the other. We come up with a full set of NRA & NRC, an exhaustive list of rewrite rules, which cover all possible rewrites needed for our language. We mathematically find a minimum core set, that we call the concise or the non-derivable set of NRA & NRC and prove their derivability either mathematically or using a theorem prover. We also present a mathematical proof for equivalence relationship between the rule sets of NRA & NRC. The proof obtained for NRA & NRC that is comprised of basic values, pairs and tuples, for one free variable. Subject Nested Relational CalculusNested Relational AlgebraRDF gearsdatabase To reference this document use: http://resolver.tudelft.nl/uuid:d0b5c0b9-356f-4852-ba98-f3703831daf6 Embargo date 2014-03-23 Part of collection Student theses Document type master thesis Rights (c) 2014 Prasad, G. Files PDF Thesis_GargiPrasad.pdf 654.82 KB Close viewer /islandora/object/uuid:d0b5c0b9-356f-4852-ba98-f3703831daf6/datastream/OBJ/view