ACM SIGMOD Anthology TODS dblp.uni-trier.de

Calculating Constraints on Relational Expressions.

Anthony C. Klug: Calculating Constraints on Relational Expressions. ACM Trans. Database Syst. 5(3): 260-290(1980)
@article{DBLP:journals/tods/Klug80,
  author    = {Anthony C. Klug},
  title     = {Calculating Constraints on Relational Expressions},
  journal   = {ACM Trans. Database Syst.},
  volume    = {5},
  number    = {3},
  year      = {1980},
  pages     = {260-290},
  ee        = {http://doi.acm.org/10.1145/320613.320615, db/journals/tods/Klug80.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

This paper deals with the problem of determining which of a certain class of constraints hold on a given relational algebra expression where the base relations come from a given schema. The class of constraints includes functional dependencies, equality of domains, and constancy of domains. The relational algebra consists of projection, selection, restriction, cross product, union, and difference. The problem as given is undecidable, but if set difference is removed from the algebra, there is a solution. Operators specifying a closure function (similar to functional dependency closure on one relation) are defined; these will generate exactly the set of constraints valid on the given relational algebra expression. We prove that the operators are sound and complete.

Copyright © 1980 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]
Dennis Tsichritzis, Anthony C. Klug: The ANSI/X3/SPARC DBMS Framework Report of the Study Group on Dabatase Management Systems. Inf. Syst. 3(3): 173-191(1978) BibTeX
[3]
William Ward Armstrong: Dependency Structures of Data Base Relationships. IFIP Congress 1974: 580-583 BibTeX
[4]
Catriel Beeri, Ronald Fagin, John H. Howard: A Complete Axiomatization for Functional and Multivalued Dependencies in Database Relations. SIGMOD Conference 1977: 47-61 BibTeX
[5]
Philip A. Bernstein: Synthesizing Third Normal Form Relations from Functional Dependencies. ACM Trans. Database Syst. 1(4): 277-298(1976) BibTeX
[6]
...
[7]
...
[8]
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
[9]
...
[10]
Yehoshua Sagiv, Mihalis Yannakakis: Equivalence among Relational Expressions with the Union and Difference Operation. VLDB 1978: 535-548 BibTeX
[11]
...

Referenced by

  1. Carmem S. Hara, Susan B. Davidson: Reasoning about Nested Functional Dependencies. PODS 1999: 91-100
  2. Uday R. Kulkarni, Richard G. Ramirez: Independently Updated Views. IEEE Trans. Knowl. Data Eng. 9(5): 798-812(1997)
  3. Michael J. Maher, Divesh Srivastava: Chasing Constrained Tuple-Generating Dependencies. PODS 1996: 128-138
  4. Xiaolei Qian: Correct Schema Transformations. EDBT 1996: 114-128
  5. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  6. Marc Gyssens, Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht: A Graph-Oriented Object Database Model. IEEE Trans. Knowl. Data Eng. 6(4): 572-586(1994)
  7. G. N. Paulley, Per-Åke Larson: Exploiting Uniqueness in Query Optimization. ICDE 1994: 68-79
  8. Victor M. Markowitz: A Relation Merging Technique for Relational Databases. ICDE 1992: 428-437
  9. Richard Hull, Masatoshi Yoshikawa: ILOG: Declarative Creation and Manipulation of Object Identifiers. VLDB 1990: 455-468
  10. Victor M. Markowitz, Arie Shoshani: Abbreviated Query Interpretation in Extended Entity-Relationship Oriented Databases. ER 1989: 325-343
  11. Victor Vianu: A Dynamic Framework for Object Projection Views. ACM Trans. Database Syst. 13(1): 1-22(1988)
  12. Joachim Biskup, Uwe Räsch: The Equivalence Problem For Relational Database Schemes. MFDBS 1987: 42-70
  13. Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
  14. Winfried Lamersdorf, G. Müller, Joachim W. Schmidt: Language Support for Office Modelling. VLDB 1984: 280-288
  15. Victor Vianu: Object Projection Views in the Dynamic Relational Model. PODS 1984: 214-220
  16. Marco A. Casanova, Vânia Maria Ponte Vidal: Towards a Sound View Integration Methodology. PODS 1983: 36-47
  17. David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
    Contents
  18. Anthony C. Klug, Rod Price: Determining View Dependencies Using Tableaux. ACM Trans. Database Syst. 7(3): 361-380(1982)
  19. 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)
  20. Tomasz Imielinski, Witold Lipski Jr.: A Systematic Approach to Relational Database Theory. SIGMOD Conference 1982: 8-14
  21. Marco A. Casanova: A Theory of Data Dependencies over Relational Expressions. PODS 1982: 189-198
  22. Katsumi Tanaka, Yahiko Kambayashi: Logical Integration of Locally Independent Relational Databases into a Distributed Database. VLDB 1981: 131-141
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:43 2008