Independent and Separable Database Schemes.

Edward P. F. Chan, Alberto O. Mendelzon: Independent and Separable Database Schemes. PODS 1983: 288-296
  author    = {Edward P. F. Chan and
               Alberto O. Mendelzon},
  title     = {Independent and Separable Database Schemes},
  booktitle = {Proceedings of the Second ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, March 21-23, 1983, Colony Square Hotel,
               Atlanta, Georgia},
  publisher = {ACM},
  year      = {1983},
  isbn      = {0-89791-097-4},
  pages     = {288-296},
  ee        = {, db/conf/pods/ChanM83.html},
  crossref  = {DBLP:conf/pods/83},
  bibsource = {DBLP,}


We propose and investigate the notion of separability to capture the design goal of independently updatable decompositions. As evidence in favor of separability as a natural concept of independence, we show that it is equivalent to a specialization of the abstract independent mappings defined by Bancilhon and Spyratos. We then characterize separable schemes in the important case when the only constraints given are a set of functional dependencies and the join dependency for the database scheme. This characterization is also applicable to dependency preserving database schemes when a set of functional dependencies is given as constraint. Our characterization yields a polynomial-time algorithm for testing separability in these cases.

Copyright © 1983 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 Second ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March 21-23, 1983, Colony Square Hotel, Atlanta, Georgia. ACM 1983, ISBN 0-89791-097-4
Contents BibTeX

Online Edition: ACM Digital Library


Catriel Beeri, Alberto O. Mendelzon, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalence of Relational Database Schemes. SIAM J. Comput. 10(2): 352-370(1981) BibTeX
François Bancilhon, Nicolas Spyratos: Independent Components of Databases. VLDB 1981: 398-408 BibTeX
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
Ronald Fagin, Alberto O. Mendelzon, Jeffrey D. Ullman: A Simplified Universal Relation Assumption and Its Properties. ACM Trans. Database Syst. 7(3): 343-360(1982) BibTeX
Marc H. Graham, Alberto O. Mendelzon: Notions of Dependency Satisfaction. PODS 1982: 177-188 BibTeX
Marc H. Graham, Mihalis Yannakakis: Independent Database Schemas. PODS 1982: 199-204 BibTeX
Peter Honeyman: Testing satisfaction of functional dependencies. J. ACM 29(3): 668-677(1982) BibTeX
David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979) BibTeX
David Maier, Alberto O. Mendelzon, Fereidoon Sadri, Jeffrey D. Ullman: Adequacy of Decompositions of Relational Databases. J. Comput. Syst. Sci. 21(3): 368-379(1980) BibTeX
Jorma Rissanen: Independent Components of Relations. ACM Trans. Database Syst. 2(4): 317-325(1977) BibTeX
Yehoshua Sagiv: Can We Use the Universal Instance Assumption Without Using Nulls? SIGMOD Conference 1981: 108-120 BibTeX
Moshe Y. Vardi: On Decomposition of Relational Databases. FOCS 1982: 176-185 BibTeX

Referenced by

  1. Edward A. Komissartschik: Restructuring and Dependencies in Databases. MFDBS 1989: 269-284
  2. Georg Gottlob, Paolo Paolini, Roberto Zicari: Properties and Update Semantics of Consistent Views. ACM Trans. Database Syst. 13(4): 486-524(1988)
  3. James P. Delgrande: Formal Limits on the Automatic Generation and Maintenance of Integrity Constraints. PODS 1987: 190-196
  4. Paolo Atzeni, Edward P. F. Chan: Efficient Query Answering in the Representative Instance Approach. PODS 1985: 181-188
  5. Edward P. F. Chan: Optimal Computation of Total Projections with Unions of Simple Chase Join Expressions. SIGMOD Conference 1984: 149-163
  6. Kent Laver, Alberto O. Mendelzon, Marc H. Graham: Functional Dependencies on Cyclic Database Schemes. SIGMOD Conference 1983: 79-91
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:33:43 2009