Determining View Dependencies Using Tableaux.

@article{DBLP:journals/tods/KlugP82,
  author    = {Anthony C. Klug and
               Rod Price},
  title     = {Determining View Dependencies Using Tableaux},
  journal   = {ACM Trans. Database Syst.},
  volume    = {7},
  number    = {3},
  year      = {1982},
  pages     = {361-380},
  ee        = {http://doi.acm.org/10.1145/319732.319738, db/journals/tods/KlugP82.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A relational database models some part of the real world by a set of relations and a set of constraints. The constraints model properties of the stored information and must be maintained true at all times. For views defined over physically stored (base) relations, this is done by determining whether the view constraints are logical consequences of base relation constraints. A technique for determining such valid view constraints is presented in this paper. A generalization of the tableau chase is used. The idea of the method is to generate a tableau for the expression whose summary violates the test constraint in a "canonical" way. The chase then tries to remove this violation.

It is also shown how this method has applications to schema design. Relations not in normal form or having other deficiencies can be replaced by normal form projections without losing the ability to represent all constraint information.

Copyright © 1982 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 Databases. ACM Trans. Database Syst. 4(3): 297-314(1979) BibTeX

[2]

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

[3]

Catriel Beeri, Moshe Y. Vardi: The Implication Problem for Data Dependencies. ICALP 1981: 73-85 BibTeX

[4]

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

[5]

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

[6]

Philip A. Bernstein, Nathan Goodman: What does Boyce-Codd Normal Form Do? VLDB 1980: 245-259 BibTeX

[7]

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

[8]

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

[9]

E. F. Codd: Relational Completeness of Data Base Sublanguages. In: R. Rustin (ed.): Database Systems: 65-98, Prentice Hall and IBM Research Report RJ 987, San Jose, California : (1972) BibTeX

[10]

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

[11]

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

[12]

...

[13]

John Grant, Barry E. Jacobs: On the family of generalized dependency constraints. J. ACM 29(4): 986-997(1982) BibTeX

[14]

Patricia P. Griffiths, Bradford W. Wade: An Authorization Mechanism for a Relational Database System. ACM Trans. Database Syst. 1(3): 242-255(1976) BibTeX

[15]

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) BibTeX

[16]

Anthony C. Klug: Calculating Constraints on Relational Expressions. ACM Trans. Database Syst. 5(3): 260-290(1980) BibTeX

[17]

...

[18]

David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979) BibTeX

[19]

Jean-Marie Nicolas: Mutual Dependencies and Some Results on Undecomposable Relations. VLDB 1978: 360-367 BibTeX

[20]

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

[21]

Yehoshua Sagiv, Mihalis Yannakakis: Equivalences Among Relational Expressions with the Union and Difference Operators. J. ACM 27(4): 633-655(1980) BibTeX

[22]

Ravi Sethi: Testing for the Church-Rosser Property. J. ACM 21(4): 671-679(1974) BibTeX

[23]

Michael Stonebraker: Implementation of Integrity Constraints and Views by Query Modification. SIGMOD Conference 1975: 65-78 BibTeX

[24]

Jeffrey D. Ullman: Principles of Database Systems, 1st Edition. Computer Science Press 1980
BibTeX

Referenced by

1. Carmem S. Hara, Susan B. Davidson: Reasoning about Nested Functional Dependencies. PODS 1999: 91-100
2. Lucian Popa, Val Tannen: An Equational Chase for Path-Conjunctive Queries, Constraints, and Views. ICDT 1999: 39-57
3. Joachim Biskup, Andreas Kluck: A New Approach to Inferences of Semantic Constraints. ADBIS 1997: 72-79
4. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
   Contents
5. Ke Wang, Li-Yan Yuan: First-Order Logic Characterization of Program Properties. IEEE Trans. Knowl. Data Eng. 6(4): 518-533(1994)
6. Richard Hull, Masatoshi Yoshikawa: ILOG: Declarative Creation and Manipulation of Object Identifiers. VLDB 1990: 455-468
7. Yehoshua Sagiv: Optimizing Datalog Programs. PODS 1987: 349-362
8. Seymour Ginsburg, Katsumi Tanaka: Interval Queries on Object Histories: Extended Abstract. VLDB 1984: 208-217
9. Tomasz Imielinski, Witold Lipski Jr.: Incomplete Information and Dependencies in Relational Databases. SIGMOD Conference 1983: 178-184
10. Tomasz Imielinski, Witold Lipski Jr.: Inverting Relational Expressions - A Uniform and Natural Technique for Various Database Problems. PODS 1983: 305-311
11. David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
    Contents