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

DOI10.1016/0022-0000(86)90018-8MaRDI QIDQ579964zbMATH OpenOpenAlexFDO

Authors Giorgio Ausiello, Alessandro D'Atri

Publication date 1986

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(86)90018-8

zbMATH Keywords

acyclicitybipartite graphschordality propertiesminimal connection among a set of objectsrelational databasessemantic data modelSteiner tree

Mathematics Subject Classification ID

Data structures (68P05) Information storage and retrieval of data (68P20) Graph theory (including graph drawing) in computer science (68R10)

Review text

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.

Recommendations

• Semantic acyclicity on graph databases
• Characterizations and algorithmic applications of chordal graph embeddings
• scientific article; zbMATH DE number 4198043
• Chordal graph models of contingency tables
• scientific article; zbMATH DE number 1670898
• scientific article; zbMATH DE number 1670897
• On the chordality of a graph
• scientific article; zbMATH DE number 1533810

Cites work

• Connections in acyclic hypergraphs
• Degrees of acyclicity for hypergraphs and relational database schemes
• scientific article; zbMATH DE number 3839362 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3890770 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On the Desirability of Acyclic Database Schemes
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Steiner trees, connected domination and strongly chordal graphs

Cited in

(17)

• On hypergraph acyclicity and graph chordality
• On-line computation of minimal and maximal length paths
• Problems with generalized Steiner problems
• A fast algorithm for query optimization in universal-relation databases
• Alternating cycle-free matchings
• A parallel algorithm for computing Steiner trees in strongly chordal graphs
• A distributed algorithm for determining minimal covers of acyclic database schemes
• On stable cutsets in graphs
• Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
• An algorithm for determining minimal reduced-coverings of acyclic database schemes
• Coding theory motivated by relational databases
• An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
• Distance Hereditary Graphs and the Interlace Polynomial
• Dually chordal graphs
• Polynomial time algorithms for Hamiltonian problems on bipartite distance-hereditary graphs
• Recognizing different types of beta-cycles in a database scheme
• On locally presented posets

This page was built for publication: Chordality properties on graphs and minimal conceptual connections in semantic data models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q579964)