ACM SIGMOD Anthology TODS dblp.uni-trier.de

Database States and Their Tableaux.

Alberto O. Mendelzon: Database States and Their Tableaux. ACM Trans. Database Syst. 9(2): 264-282(1984)
@article{DBLP:journals/tods/Mendelzon84,
  author    = {Alberto O. Mendelzon},
  title     = {Database States and Their Tableaux},
  journal   = {ACM Trans. Database Syst.},
  volume    = {9},
  number    = {2},
  year      = {1984},
  pages     = {264-282},
  ee        = {http://doi.acm.org/10.1145/329.318579, db/journals/tods/Mendelzon84.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Recent work considers a database state to satisfy a set of dependencies if there exists a satisfying universal relation whose projections contain each of the relations in the state. Such relations are called weak instances for the state. We propose the set of all weak instances for a state as an embodiment of the information represented by the state. We characterize states that have the same set of weak instances by the equivalence of their associated tableaux. We apply this notion to the comparison of database schemes and characterize all pairs of schemes such that for every legal state of one of them there exists an equivalent legal state of the other one. We use this approach to provide a new characterization of Boyce-Codd Normal Form relation schemes.

Copyright © 1984 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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

References

[1]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX
[2]
Edward Babb: Joined Normal Form: A Storage Encoding for Relational Databases. ACM Trans. Database Syst. 7(4): 588-614(1982) BibTeX
[3]
Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Database Normalization Theory. VLDB 1978: 113-124 BibTeX
[4]
Catriel Beeri, Alberto O. Mendelzon, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalence of Relational Database Schemes. SIAM J. Comput. 10(2): 352-370(1981) BibTeX
[5]
...
[6]
Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX
[7]
E. F. Codd: Further Normalization of the Data Base Relational Model. IBM Research Report, San Jose, California RJ909: (1971) BibTeX
[8]
Ronald Fagin: Normal Forms and Relational Database Operators. SIGMOD Conference 1979: 153-160 BibTeX
[9]
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
[10]
Marc H. Graham: Functions in Databases. ACM Trans. Database Syst. 8(1): 81-109(1983) BibTeX
[11]
Marc H. Graham, Alberto O. Mendelzon: Notions of Dependency Satisfaction. PODS 1982: 177-188 BibTeX
[12]
Peter Honeyman: Testing satisfaction of functional dependencies. J. ACM 29(3): 668-677(1982) BibTeX
[13]
Sharon McCure Kuck, Yehoshua Sagiv: A Universal Relation Database System Implemented via the Network Model. PODS 1982: 147-157 BibTeX
[14]
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
[15]
David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979) BibTeX
[16]
David Maier, David Rozenshtein, Sharon C. Salveter, Jacob Stein, David Scott Warren: Toward Logical Data Independence: A Relational Query Language Without Relations. SIGMOD Conference 1982: 51-60 BibTeX
[17]
David Maier, Jeffrey D. Ullman, Moshe Y. Vardi: The Revenge of the JD. PODS 1983: 279-287 BibTeX
[18]
Jorma Rissanen: On Equivalences of Database Schemes. PODS 1982: 23-26 BibTeX
[19]
...
[20]
Yehoshua Sagiv: Can We Use the Universal Instance Assumption Without Using Nulls? SIGMOD Conference 1981: 108-120 BibTeX
[21]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX
[22]
...

Referenced by

  1. Gösta Grahne, Alberto O. Mendelzon: Tableau Techniques for Querying Information Sources through Global Schemas. ICDT 1999: 332-347
  2. Mark Levene, George Loizou: Semantics for Null Extended Nested Relations. ACM Trans. Database Syst. 18(3): 414-459(1993)
  3. Ke Wang, Marc H. Graham: Constant-Time Maintainability: A Generalization of Independence. ACM Trans. Database Syst. 17(2): 201-246(1992)
  4. Paolo Atzeni, Riccardo Torlone: Updating Relational Databases Through Weak Instance Interfaces. ACM Trans. Database Syst. 17(4): 718-745(1992)
  5. Héctor J. Hernández, Edward P. F. Chan: Constant-Time-Maintainable BCNF Database Schemes. ACM Trans. Database Syst. 16(4): 571-599(1991)
  6. Ke Wang: Polynomial Time Designs toward Both BCNF and Efficient Data Manipulation. SIGMOD Conference 1990: 74-83
  7. Paolo Atzeni, Riccardo Torlone: Efficient Updates to Independent Schemes in the Weak Instance Model. SIGMOD Conference 1990: 84-93
  8. Paolo Atzeni, Edward P. F. Chan: Efficient Optimization of Simple Chase Join Expressions. ACM Trans. Database Syst. 14(2): 212-230(1989)
  9. Ke Wang: Can Constant-time Maintainability Be More Practical? PODS 1989: 120-127
  10. Paolo Atzeni, Riccardo Torlone: Updating Databases in the Weak Instance Model. PODS 1989: 101-109
  11. Paolo Atzeni, Riccardo Torlone: Approaches to Updates over Weak Instances. MFDBS 1989: 12-23
  12. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  13. Christophe Lécluse, Nicolas Spyratos: Implementing Queries and Updates on Universal Scheme Interfaces. VLDB 1988: 62-75
  14. Héctor J. Hernández, Edward P. F. Chan: A Characterization of Constant-time-mainteinability for BCNF Database Schemes. SIGMOD Conference 1988: 209-217
  15. Edward P. F. Chan, Héctor J. Hernández: Independence-reducible Database Schemes. PODS 1988: 163-173
  16. Jeffrey D. Ullman: Database Theory: Past and Future. PODS 1987: 1-10
  17. Edward P. F. Chan, Héctor J. Hernández: On Designing Database Schemes Bounded or Constant-time-maintainable with respect to Functional Dependencies. PODS 1987: 48-57
  18. Paolo Atzeni, Maria Cristina De Bernardis: A New Basis for the Weak Instance Model. PODS 1987: 79-86
  19. Edward P. F. Chan, Paolo Atzeni: On the Properties and Characterization of Connection-tap-free Schemes. PODS 1986: 140-147
  20. Edward P. F. Chan, Héctor J. Hernández: On the Desirability of gamma-Acyclic BCNF Database Schemes. ICDT 1986: 105-122
  21. Yehoshua Sagiv: On Computing Restricted Projections of Representative Instances. PODS 1985: 171-180
  22. David Maier, Jeffrey D. Ullman, Moshe Y. Vardi: On the Foundations of the Universal Relation Model. ACM Trans. Database Syst. 9(2): 283-308(1984)
  23. Jeffrey D. Ullman: On Kent's "Consequences of Assuming a Universal Relation". ACM Trans. Database Syst. 8(4): 637-643(1983)
  24. David Maier, David Rozenshtein, David Scott Warren: Windows on the World. SIGMOD Conference 1983: 68-78
  25. Tomasz Imielinski, Witold Lipski Jr.: Inverting Relational Expressions - A Uniform and Natural Technique for Various Database Problems. PODS 1983: 305-311
  26. David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
    Contents
  27. Jeffrey D. Ullman: The U. R. Strikes Back. PODS 1982: 10-22
  28. Jorma Rissanen: On Equivalences of Database Schemes. PODS 1982: 23-26
  29. Marc H. Graham, Mihalis Yannakakis: Independent Database Schemas. PODS 1982: 199-204
  30. Marc H. Graham, Alberto O. Mendelzon: Notions of Dependency Satisfaction. PODS 1982: 177-188
  31. Marco A. Casanova: A Theory of Data Dependencies over Relational Expressions. PODS 1982: 189-198
  32. Paolo Atzeni, Douglas Stott Parker Jr.: Assumptions in Relational Database Theory. PODS 1982: 1-9
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:38:54 2008