Sven Hartmann, Uwe Leck
Matrix representations of participation constraints
Preprint series: Preprints aus dem Fachbereich Mathematik, Universität Rostock

MSC:

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