Symmetric Relations and Cardinality-Bounded Multisets in Database Systems

This chapter provides techniques that enable a database engine to support a symmetric table type. The techniques include: a nonredundant data structure with update methods and specialized indexes; methods for normalization in the presence of symmetric tables; an algebraic symmetric closure operator, together with algebraic equivalences useful for query optimization; inference methods to determine when a query/view is guaranteed to be symmetric; and a syntactic SQL extension to enable compact query expression. A symmetric table type allows database schema designers to model symmetric relationships without worrying about integrity, redundancy, consistency of updates, query efficiency, or suboptimal physical design. One could go even further and implement different kinds of symmetric table, such as the class of antireflexive symmetric relations satisfies simpler algebraic rules, and some duplicate elimination steps can be omitted in the implementation of the γ operator.