On the Equivalence of Nested Relational Languages

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.Computer ScienceSoftware TechnologyElectrical Engineering, Mathematics and Computer Scienc