Temporal FDs on complex objects

ABSTRACT

Temporal functional dependencies (TFD) are defined for temporal databases that include object identity. It is argued that object identity can overcome certain semantic diffuculties with existing temporal relational data models. Practical applications of TFDs in object bases are discussed. Reasoning about TFDs is at the center of this paper. It turns out that the distinction between acyclic and cyclic schemas is significant. For acyclic schemas, a complete axiomatization for finite implication is given and an algorithm for deciding finite implication provided. The same axiomatization is proven complete for unrestricted implication in unrestricted schemas, which can be cyclic. An interesting result is that there are cyclic schemas for which unrestricted and finite implication do not coincide. TFDs relate and extend some earlier work on dependency theory in temporal databases. Throughout this paper, the construct of TFD is compared with the notion of temporal FD introduced by Wang et al. (1997). A comparison with other related work is provided at the end of the article.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: Constantin Arapis, Temporal specifications of object behavior, Proceedings of the 3rd symposium on Mathematical fundamentals of database and knowledge base systems, p.308-324, May 1991, Rostock, Germany
• 3: Marianne Baudinet , Jan Chomicki , Pierre Wolper, Constraint-Generating Dependencies, Proceedings of the 5th International Conference on Database Theory, p.322-337, January 11-13, 1995
• 4: BETTINI, C., DYRESON, C., EVANS, W., SNODGRASS, R., AND WANG, X. 1998. A glossary of time granularity concepts. In Temporal Databases: Research and Practice: State-of-the-Art Survey, O. Etzion, S. Jajodia, and S. Sripada, Eds. Springer-Verlag, New York, 406-413.
• 5: CHEN, G., KERRE, E. E., AND VANDENBULCKE, J. 1994. A computational algorithm for the FFD transitive closure and a complete axiomatization of fuzzy functional dependence (FFD). Int. J. Intell. Syst. 9, 421-439.
• 6: Jan Chomicki, Efficient checking of temporal integrity constraints using bounded history encoding, ACM Transactions on Database Systems (TODS), v.20 n.2, p.149-186, June 1995 [doi>10.1145/210197.210200]
• 7: Jan Chomicki , Damian Niwiński, On the feasibility of checking temporal integrity constraints, Journal of Computer and System Sciences, v.51 n.3, p.523-535, Dec. 1995 [doi>10.1006/jcss.1995.1088]
• 8: James Clifford , Albert Croker , Alexander Tuzhilin, On completeness of historical relational query languages, ACM Transactions on Database Systems (TODS), v.19 n.1, p.64-116, March 1994 [doi>10.1145/174638.174642]
• 9: DAVEY, B. AND PRIESTLEY, H. 1990. Introduction to Lattices and Order. Cambridge University Press, New York, NY.
• 10: ELMASRI, R., Wuu, G. T., AND KOURAMAJIAN, V. 1993. A temporal model and query language for EER databases. In Temporal Databases: Theory, Design, and Implementation, A. Tansel, J. Clifford, S. Gadia, S. Jajodia, A. Segev, and R. Snodgrass, Eds. Benjamin/Cummings, Redwood City, CA, 212-229.
• 11: GADIA, S. K. AND NAIR, S. S. 1993. Temporal databases: A prelude to parametric data. In Temporal Databases: Theory, Design, and Implementation, A. Tansel, J. Clifford, S. Gadia, S. Jajodia, A. Segev, and R. Snodgrass, Eds. Benjamin/Cummings, Redwood City, CA, 28-66.
• 12: Shashi K. Gadia , Chuen-Sing Yeung, Inadequacy of interval timestamps in temporal databases, Information Sciences: an International Journal, v.54 n.1-2, p.1-22, March 1991 [doi>10.1016/0020-0255(91)90042-S]
• 13: GREGERSEN, H. AND JENSEN, C. S. 1997. Temporal entity-relationship models: A survey. Tech. Rep. TR-3. TimeCenter.
• 14: Christian S. Jensen , Richard Thomas Snodgrass , Michael D. Soo, Extending Existing Dependency Theory to Temporal Databases, IEEE Transactions on Knowledge and Data Engineering, v.8 n.4, p.563-582, August 1996 [doi>10.1109/69.536250]
• 15: Christian S. Jensen , Richard Thomas Snodgrass, Semantics of Time-Varying Attributes and their Use for Temporal Database Design, Proceedings of the 14th International Conference on Object-Oriented and Entity-Relationship Modelling, p.366-377, December 12-15, 1995
• 16: Won Kim, Introduction to object-oriented databases, MIT Press, Cambridge, MA, 1991
• 17: U. W. Lipeck , G. Saake, Monitoring dynamic integrity constraints based on temporal logic, Information Systems, v.12 n.3, p.255-269, 1987 [doi>10.1016/0306-4379(87)90004-4]
• 18: MONTANARI, n. AND PERNICI, B. 1993. Temporal reasoning. In Temporal Databases: Theory, Design, and Implementation, A. Tansel, J. Clifford, S. Gadia, S. Jajodia, A. Segev, and R. Snodgrass, Eds. Benjamin/Cummings, Redwood City, CA, 534-562.
• 19: S. B. Navathe , R. Ahmed, A temporal relational model and a query language, Information Sciences: an International Journal, v.49 n.1-3, p.147-175, Oct.-Dec. 1989 [doi>10.1016/0020-0255(89)90026-1]
• 20: NAVATHE, S. B. AND AHMED, R. 1993. Temporal extensions to the relational model and SQL. In Temporal Databases: Theory, Design, and Implementation, A. Tansel, J. Clifford, S. Gadia, S. Jajodia, A. Segev, and R. Snodgrass, Eds. Benjamin/Cummings, Redwood City, CA, 92-109.
• 21: N. L. Sarda, Extensions to SQL for Historical Databases, IEEE Transactions on Knowledge and Data Engineering, v.2 n.2, p.220-230, June 1990 [doi>10.1109/69.54721]
• 22: Yoav Shoham, Temporal logics in AI: semantical and ontological considerations, Artificial Intelligence, v.33 n.1, p.89-104, Sept. 1987 [doi>10.1016/0004-3702(87)90052-X]
• 23: Abdullah Uz Tansel , James Clifford , Shashi Gadia , Sushil Jajodia , Arie Segev , Richard Snodgrass, Temporal databases: theory, design, and implementation, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1993
• 24: TAUZOVICH, B. 1991. Towards temporal extensions to the Entity-Relationship model. In Proceedings of the lOth International Conference on Entity-Relationship Approach. 163-179.
• 25: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 26: M. F. van Bommel , G. E. Weddell, Reasoning About Equations and Functional Dependencies on Complex Objects, IEEE Transactions on Knowledge and Data Engineering, v.6 n.3, p.455-469, June 1994 [doi>10.1109/69.334857]
• 27: Victor Vianu, Dynamic functional dependencies and database aging, Journal of the ACM (JACM), v.34 n.1, p.28-59, Jan. 1987 [doi>10.1145/7531.7918]
• 28: X. Sean Wang , Claudio Bettini , Alexander Brodsky , Sushil Jajodia, Logical design for temporal databases with multiple granularities, ACM Transactions on Database Systems (TODS), v.22 n.2, p.115-170, June 1997 [doi>10.1145/249978.249979]
• 29: Grant E. Weddell, Reasoning about functional dependencies generalized for semantic data models, ACM Transactions on Database Systems (TODS), v.17 n.1, p.32-64, March 1992 [doi>10.1145/128765.128767]
• 30: Jozef Wijsen, Design of Temporal Relational Databases Based on Dynamic and Temporal Functional Dependencies, Proceedings of the International Workshop on Temporal Databases: Recent Advances in Temporal Databases, p.61-76, September 17-18, 1995
• 31: WIJSEN, J. 1995. Extending dependency theory for temporal databases. Ph.D. Dissertation. Department of Computer Science, Katholieke Universiteit Leuven, Leuven, Belgium.
• 32: WIJSEN, J. AND MEERSMAN, R. 1997. On the complexity of mining temporal trends. In Proceedings of the ACM SIGMOD International Workshop on Data Mining and Knowledge Discovery, R. Ng, Ed. ACM Press, New York, NY.
• 33: Jef Wijsen , Jacques Vendenbulcke , Henke Olivie, Functional Dependencies Generalized for Temporal Databases that Include Object-Identity, Proceedings of the 12th International Conference on the Entity-Relationship Approach: Entity-Relationship Approach, p.99-109, December 15-17, 1993

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Design, Theory

Keywords:
database constraints, functional dependency, object-identity, temporal databases, time granularity