Testing Implications of Data Dependencies.

@article{DBLP:journals/tods/MaierMS79,
  author    = {David Maier and
               Alberto O. Mendelzon and
               Yehoshua Sagiv},
  title     = {Testing Implications of Data Dependencies},
  journal   = {ACM Trans. Database Syst.},
  volume    = {4},
  number    = {4},
  year      = {1979},
  pages     = {455-469},
  ee        = {http://doi.acm.org/10.1145/320107.320115, db/journals/tods/MaierMS79.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1979 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

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An3-1 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

References

[1]

Alfred V. Aho, Catriel Beeri, Jeffrey D. Ullman: The Theory of Joins in Relational Data Bases (Extended Abstract). FOCS 1977: 107-113 BibTeX

[2]

Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX

[3]

William Ward Armstrong: Dependency Structures of Data Base Relationships. IFIP Congress 1974: 580-583 BibTeX

[4]

Catriel Beeri: On the Membership Problem for Functional and Multivalued Dependencies in Relational Databases. ACM Trans. Database Syst. 5(3): 241-259(1980) BibTeX

[5]

...

[6]

Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Database Normalization Theory. VLDB 1978: 113-124 BibTeX

[7]

Catriel Beeri, Ronald Fagin, John H. Howard: A Complete Axiomatization for Functional and Multivalued Dependencies in Database Relations. SIGMOD Conference 1977: 47-61 BibTeX

[8]

Catriel Beeri, Alberto O. Mendelzon, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalence of Relational Database Schemes. STOC 1979: 319-329 BibTeX

[9]

Philip A. Bernstein: Synthesizing Third Normal Form Relations from Functional Dependencies. ACM Trans. Database Syst. 1(4): 277-298(1976) BibTeX

[10]

Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX

[11]

E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX

[12]

...

[13]

Ronald Fagin: Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Trans. Database Syst. 2(3): 262-278(1977) BibTeX

[14]

Ronald Fagin: Normal Forms and Relational Database Operators. SIGMOD Conference 1979: 153-160 BibTeX

[15]

Kenichi Hagihara, Minoru Ito, Kenichi Taniguchi, Tadao Kasami: Decision Problems for Multivalued Dependencies in Relational Databases. SIAM J. Comput. 8(2): 247-264(1979) BibTeX

[16]

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

[17]

Jorma Rissanen: Independent Components of Relations. ACM Trans. Database Syst. 2(4): 317-325(1977) BibTeX

[18]

Jorma Rissanen: Theory of Relations for Databases - A Tutorial Survey. MFCS 1978: 536-551 BibTeX

[19]

...

[20]

...

Referenced by

1. Mark Levene, George Loizou: Database Design for Incomplete Relations. ACM Trans. Database Syst. 24(1): 80-125(1999)
2. Kenneth A. Ross, Surajit Chaudhuri, Gösta Grahne, H. V. Jagadish, Jan Van den Bussche, Moshe Y. Vardi: Reminiscences on Influential Papers. SIGMOD Record 28(4): 39-41(1999)
3. Carmem S. Hara, Susan B. Davidson: Reasoning about Nested Functional Dependencies. PODS 1999: 91-100
4. Lucian Popa, Val Tannen: An Equational Chase for Path-Conjunctive Queries, Constraints, and Views. ICDT 1999: 39-57
5. Joachim Biskup, Andreas Kluck: A New Approach to Inferences of Semantic Constraints. ADBIS 1997: 72-79
6. Marc Andries, Luca Cabibbo, Jan Paredaens, Jan Van den Bussche: Applying an Update Method to a Set of Receivers. PODS 1995: 208-218
7. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
   Contents
8. Yehoshua Sagiv, Oded Shmueli: Solving Queries by Tree Projections. ACM Trans. Database Syst. 18(3): 487-511(1993)
9. Mark Levene, George Loizou: Semantics for Null Extended Nested Relations. ACM Trans. Database Syst. 18(3): 414-459(1993)
10. Paolo Atzeni, Riccardo Torlone: Updating Relational Databases Through Weak Instance Interfaces. ACM Trans. Database Syst. 17(4): 718-745(1992)
11. Héctor J. Hernández, Edward P. F. Chan: Constant-Time-Maintainable BCNF Database Schemes. ACM Trans. Database Syst. 16(4): 571-599(1991)
12. Ke Wang: Polynomial Time Designs toward Both BCNF and Efficient Data Manipulation. SIGMOD Conference 1990: 74-83
13. Paolo Atzeni, Riccardo Torlone: Efficient Updates to Independent Schemes in the Weak Instance Model. SIGMOD Conference 1990: 84-93
14. Paolo Atzeni, Edward P. F. Chan: Efficient Optimization of Simple Chase Join Expressions. ACM Trans. Database Syst. 14(2): 212-230(1989)
15. Paolo Atzeni, Riccardo Torlone: Updating Databases in the Weak Instance Model. PODS 1989: 101-109
16. Victor Vianu, Gottfried Vossen: Goal-Oriented Concurrency Control. MFDBS 1989: 398-414
17. Georg Gottlob, Michael Schrefl, Markus Stumptner: On the Interaction between Transitive Closure and Functional Dependencies. MFDBS 1989: 187-206
18. Paolo Atzeni, Riccardo Torlone: Approaches to Updates over Weak Instances. MFDBS 1989: 12-23
19. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
20. K. V. S. V. N. Raju, Arun K. Majumdar: Fuzzy Functional Dependencies and Lossless Join Decomposition of Fuzzy Relational Database Systems. ACM Trans. Database Syst. 13(2): 129-166(1988)
21. Héctor J. Hernández, Edward P. F. Chan: A Characterization of Constant-time-mainteinability for BCNF Database Schemes. SIGMOD Conference 1988: 209-217
22. Serge Abiteboul, Richard Hull: Data Functions, Datalog and Negation (Extended Abstract). SIGMOD Conference 1988: 143-153
23. Edward P. F. Chan, Héctor J. Hernández: Independence-reducible Database Schemes. PODS 1988: 163-173
24. Victor Vianu, Gottfried Vossen: Conceptual Level Concurrency Control of Relational Update Transactions. ICDT 1988: 353-367
25. Mark Levene, George Loizou: A Universal Relation Model for Nested Relations. EDBT 1988: 294-308
26. Yehoshua Sagiv: Optimizing Datalog Programs. PODS 1987: 349-362
27. 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
28. Paolo Atzeni, Maria Cristina De Bernardis: A New Basis for the Weak Instance Model. PODS 1987: 79-86
29. Serge Abiteboul, Victor Vianu: A Transcation Language Complete for Database Update and Specification. PODS 1987: 260-268
30. Paolo Atzeni, Douglas Stott Parker Jr.: Algorithms for Set Containment Inference. DBPL 1987: 117-127
31. Marc Gyssens: On the Complexity of Join Dependencies. ACM Trans. Database Syst. 11(1): 81-108(1986)
32. Yehoshua Sagiv, Oded Shmueli: On Finite FD-Acyclicity. PODS 1986: 173-182
33. Yehoshua Sagiv, Oded Shmueli: The Equivalence of Solving Queries and Production Tree Projections. PODS 1986: 160-172
34. Edward P. F. Chan, Paolo Atzeni: On the Properties and Characterization of Connection-tap-free Schemes. PODS 1986: 140-147
35. Peter Thanisch, George Loizou: A Polynomial-Time Join Dependency Implication Algorithm for Multi-Valued Dependencies. ICDT 1986: 397-408
36. Dirk Van Gucht: Interaction-Free Multivalued Dependency Sets. ICDT 1986: 409-420
37. Edward P. F. Chan, Héctor J. Hernández: On the Desirability of gamma-Acyclic BCNF Database Schemes. ICDT 1986: 105-122
38. Aviel Klausner, Nathan Goodman: Multirelations - Semantice and Languages. VLDB 1985: 251-258
39. Serge Abiteboul, Gösta Grahne: Update Semantics for Incomplete Databases. VLDB 1985: 1-12
40. Jacob Stein, David Maier: Relaxing the Universal Relation Scheme Assumption. PODS 1985: 76-84
41. Yehoshua Sagiv: On Computing Restricted Projections of Representative Instances. PODS 1985: 171-180
42. Marc Gyssens: Embedded Join Dependencies as a Tool for Decomposing Full Join Dependencies. PODS 1985: 205-214
43. Paolo Atzeni, Edward P. F. Chan: Efficient Query Answering in the Representative Instance Approach. PODS 1985: 181-188
44. Alberto O. Mendelzon: Database States and Their Tableaux. ACM Trans. Database Syst. 9(2): 264-282(1984)
45. 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)
46. Hirofumi Katsuno: An Extension of Conflict-Free Multivalued Dependency Sets. ACM Trans. Database Syst. 9(2): 309-326(1984)
47. Hervé Gallaire, Jack Minker, Jean-Marie Nicolas: Logic and Databases: A Deductive Approach. ACM Comput. Surv. 16(2): 153-185(1984)
48. Gösta Grahne: Dependency Satisfaction in Databases with Incomplete Information. VLDB 1984: 37-45
49. Edward P. F. Chan: Optimal Computation of Total Projections with Unions of Simple Chase Join Expressions. SIGMOD Conference 1984: 149-163
50. Mihalis Yannakakis: Querying Weak Instances. PODS 1984: 275-280
51. Domenico Saccà, F. Manfredi, A. Mecchia: Properties of Database Schemata with Functional Dependencies. PODS 1984: 19-28
52. Marc Gyssens, Jan Paredaens: On the Decomposition of Join Dependencies. PODS 1984: 143-152
53. Yehoshua Sagiv: A Characterization of Globally Consistent Databases and Their Correct Access Paths. ACM Trans. Database Syst. 8(2): 266-286(1983)
54. David Maier, Jeffrey D. Ullman: Maximal Objects and the Semantics of Universal Relation Databases. ACM Trans. Database Syst. 8(1): 1-14(1983)
55. Marc H. Graham: Functions in Databases. ACM Trans. Database Syst. 8(1): 81-109(1983)
56. David Maier, David Rozenshtein, David Scott Warren: Windows on the World. SIGMOD Conference 1983: 68-78
57. Kent Laver, Alberto O. Mendelzon, Marc H. Graham: Functional Dependencies on Cyclic Database Schemes. SIGMOD Conference 1983: 79-91
58. Sharon McCure Kuck, Yehoshua Sagiv: Designing Globally Consistent Network Schemas. SIGMOD Conference 1983: 185-195
59. Tomasz Imielinski, Witold Lipski Jr.: Incomplete Information and Dependencies in Relational Databases. SIGMOD Conference 1983: 178-184
60. Domenico Saccà: On the Recognition of Coverings of Acyclic Database Hypergraphs. PODS 1983: 297-304
61. David Maier, Jeffrey D. Ullman, Moshe Y. Vardi: The Revenge of the JD. PODS 1983: 279-287
62. Tomasz Imielinski, Witold Lipski Jr.: Inverting Relational Expressions - A Uniform and Natural Technique for Various Database Problems. PODS 1983: 305-311
63. Stephen J. Hegner: Algebraic Aspects of Relational Database Decomposition. PODS 1983: 400-413
64. Marc H. Graham: Path Expressions in Databases. PODS 1983: 366-378
65. Stavros S. Cosmadakis, Christos H. Papadimitriou: Updates of Relational Views. PODS 1983: 317-331
66. Edward P. F. Chan, Alberto O. Mendelzon: Independent and Separable Database Schemes. PODS 1983: 288-296
67. David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
    Contents
68. Carlo Zaniolo: A New Normal Form for the Design of Relational Database Schemata. ACM Trans. Database Syst. 7(3): 489-499(1982)
69. Anthony C. Klug, Rod Price: Determining View Dependencies Using Tableaux. ACM Trans. Database Syst. 7(3): 361-380(1982)
70. Barry E. Jacobs, Alan R. Aronson, Anthony C. Klug: On Interpretations of Relational Languages and Solutions to the Implied Constraint Problem. ACM Trans. Database Syst. 7(2): 291-315(1982)
71. 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)
72. Tomasz Imielinski, Witold Lipski Jr.: A Technique for Translating States Between Database Schemata. SIGMOD Conference 1982: 61-68
73. Moshe Y. Vardi: The Implication and Finite Implication Problems for Typed Template Dependencies. PODS 1982: 230-238
74. Sharon McCure Kuck, Yehoshua Sagiv: A Universal Relation Database System Implemented via the Network Model. PODS 1982: 147-157
75. David S. Johnson, Anthony C. Klug: Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies. PODS 1982: 164-169
76. Marc H. Graham, Alberto O. Mendelzon: Notions of Dependency Satisfaction. PODS 1982: 177-188
77. Nathan Goodman, Oded Shmueli: The Tree Property is Fundamental for Query Processing. PODS 1982: 40-48
78. Marco A. Casanova: A Theory of Data Dependencies over Relational Expressions. PODS 1982: 189-198
79. Ronald Fagin: A Normal Form for Relational Databases That Is Based on Domians and Keys. ACM Trans. Database Syst. 6(3): 387-415(1981)
80. Mihalis Yannakakis: Algorithms for Acyclic Database Schemes. VLDB 1981: 82-94
81. Katsumi Tanaka, Yahiko Kambayashi: Logical Integration of Locally Independent Relational Databases into a Distributed Database. VLDB 1981: 131-141
82. Hervé Gallaire: Impacts of Logic and Databases (Invited Paper). VLDB 1981: 248-259
83. Edward Sciore: Real-World MVD's. SIGMOD Conference 1981: 121-132
84. Yehoshua Sagiv: Can We Use the Universal Instance Assumption Without Using Nulls? SIGMOD Conference 1981: 108-120
85. Peter Honeyman: Extension Joins. VLDB 1980: 239-244
86. Fereidoon Sadri, Jeffrey D. Ullman: The Interaction between Functional Dependencies and Template Dependencies. SIGMOD Conference 1980: 45-51
87. Douglas Stott Parker Jr., Kamran Parsaye-Ghomi: Inferences Involving Embedded Multivalued Dependencies and Transitive Dependencies. SIGMOD Conference 1980: 52-57
88. 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)
89. Alberto O. Mendelzon, David Maier: Generalized Mutual Dependencies and the Decomposition of Database Relations. VLDB 1979: 75-82