Chordality properties on graphs and minimal conceptual connections in semantic data models

摘要

In this paper the problem of finding a minimal connection among a set of objects that represent conceptual entities in a semantic data model is investigated. If we represent the conceptual structure of reality by means of a graph this problem corresponds to finding a Steiner tree over a given set of nodes. In this paper the case of bipartite graphs is considered and it is shown that, if the bipartite graphs satisfy suitable chordality properties, the Steiner problem may be solved in polynomial time. Furthermore, it is shown that such chordality properties correspond to the concepts of acyclicity that are usually considered in the relational model of data.