Sven Hartmann, Uwe Leck
Matrix representations of participation constraints
Preprint series: Preprints aus dem Fachbereich Mathematik, Universität Rostock
68P15 Database theory
05C70 Factorization, matching, covering and packing
Abstract: We discuss the existence of matrix representations for generalized
and minimum participation constraints which are frequently used in
database design and conceptual modelling. Matrix representations,
also known as Armstrong relations, have been studied in literature
\eg for functional dependencies and play an important role in
example-based design and for the implication problem of database
constraints. The major tool to achieve the results in this paper
is a theorem of Hajnal and Szemer\'edi on the occurrence of clique
graphs in a given graph.
Keywords: participation constraints, matrix representation, Armstrong database, axiomatization, graph packing, clique graph