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

Partition Semantics for Relations.

Stavros S. Cosmadakis, Paris C. Kanellakis, Nicolas Spyratos: Partition Semantics for Relations. PODS 1985: 261-275
@inproceedings{DBLP:conf/pods/CosmadakisKS85,
  author    = {Stavros S. Cosmadakis and
               Paris C. Kanellakis and
               Nicolas Spyratos},
  title     = {Partition Semantics for Relations},
  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     = {261-275},
  ee        = {http://doi.acm.org/10.1145/325405.325452, db/conf/pods/CosmadakisKS85.html},
  crossref  = {DBLP:conf/pods/85},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Set-theoretic partitions were first used in [15] to provide models for relation schemes, relations and dependencies. This new point of view of the relational model demonstrates that there is a natural extension of functional dependencies (FD's), which is based on the duality between product and sum of partitions. We show that these partition dependencies (PD's) have the power to express both functional determination and transitive closure of undirected graphs. The inference problem of PD's is shown to be the uniform word problem in a lattice. We provide a polynomial time algorithm for this natural generalization of the FD inference problem. We show how partition semantics justify a number of variants of the weak instance assumption and investigate the expressive power of PD's. We also provide a polynomial time test for consistency of a set of relations with a set of PD's.

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

Stavros S. Cosmadakis, Paris C. Kanellakis, Nicolas Spyratos: Partition Semantics for Relations. J. Comput. Syst. Sci. 33(2): 203-233(1986) BibTeX

References

[1]
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX
[2]
Catriel Beeri, Moshe Y. Vardi: Formal Systems for Tuple and Equality Generating Dependencies. SIAM J. Comput. 13(1): 76-98(1984) BibTeX
[3]
...
[4]
...
[5]
Ronald Fagin: Horn clauses and database dependencies. J. ACM 29(4): 952-985(1982) BibTeX
[6]
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
[7]
...
[8]
Peter Honeyman: Testing satisfaction of functional dependencies. J. ACM 29(3): 668-677(1982) BibTeX
[9]
John E. Hopcroft, Jeffrey D. Ullman: Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979, ISBN 0-201-02988-X
BibTeX
[10]
...
[11]
Dexter Kozen: Complexity of Finitely Presented Algebras. STOC 1977: 164-177 BibTeX
[12]
David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX
[13]
...
[14]
Fereidoon Sadri, Jeffrey D. Ullman: Template Dependencies: A Large Class of Dependencies in Relational Databases and Its Complete Axiomatization. J. ACM 29(2): 363-372(1982) BibTeX
[15]
...
[16]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX
[17]
...
[18]
...
[19]
Mihalis Yannakakis, Christos H. Papadimitriou: Algebraic Dependencies. J. Comput. Syst. Sci. 25(1): 2-41(1982) BibTeX

Referenced by

  1. Dominique Laurent, Nicolas Spyratos: A Partition Model Approach to Updating Universal Scheme Interfaces. IEEE Trans. Knowl. Data Eng. 6(2): 316-330(1994)
  2. Chris Tuijn, Marc Gyssens: Views and Decompositions of Databases from a Categorical Perspective. ICDT 1992: 99-112
  3. Christophe Lécluse, Nicolas Spyratos: Implementing Queries and Updates on Universal Scheme Interfaces. VLDB 1988: 62-75
  4. Dominique Laurent, Nicolas Spyratos: Partition Semantics for Incomplete Information in Relational Databases. SIGMOD Conference 1988: 66-73
  5. Nicolas Spyratos, Christophe Lécluse: Incorporating Functional Dependencies in Deductive Query Answering. ICDE 1987: 658-664
  6. Moshe Y. Vardi: On the Integrity of Databases with Incomplete Information. PODS 1986: 252-266
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:48 2009