ACM SIGMOD Anthology TODS dblp.uni-trier.de

Reasoning about Functional Dependencies Generalized for Semantic Data Models.

Grant E. Weddell: Reasoning about Functional Dependencies Generalized for Semantic Data Models. ACM Trans. Database Syst. 17(1): 32-64(1992)
@article{DBLP:journals/tods/Weddell92,
  author    = {Grant E. Weddell},
  title     = {Reasoning about Functional Dependencies Generalized for Semantic
               Data Models},
  journal   = {ACM Trans. Database Syst.},
  volume    = {17},
  number    = {1},
  year      = {1992},
  pages     = {32-64},
  ee        = {http://doi.acm.org/10.1145/128765.128767, db/journals/tods/Weddell92.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We propose a more general form of functional dependency for semantic data models that derives from their common feature in which the separate notions of domain and relation in the relational model are combined into a single notion of class. This usually results in a richer terminological component for their query languages, whereby terms may navigate through any number of properties, including none. We prove the richer expressiveness of this more general functional dependency, and exhibit a sound and complete set of inference axioms. Although the general problem of decidability of their logical implication remains open at this time, we present decision procedures for cases in which the dependencies included in a schema correspond to keys, or in which the schema itself is acyclic. The theory is then extended to include a form of conjunctive query. Of particular significance is that the query becomes an additional source of functional dependency. Finally, we outline several applications of the theory to various problems in physical design and in query optimization. The applications derive from an ability to predict when a query can have at most one solution.

Copyright © 1992 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 2, TODS 1991-1995, TKDE 1989-1992" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

[Abstract, Index Terms and Review]
[Full Text in PDF Format, 1961 KB]

References

[1]
...
[2]
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
[3]
Catriel Beeri: Formal Models for Object Oriented Databases. DOOD 1989: 405-430 BibTeX
[4]
...
[5]
...
[6]
...
[7]
E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX
[8]
Umeshwar Dayal: Queries and Views in an Object-Oriented Data Model. DBPL 1989: 80-102 BibTeX
[9]
Peter J. Downey, Ravi Sethi, Robert Endre Tarjan: Variations on the Common Subexpression Problem. J. ACM 27(4): 758-771(1980) BibTeX
[10]
Adele Goldberg, David Robson: Smalltalk-80: The Language and Its Implementation. Addison-Wesley 1983
BibTeX
[11]
...
[12]
William Kent: Limitations of Record-Based Information Models. ACM Trans. Database Syst. 4(1): 107-131(1979) BibTeX
[13]
David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX
[14]
Alberto O. Mendelzon: Functional Dependencies in Logic Programs. VLDB 1985: 324-330 BibTeX
[15]
John Mylopoulos, Philip A. Bernstein, Harry K. T. Wong: A Language Facility for Designing Database-Intensive Applications. ACM Trans. Database Syst. 5(2): 185-207(1980) BibTeX
[16]
Greg Nelson, Derek C. Oppen: Fast Decision Procedures Based on Congruence Closure. J. ACM 27(2): 356-364(1980) BibTeX
[17]
...
[18]
Bjarne Stroustrup: The C++ Programming Language, First Edition. Addison-Wesley 1986, ISBN 0-201-12078-X
BibTeX
[19]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX
[20]
...
[21]
Grant E. Weddell: Selection of Indexes to Memory-Resident Entities for Semantic Data Models. IEEE Trans. Knowl. Data Eng. 1(2): 274-284(1989) BibTeX
[22]
Carlo Zaniolo: The Database Language GEM. SIGMOD Conference 1983: 207-218 BibTeX

Referenced by

  1. Vitaliy L. Khizder, David Toman, Grant E. Weddell: On Decidability and Complexity of Description Logics with Uniqueness Constraints. ICDT 2001: 54-67
  2. Jef Wijsen: Temporal FDs on Complex Objects. ACM Trans. Database Syst. 24(1): 127-176(1999)
  3. Carmem S. Hara, Susan B. Davidson: Reasoning about Nested Functional Dependencies. PODS 1999: 91-100
  4. Domenico Beneventano, Sonia Bergamaschi, Stefano Lodi, Claudio Sartori: Consistency Checking in Complex Object Database Schemata with Integrity Constraints. IEEE Trans. Knowl. Data Eng. 10(4): 576-598(1998)
  5. Ykä Huhtala, Juha Kärkkäinen, Pasi Porkka, Hannu Toivonen: Efficient Discovery of Functional and Approximate Dependencies Using Partitions. ICDE 1998: 392-401
  6. Joachim Biskup, Ralf Menzel, Torsten Polle, Yehoshua Sagiv: Decomposition of Relationships through Pivoting. ER 1996: 28-41
  7. Mark Levene, George Loizou: A Graph-Based Data Model and its Ramifications. IEEE Trans. Knowl. Data Eng. 7(5): 809-823(1995)
  8. Domenico Beneventano, Sonia Bergamaschi, Stefano Lodi, Claudio Sartori: Consistency Checking in Complex Object Database Schemata with Integrity Constraints. DBPL 1995: 4
  9. Martin F. van Bommel, Grant E. Weddell: Reasoning About Equations and Functional Dependencies on Complex Objects. IEEE Trans. Knowl. Data Eng. 6(3): 455-469(1994)
  10. Jef Wijsen, Jacques Vandenbulcke, Henke Olivie: Functional Dependencies Generalized for Temporal Databases that Include Object-Identity. ER 1993: 99-109
  11. Grant E. Weddell, Neil Coburn: A Theory of Specialization Constraints for Complex Objects. ICDT 1990: 229-244
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:39:12 2008