Mengchi Liu
Abstract
Over the past decade, a large number of deductive object-oriented database languages have been proposed. The earliest of these languages had few object-oriented features, and more and more features have systematically been incorporated in successive languages. However, a language with a clean logical semantics that naturally accounts for all the key object-oriented features, is still missing from the literature. This article takes us another step towards solving this problem. Two features that are currently missing are the encapsulation of rule-based methods in classes, and nonmonotonic structural and behavioral inheritance with overriding, conflict resolution and blocking. This article introduces the syntax of a language with these features. The language is restricted in the sense that we have omitted other object-oriented and deductive features that are now well understood, in order to make our contribution clearer. It then defines a class of databases, called well-defined databases, that have an intuitive meaning and develops a direct logical semantics for this class of databases. The semantics is based on the well-founded semantics from logic programming. The work presented in this article establishes a firm logical foundation for deductive object-oriented databases.
- Abiteboul, S. and Kanellakis, P. C. 1998. Object identity as a query language. J. ACM 45, 5, 798--842. Google Scholar
Digital Library
- Abiteboul, S., Lausen, G., Uphoff, H., and Waller, E. 1993. Methods and rules. In Proceedings of the ACM SIGMOD International Conference on Management of Data (Washington, D.C.). ACM, New York, pp. 32--41. Google ScholarDigital Library
- Bal, R. and Balsters, H. 1993. A deductive and typed object-oriented language. In Proceedings of the International Conference on Deductive and Object-Oriented Databases, S. Ceri, K. Tanaka, and S. Tsur, Eds. (Phoenix, Az.). Lecture Notes in Computer Science, vol. 760.Springer-Verlag, New York, pp. 340--359.Google Scholar
- Barja, M. L., Fernandes, A. A. A., Paton, N. W., Williams, M. H., Dinn, A., and Abdelmoty, A. I. 1995. Design and implementation of rock & roll: A deductive object-oriented database system. Inf. Syst. 20, 3, 185--211. Google ScholarDigital Library
- Bugliesi, M. and Jamil, H. M. 1994. A logic for encapsulation in object oriented languages. In Proceedings of International Symposium on Programming Languages, Implementations, Logics and Programs (PLILP '94) (Madrid, Spain). Lecture Notes in Computer Science, vol. 844. Springer-Verlag New York, pp. 213--229. Google ScholarDigital Library
- Butterworth, P., Otis, A., and Stein, J. 1991. The gemstone object database management system. Commun. ACM 34, 10, 64--77. Google ScholarDigital Library
- Cacace, F., Ceri, S., Crepi-Reghizzi, S., Tanca, L., and Zicari, R. 1990. Integrating object-oriented data modelling with a rule-based programming paradigm. In Proceedings of the ACM SIGMOD International Conference on Management of Data (Atlantic City, N.J.). ACM, New York, pp. 225--236. Google ScholarDigital Library
- Cattell, R. G. G., Ed. 1996. The Object Database Standard: ODMG-93, Release 1.2. Morgan-Kaufmann, Los Altos, Calif. Google ScholarDigital Library
- Cattell, R. G. G. and Barry, D., Eds. 1997. The Object Database Standard: ODMG 2.0. Morgan-Kaufmann, Los Altos, Calif. Google ScholarDigital Library
- Chen, W., and Warren, D. 1989. C-Logic for complex objects. In Proceedings of the ACM Symposium on Principles of Database Systems (Philadelphia, Pa.). ACM, New York, pp. 369--378. Google ScholarDigital Library
- Deux, O. et al. 1990. The Story of O2. IEEE Trans. Knowl. Data Eng. 2, 1, 91--108. Google ScholarDigital Library
- Deux, O. et al. 1991. The O2 System. Commun. ACM 34, 10, 35--48. Google ScholarDigital Library
- Dobbie, G. and Topor, R. 1995. On the declarative and procedural semantics of deductive object-oriented systems. J. Intel. Inf. Syst. 4, 2, 193--219. Google ScholarDigital Library
- Fishman, D. H., Beech, B., Cate, H. P., Chow, E. C., Connors, T., Davis, J. W., Derrett, N., Hoch, C. G., Kent, W., Lyngbaek, P., Mahbod, B., Neimat, M. A., Ryan, T. A., and Shan, M. C. 1987. Iris: An object-oriented database management system. ACM Trans. Office Inf. Syst. 5, 1, 48--69.Google Scholar
- Gelder, A. V., Ross, K. A., and Schlipf, J. S. 1991. The well-founded semantics for general logic programs. J. ACM 38, 3, 620--650. Google ScholarDigital Library
- Greco, S., Leone, N., and Rullo, P. 1992. Complex: An object-oriented logic programming system. IEEE Trans. Knowl. Data Eng. 4, 4, 344--359. Google ScholarDigital Library
- Guerrini, G., Bertino, E., and Bal, R. 1998. A formal definition of the chimera object-oriented data model. J. Int. Inf. Syst. 11, 1, 5--40. Google ScholarDigital Library
- Heuer, A. and Sander, P. 1993. The living in a lattice rule language. Data Knowl. Eng. 9, 4, 249--286. Google ScholarDigital Library
- Jamil, H. M. 1997. Implementing abstract objects with inheritance in datalogneg. In Proceedings of the International Conference on Very Large Data Bases (Athens, Greece). Morgan-Kaufmann, Los Altos, Calif., pp. 46--65. Google ScholarDigital Library
- Jamil, M. H. and Lakshmanan, L. V. S. 1992. Orlog: A logic for semantic object-oriented models. In Proceedings of the 1st International Conference on Information and Knowledge Management (Baltimore, Md.). ACM New York, pp. 584--592.Google Scholar
- Kifer, M., Lausen, G., and Wu, J. 1995. Logical foundations of object-oriented and frame-based languages. J. ACM 42, 4, 741--843. Google ScholarDigital Library
- Kifer, M. and Wu, J. 1993. A logic for programming with complex objects. J. Comput. Syst. Sci. 47, 1, 77--120. Google ScholarDigital Library
- Kim, W. 1990. Introduction to Object-Oriented Databases. The MIT Press, Cambridge, Mass. Google ScholarDigital Library
- Lamb, C., Landis, G., Orenstein, J., and Weinreb, D. 1991. The objectStore system. Commun. ACM 34, 10, 50--63. Google ScholarDigital Library
- Ling, T. W. and Lee, W. B. T. 1998. DO2: A deductive object-oriented database system. In Proceedings of the 9th International Conference on Database and Expert System Applications (DEXA '98)(Vienna, Austria). Lecture Notes in Computer Science, vol. 1460. Springer-Verlag, New York, pp. 50--59. Google ScholarDigital Library
- Ling, T. W. and Teo, P. K. 1995. Object migration in ISA hierarchies. In Proceedings of the International Conference on Database Systems for Advanced Applications (DASFAA '95). World Scientific Press, Singapore, pp. 216--225. Google ScholarDigital Library
- Liu, M. 1996. ROL: A deductive object base language. Inf. Syst. 21, 5, 431--457. Google ScholarDigital Library
- Liu, M. 1998a. Incorporating methods and encapsulation into deductive object-oriented database languages. In Proceedings of the 9th International Conference on Database and Expert System Applications (DEXA '98) (Vienna, Austria). Lecture Notes in Computer Science, vol. 1460. Springer-Verlag, New York, pp. 892--902. Google ScholarDigital Library
- Liu, M. 1998b. Relationlog: A typed extension to Datalog with sets and tuples. J. Logic Prog. 36, 3, 271--299.Google ScholarCross Ref
- Liu, M. 1999. Overview of the ROL2 deductive object-oriented database system. In Proceedings of the 30th International Conference on Technology of Object-Oriented Languages & Systems (TOOLS USA '99) (Santa Barbara, Cailf.). IEEE Computer Society Press, Los Alamitos, Cailf., pp. 63--72. Google ScholarDigital Library
- Liu, M. and Guo, M. 1998. ROL2: A real deductive object-oriented database language. In Proceedings of the 17th International Conference on Conceptual Modeling (ER '98) (Singapore). Lecture Notes in Computer Science, vol. 1507. Springer-Verlag, New York, pp. 302--315. Google ScholarDigital Library
- Lou, Y. and Ozsoyoglu, M. 1991. LLO: A deductive language with methods and method inheritance. In Proceedings of the ACM SIGMOD International Conference on Management of Data (Denver, Colo.). ACM, New York, pp. 198--207. Google ScholarDigital Library
- Maier, D. 1986. A logic for objects. Tech. Rep. CS/E-86-012. Oregon Graduate Institute, Beaverton, Ore.Google Scholar
- Mumick, I. S. and Ross, K. A. 1993. Noodle: A language for declarative querying in an object-oriented database. In Proceedings of the International Conference on Deductive and Object-Oriented Databases (Phoenix, Az.). S. Ceri, K. Tanaka, and S. Tsur, Eds. Lecture Notes in Computer Science, vol. 760. Springer-Verlag, New York, pp. 360--378.Google Scholar
- Soloviev, V. 1992. An overview of three commercial object-oriented database management systems: ONTOS, ObjectStore, O2. SIGMOD Rec. 21, 1, 93--104. Google ScholarDigital Library
- Srivastava, D., Ramakrishnan, R., Srivastava, D., and Sudarshan, S. 1993. CORAL++: Adding object-orientation to a logic database language. In Proceedings of the International Conference on Very Large Data Bases (Dublin, Ireland). Morgan-Kaufmann, Los Altos, Calif., pp. 158--170. Google ScholarDigital Library
Index Terms
- A logical foundation for deductive object-oriented databases
Recommendations
Deductive database languages: problems and solutions
Deductive databases result from the integration of relational database and logic programming techniques. However, significant problems remain inherent in this simple synthesis from the language point of view. In this paper, we discuss these problems ...
Semantics and Expressive Power of Nondeterministic Constructs in Deductive Databases
Nondeterministic extensions are needed in logic-based languages, such as first-order relational languages and Datalog, to enhance their expressive power and support the efficient formulation of low-complexity problems and database queries. In this paper,...
Logical foundations of object-oriented and frame-based languages
We propose a novel formalism, called Frame Logic (abbr., F-logic), that accounts in a clean and declarative fashion for most of the structural aspects of object-oriented and frame-based languages. These features include object identity, complex objects, ...
Reviews
Amit Rudra
Object-oriented databases are not a new topic. However, including a deductive aspect to the database is not common, and there have been very few papers on this topic published. From this point of view, this work definitely adds something to our knowledge. The main contribution of the paper is its addition of two object-oriented features to deductive object-oriented databases (together with a direct logical semantics). Specifically, these two features are rule-based methods (and the encapsulation of these methods in classes) and multiple inheritance, with overriding, blocking, and conflict handling. Of particular interest is the special class “none,” added to indicate that a method blocks for its subclasses. Written in a flowing style, this paper brings both clarity and depth to the topic of deductive object-oriented databases. The examples included are helpful, and explain the concepts very clearly and simply. The paper suffers from a bibliography that does not refer to recent works; there were no references to any paper published in the new millennium.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments