Reasoning about functional dependencies generalized for semantic data models

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.

REFERENCES

• 1: ADAPLEX: Rational and Reference Manual. CCA-83-08, Computer Corporation of America, May 1983.
• 2: Catriel Beeri , Philip A. Bernstein, Computational problems related to the design of normal form relational schemas, ACM Transactions on Database Systems (TODS), v.4 n.1, p.30-59, March 1979 [doi>10.1145/320064.320066]
• 3: BEERI, C. Formal models for object oriented databases. In Proceedings 1989 DOOD Conference on Deductive and Object-Oriented Databases (Dec. 1989), pp. 370-395.
• 4: VAN BOMMEL, M. F. Theory and applications of join conditions and path functional dependencies for object-oriented data models. Master's thesis, Univ. of Waterloo, 1989.
• 5: BORGIDA, A. Features of languages for the development of information systems at the conceptual level. IEEE Softw. 2, 1 (Jan 1985), 63-72.
• 6: CHAMBERLIN, D. D., ASTRAHAN, M. M., ESWARAN, K. P. GRIFFITHS, P, LORIE, R. A., MEHL, J. W., REISNER, P., AND WADE, B.W. SEQUEL 2: A unified approach to data definition, manipulation, and control. IBM J. Res. Dev. 20, 6 (Nov. 1976), 560-575.
• 7: E. F. Codd, Extending the database relational model to capture more meaning, ACM Transactions on Database Systems (TODS), v.4 n.4, p.397-434, Dec. 1979 [doi>10.1145/320107.320109]
• 8: Umeshwar Dayal, Queries and views in an object-oriented data model, Proceedings of the second international workshop on Database programming languages, p.80-102, December 1989, Salishan Lodge, Gleneden Beach, Oregon, United States
• 9: Peter J. Downey , Ravi Sethi , Robert Endre Tarjan, Variations on the Common Subexpression Problem, Journal of the ACM (JACM), v.27 n.4, p.758-771, Oct. 1980 [doi>10.1145/322217.322228]
• 10: Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 11: HELD, G. D., STONEBRAKER, M. R., AND WONG, E. INGRES--A relational data base system. In Proceedings Natmnal Computer Conference 44 (1975).
• 12: William Kent, Limitations of record-based information models, ACM Transactions on Database Systems (TODS), v.4 n.1, p.107-131, March 1979 [doi>10.1145/320064.320070]
• 13: David Maier, Theory of Relational Databases, Computer Science Pr, 1983
• 14: MENDELZON, A. Functional dependencies in logic programs. In Proceedings Eleventh International Conference on Very Large Data Bases (Aug 1985), pp. 324-330.
• 15: John Mylopoulos , Philip A. Bernstein , Harry K. T. Wong, A language facility for designing database-intensive applications, ACM Transactions on Database Systems (TODS), v.5 n.2, p.185-207, June 1980 [doi>10.1145/320141.320150]
• 16: Greg Nelson , Derek C. Oppen, Fast Decision Procedures Based on Congruence Closure, Journal of the ACM (JACM), v.27 n.2, p.356-364, April 1980 [doi>10.1145/322186.322198]
• 17: SMITH, J. M , AND SMITH, D. C. P. A database approach to software specification. Tech. Rep. 17, Computer Corporation of America, 1979
• 18: Bjarne Stroustrup, The C++ programming language, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 19: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 20: WEDDELL, G.E. Physical design and query compilation for a semantic data model (assuming memory residence). Tech. Rep. 198, Computer Systems Research Institute, Univ. of Toronto, 1987.
• 21: G. E. Weddell, Selection of Indexes to Memory-Resident Entities for Semantic Data, IEEE Transactions on Knowledge and Data Engineering, v.1 n.2, p.274-284, June 1989 [doi>10.1109/69.87966]
• 22: Carlo Zaniolo, The database language GEM, Proceedings of the 1983 ACM SIGMOD international conference on Management of data, May 23-26, 1983, San Jose, California

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Normal forms

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Theory

Keywords:
constraint theory, functional dependencies, query optimization, semantic data models