Algebraic support for complex objects with arrays, identity, and inheritance
Scott L. Vandenberg, David J. DeWitt · 1991
Algebraic query processing and optimization for relational databases is a proven and reasonably well-understood technology.Recently the algebraic approach has been extended to more advanced data models (nested relations, complex objects, object-oriented systems).Here we continue this evolution by presenting novel algebraic operators and transformations supporting grouping, arrays, references, and multisets.We also propose a new approach to processing and optimizing overridden methods in the presence of multiple inheritance.The utility of Lxsth the algebraic operators and the transformation rules is demonstrated with examples.Object identity is incorporated into the algebraic domains, giving an original, intuitive set-theoretic semantics for the domains of object identifiers in the presence of multiple inheritance.We prove that the algebra is eqtripollent to the QUEL-like user-level query language and discuss some other expressiveness issues.