ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Chordality Properties on Graphs and Minimal Conceptual Connections in Semantic Data Models.

Giorgio Ausiello, Alessandro D'Atri, Marina Moscarini: Chordality Properties on Graphs and Minimal Conceptual Connections in Semantic Data Models. PODS 1985: 164-170
@inproceedings{DBLP:conf/pods/AusielloDM85,
  author    = {Giorgio Ausiello and
               Alessandro D'Atri and
               Marina Moscarini},
  title     = {Chordality Properties on Graphs and Minimal Conceptual Connections
               in Semantic Data Models},
  booktitle = {Proceedings of the Fourth ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, March 25-27, 1985, Portland, Oregon},
  publisher = {ACM},
  year      = {1985},
  isbn      = {0-89791-153-9},
  pages     = {164-170},
  ee        = {http://doi.acm.org/10.1145/325405.325426, db/conf/pods/AusielloDM85.html},
  crossref  = {DBLP:conf/pods/85},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

In this paper the problem of finding a minimal connection among a set of objects which represent conceptual entities in a semantic data model is investigated. If we represent the conceptual structure of the reality by means of a k-partite graph this problem corresponds to finding a Steiner tree over a given set of nodes in the graph. 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 linear time. Furthermore it is shown that such chordality properties correspond to the concepts of acyclicity which are usually considered in the relational model of data.

Copyright © 1985 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Fourth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March 25-27, 1985, Portland, Oregon. ACM 1985, ISBN 0-89791-153-9
Contents BibTeX

Online Edition: ACM Digital Library

Journal Version

Giorgio Ausiello, Alessandro D'Atri, Marina Moscarini: Chordality Properties on Graphs and Minimal Conceptual Connections in Semantic Data Models. J. Comput. Syst. Sci. 33(2): 179-202(1986) BibTeX

References

[1]
...
[2]
...
[3]
Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis: On the Desirability of Acyclic Database Schemes. J. ACM 30(3): 479-513(1983) BibTeX
[4]
...
[5]
Alessandro D'Atri, Marina Moscarini: On the Recognition and Design of Acyclic Databases. PODS 1984: 1-8 BibTeX
[6]
Alessandro D'Atri, Marina Moscarini, Nicolas Spyratos: Answering Queries in Relational Databases. SIGMOD Conference 1983: 173-177 BibTeX
[7]
Ronald Fagin: Degrees of Acyclicity for Hypergraphs and Relational Database Schemes. J. ACM 30(3): 514-550(1983) BibTeX
[8]
M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX
[9]
...
[10]
David Maier, David Rozenshtein, David Scott Warren: Windows on the World. SIGMOD Conference 1983: 68-78 BibTeX
[11]
David Maier, Jeffrey D. Ullman: Connections in Acyclic Hypergraphs. Theor. Comput. Sci. 32: 185-199(1984) BibTeX
[12]
Robert Endre Tarjan, Mihalis Yannakakis: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs. SIAM J. Comput. 13(3): 566-579(1984) BibTeX
[13]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX
[14]
...
[15]
Joseph A. Wald, Paul G. Sorenson: Resolving the Query Inference Problem Using Steiner Trees. ACM Trans. Database Syst. 9(3): 348-368(1984) BibTeX

Referenced by

  1. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  2. Dirk Van Gucht: Interaction-Free Multivalued Dependency Sets. ICDT 1986: 409-420
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:33:47 2009