ACM SIGMOD Anthology TODS dblp.uni-trier.de

A Characterization of Globally Consistent Databases and Their Correct Access Paths.

Yehoshua Sagiv: A Characterization of Globally Consistent Databases and Their Correct Access Paths. ACM Trans. Database Syst. 8(2): 266-286(1983)
@article{DBLP:journals/tods/Sagiv83,
  author    = {Yehoshua Sagiv},
  title     = {A Characterization of Globally Consistent Databases and Their
               Correct Access Paths},
  journal   = {ACM Trans. Database Syst.},
  volume    = {8},
  number    = {2},
  year      = {1983},
  pages     = {266-286},
  ee        = {http://doi.acm.org/10.1145/319983.319988, db/journals/tods/Sagiv83.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

The representative instance is proposed as a representation of the data stored in a database whose relations are not the projections of a universal instance. Database schemes are characterized for which local consistency implies global consistency. (Local consistency means that each relation satisfies its own functional dependencies; global consistency means that the representative instance satisfies all the functional dependencies.) A method of efficiently computing projections of the representative instance is given, provided that local consistency implies global consistency. Throughout, it is assumed that a cover of the functional dependencies is embodied in the database scheme in the form of keys.

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.

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, Catriel Beeri, Jeffrey D. Ullman: The Theory of Joins in Relational Databases. ACM Trans. Database Syst. 4(3): 297-314(1979) BibTeX
[2]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Optimization of a Class of Relational Expressions. ACM Trans. Database Syst. 4(4): 435-454(1979) BibTeX
[3]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX
[4]
William Ward Armstrong: Dependency Structures of Data Base Relationships. IFIP Congress 1974: 580-583 BibTeX
[5]
Catriel Beeri, Philip A. Bernstein: Computational Problems Related to the Design of Normal Form Relational Schemas. ACM Trans. Database Syst. 4(1): 30-59(1979) BibTeX
[6]
Philip A. Bernstein: Synthesizing Third Normal Form Relations from Functional Dependencies. ACM Trans. Database Syst. 1(4): 277-298(1976) BibTeX
[7]
Philip A. Bernstein, Nathan Goodman: What does Boyce-Codd Normal Form Do? VLDB 1980: 245-259 BibTeX
[8]
Joachim Biskup, Umeshwar Dayal, Philip A. Bernstein: Synthesizing Independent Database Schemas. SIGMOD Conference 1979: 143-151 BibTeX
[9]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
[10]
E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX
[11]
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
[12]
Peter Honeyman: Extension Joins. VLDB 1980: 239-244 BibTeX
[13]
Peter Honeyman: Testing satisfaction of functional dependencies. J. ACM 29(3): 668-677(1982) BibTeX
[14]
Peter Honeyman, Richard E. Ladner, Mihalis Yannakakis: Testing the Universal Instance Assumption. Inf. Process. Lett. 10(1): 14-19(1980) BibTeX
[15]
...
[16]
...
[17]
Y. Edmund Lien: Multivalued Dependencies with Null Values in Relational Data Bases. VLDB 1979: 61-66 BibTeX
[18]
...
[19]
David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979) BibTeX
[20]
David Maier, Jeffrey D. Ullman: Maximal Objects and the Semantics of Universal Relation Databases. ACM Trans. Database Syst. 8(1): 1-14(1983) BibTeX
[21]
Sylvia L. Osborn: Towards a Universal Relation Interface. VLDB 1979: 52-60 BibTeX
[22]
Yehoshua Sagiv: Can We Use the Universal Instance Assumption Without Using Nulls? SIGMOD Conference 1981: 108-120 BibTeX
[23]
Yehoshua Sagiv, Mihalis Yannakakis: Equivalences Among Relational Expressions with the Union and Difference Operators. J. ACM 27(4): 633-655(1980) BibTeX
[24]
...
[25]
...
[26]
Yannis Vassiliou: Functional Dependencies and Incomplete Information. VLDB 1980: 260-269 BibTeX

Referenced by

  1. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  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. M. E. Iofinova: Updating Hierarchical Databases by Complex Forms. MFDBS 1991: 134-145
  7. Rom Langerak: View Updates in Relational Databases with an Independent Scheme. ACM Trans. Database Syst. 15(1): 40-66(1990)
  8. Ke Wang: Polynomial Time Designs toward Both BCNF and Efficient Data Manipulation. SIGMOD Conference 1990: 74-83
  9. Paolo Atzeni, Riccardo Torlone: Efficient Updates to Independent Schemes in the Weak Instance Model. SIGMOD Conference 1990: 84-93
  10. Paolo Atzeni, Edward P. F. Chan: Efficient Optimization of Simple Chase Join Expressions. ACM Trans. Database Syst. 14(2): 212-230(1989)
  11. Ke Wang: Can Constant-time Maintainability Be More Practical? PODS 1989: 120-127
  12. Paolo Atzeni, Riccardo Torlone: Updating Databases in the Weak Instance Model. PODS 1989: 101-109
  13. Lev A. Tenenbaum: Blocks and Projections' Synthesis in relational Databases. MFDBS 1989: 367-381
  14. Paolo Atzeni, Riccardo Torlone: Approaches to Updates over Weak Instances. MFDBS 1989: 12-23
  15. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  16. Volkert Brosda, Gottfried Vossen: Update and Retrieval in a Relational Database Through a Universal Schema Interface. ACM Trans. Database Syst. 13(4): 449-485(1988)
  17. Christophe Lécluse, Nicolas Spyratos: Implementing Queries and Updates on Universal Scheme Interfaces. VLDB 1988: 62-75
  18. Héctor J. Hernández, Edward P. F. Chan: A Characterization of Constant-time-mainteinability for BCNF Database Schemes. SIGMOD Conference 1988: 209-217
  19. Edward P. F. Chan, Héctor J. Hernández: Independence-reducible Database Schemes. PODS 1988: 163-173
  20. M. E. Iofinova, E. A. Komissartschik: Update in Hierarchical Data Bases. ICDT 1988: 292-306
  21. Mark Levene, George Loizou: A Universal Relation Model for Nested Relations. EDBT 1988: 294-308
  22. Paolo Atzeni, Edward P. F. Chan: Independent Database Schemes under Functional and Inclusion Dependencies. VLDB 1987: 159-166
  23. Jeffrey D. Ullman: Database Theory: Past and Future. PODS 1987: 1-10
  24. Alessandro D'Atri, Paolino Di Felice, Marina Moscarini: Dynamic Query Interpretation in Relational Databases. PODS 1987: 70-78
  25. 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
  26. Paolo Atzeni, Maria Cristina De Bernardis: A New Basis for the Weak Instance Model. PODS 1987: 79-86
  27. Alessandro D'Atri, Paolino Di Felice, V. S. Lakshmanan, Marina Moscarini: On Global Context Dependencies and their Properties. MFDBS 1987: 71-79
  28. Catriel Beeri, Michael Kifer: An Integrated Approach to Logical Design of Relational Database Schemes. ACM Trans. Database Syst. 11(2): 134-158(1986)
  29. Allen Van Gelder: A Message Passing Framework for Logical Query Evaluation. SIGMOD Conference 1986: 155-165
  30. Marc H. Graham, Ke Wang: Constant Time Maintenance or The Triumph of the fd. PODS 1986: 202-216
  31. Edward P. F. Chan, Héctor J. Hernández: On the Desirability of gamma-Acyclic BCNF Database Schemes. ICDT 1986: 105-122
  32. Gottfried Vossen, Volkert Brosda: A High-Level User Interface for Update and Retrieval in Relational Databases - Language Aspects. SIGMOD Conference 1985: 343-353
  33. Yehoshua Sagiv: On Computing Restricted Projections of Representative Instances. PODS 1985: 171-180
  34. Volkert Brosda, Gottfried Vossen: Updating a Relational Database through a Universal Schema Interface. PODS 1985: 66-75
  35. Paolo Atzeni, Edward P. F. Chan: Efficient Query Answering in the Representative Instance Approach. PODS 1985: 181-188
  36. Lynette I. Brady: A Universal Relation Assumption Based on Entities and Relationships. ER 1985: 208-215
  37. 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)
  38. Henry F. Korth, Gabriel M. Kuper, Joan Feigenbaum, Allen Van Gelder, Jeffrey D. Ullman: System/U: A Database System Based on the Universal Relation Assumption. ACM Trans. Database Syst. 9(3): 331-347(1984)
  39. Catriel Beeri, Michael Kifer: Comprehensive Approach to the Design of Relational Database Schemes. VLDB 1984: 196-207
  40. Edward P. F. Chan: Optimal Computation of Total Projections with Unions of Simple Chase Join Expressions. SIGMOD Conference 1984: 149-163
  41. Mihalis Yannakakis: Querying Weak Instances. PODS 1984: 275-280
  42. Jeffrey D. Ullman: On Kent's "Consequences of Assuming a Universal Relation". ACM Trans. Database Syst. 8(4): 637-643(1983)
  43. Robert Brown, Douglas Stott Parker Jr.: LAURA: A Formal Data Model and her Logical Design Methodology. VLDB 1983: 206-218
  44. David Maier, David Rozenshtein, David Scott Warren: Windows on the World. SIGMOD Conference 1983: 68-78
  45. Sharon McCure Kuck, Yehoshua Sagiv: Designing Globally Consistent Network Schemas. SIGMOD Conference 1983: 185-195
  46. Peter Honeyman, Edward Sciore: A New Characterization of Independence. SIGMOD Conference 1983: 92-96
  47. Edward Sciore: Improving Database Schemes by Adding Attributes. PODS 1983: 379-383
  48. David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
    Contents
  49. David Maier, David Scott Warren: Specifying Connections for a Universal Relation Scheme Database. SIGMOD Conference 1982: 1-7
  50. Jeffrey D. Ullman: The U. R. Strikes Back. PODS 1982: 10-22
  51. Marc H. Graham, Mihalis Yannakakis: Independent Database Schemas. PODS 1982: 199-204
  52. 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:51 2008