Chordality properties on graphs and minimal conceptual connections in semantic data models (Q579964): Difference between revisions
From MaRDI portal
Latest revision as of 12:14, 18 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Chordality properties on graphs and minimal conceptual connections in semantic data models |
scientific article |
Statements
Chordality properties on graphs and minimal conceptual connections in semantic data models (English)
0 references
1986
0 references
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.
0 references
relational databases
0 references
minimal connection among a set of objects
0 references
semantic data model
0 references
Steiner tree
0 references
bipartite graphs
0 references
chordality properties
0 references
acyclicity
0 references