Symmetric Relations and Cardinality-Bounded Multisets in Database Systems

Kenneth A. Ross, Julia Stoyanovich

    Research output: Chapter in Book/Report/Conference proceedingChapter


    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.

    Original languageEnglish (US)
    Title of host publicationProceedings 2004 VLDB Conference
    Subtitle of host publicationThe 30th International Conference on Very Large Databases (VLDB)
    Number of pages12
    ISBN (Electronic)9780120884698
    StatePublished - Jan 1 2004

    ASJC Scopus subject areas

    • General Computer Science


    Dive into the research topics of 'Symmetric Relations and Cardinality-Bounded Multisets in Database Systems'. Together they form a unique fingerprint.

    Cite this