A Membership Algorithm for Functional and Multi-valued Dependencies in the Presence of Lists

Abstract

Nested lists are used as a data structure whenever order matters. List types are therefore supported by many advanced data models such as genomic sequence, deductive and object-oriented data models including XML. What impact does the finite list type have on the two most important classes of relational dependencies? The membership problem of functional and multi-valued dependencies in databases supporting base, record and list types is investigated. The problem is to decide whether a functional or multi-valued dependency follows from a given set of functional and multi-valued dependencies. In order to capture different data models at a time, an abstract algebraic approach based on nested attributes and subtyping is taken. This algebraic framework allows to generalise Beeri's well-known membership algorithm in [Transactions on Database Systems 5 (3) (1980) 241] from the relational data model. It is argued that the algorithm presented works correctly and in polynomial time.