zbMATH — the first resource for mathematics

Acquisition and validation of complex object database schemata supporting multiple inheritance. (English) Zbl 0809.68108
Summary: We present an intelligent tool for the acquisition of object-oriented schemata supporting multiple inheritance, which preserves taxonomy coherence and performs taxonomic inferences. Its theoretical framework is based on terminological logics, which have been developed in the area of artificial intelligence. The framework includes a rigorous formalization of complex objects, which is able to express cyclic references on the schema and instance level; a subsumption algorithm, which computes all implied specialization relationships between types; and an algorithm to detect incoherent types, i.e., necessarily empty types. Using results from formal analyses of knowledge representation languages, we show that subsumption and incoherence detection are computationally intractable from a theoretical point of view. However, the problems appear to be feasible in almost all practical cases.

68T30 Knowledge representation
Full Text: DOI
[1] S. Abiteboul and R. Hull, ?IFO: A formal semantic database model,?ACM Trans. Database Syst. vol. 12, no. 3, pp. 525-565, 1987. · doi:10.1145/32204.32205
[2] P. Atzeni and D. S. Parker, ?Formal properties of net-based knowledge representation schemes,?Data Knowledge Eng. vol. 3, pp. 137-147, 1988. · doi:10.1016/0169-023X(88)90011-0
[3] T. W. Finin and D. Silverman, ?Interactive classification as a knowledge acquisition tool,? inExpert Database Systems?Proceedings From the 1st International Workshop edited by L. Kerschberg, Benjamin/Cummings: Menlo Park, CA, pp. 79-90, 1986.
[4] L. Delcambre and K. Davis, ?Automatic validation of object-oriented database structures,? in5th Int. Conf. Data Eng., Los Angeles, CA, 1989, pp. 2-9.
[5] C. Lécluse and P. Richard, ?Modeling complex structures in object-oriented databases,? inProc. 8th ACM SIGACT-SIGMOD-SIGART Symp. Principles of Database-Systems, Philadelphia, PA, 1989, pp. 360-367.
[6] S. Bergamaschi and C. Sartori, ?On taxonomic resoning in conceptual design,?ACM Trans. Database Syst. vol. 17, no. 3, pp. 385-422, 1992. · doi:10.1145/132271.132272
[7] H. W. Beck, S. K. Gala, and S. B. Navathe, ?Classification as a query processing technique in the CANDIDE semantic data model,? inProc. Int. Data Eng. Conf. IEEE, Los Angeles, CA, February 1989, pp. 572-581.
[8] A. Borgida, R. J. Brachman, D. L. McGuinness, and L. A. Resnick, ?CLASSIC: a structural data model for objects,? inProc. 1989 ACM SIGMOD Int. Conf. Management of Data, Portland, OR, 1989, pp. 59-67.
[9] C. Lécluse and P. Richard, ?The O2 database programming language,? inProc. 15th Int. Conf. Very Large Data Bases, Amsterdam, The Netherlands, 1989, pp. 411-422.
[10] L. A. Cardelli, ?Semantics of multiple inheritance,? inSemantics of Data Types Springer-Verlag: Berlin, Heidelberg, New York, 1984, pp. 51-67.
[11] B. Nebel,Reasoning and Revision in Hybrid Representation Systems, volume 422 ofLecture Notes in Artificial Intelligence, Springer-Verlag: Berlin, Heidelberg, New York, 1990. · Zbl 0702.68095
[12] R. J. Brachman and J. G. Schmolze, ?An overview of the KL-ONE knowledge representation system,?Cogn. Sci. vol. 9, no. 2, pp. 171-216, 1985. · doi:10.1207/s15516709cog0902_1
[13] S. Abiteboul and A. Bonner, ?Objects and views,? inProc. 1991 ACM SIGMOD Int. Conf. Management of Data, 1991, pp. 238-247.
[14] P. P. Chen, ?The entity-relationship model?towards a unified view of data,?ACM Trans. Database Syst. vol. 1, no. 1, pp. 9-36, 1976. · doi:10.1145/320434.320440
[15] J. Mylopoulos, P. A. Bernstein, and H. K. T. Wong, ?A language facility for designing interactive database-in-tensive systems,?ACM Trans. on Database Syst. vol. 5, no. 2, pp. 185-207, 1980. · doi:10.1145/320141.320150
[16] A. Albano, L. Cardelli, and R. Orsini, ?Galileo: a strongly typed, interactive conceptual language,?ACM Trans. Database Syst. vol. 2, pp. 230-260, 1985. · doi:10.1145/3857.3859
[17] F. Baader, ?Terminological cycles in KL-ONE-based knowledge representation languages,? inProc. 8th Natl. Conf., Boston, MA, August 1990. MIT Press: Cambridge, MA, pp. 621-626.
[18] B. Nebel, ?Terminological cycles: Semantics and computational properties,? inPrinciples of Semantic Networks edited by J. F. Sowa, Morgan Kaufmann: San Mateo, CA, pp. 331-362, 1991.
[19] P. Atzeni (ed.),LOGIDATA +: Deductive Databases with Complex Objects. Lecture Notes in Computer Science Springer-Verlag: Berlin, Heidelberg, New York, 1993. · Zbl 0825.00046
[20] S. Bergamaschi and J. P. Ballerini, ?Automatic building and validation of complex object database schemata,? CIOC-CNR, Bologna, Italy, Technical Report 91, December 1992.
[21] M. R. Garey and D. S. Johnson,Computer and Intractability?A Guide to the Theory of NP-Completeness Freeman: San Francisco, CA, 1979. · Zbl 0411.68039
[22] B. Nebel, ?Terminological reasoning is inherently intractable,?Artif. Intell. vol. 43, pp. 235-249, 1990. · Zbl 0717.68089 · doi:10.1016/0004-3702(90)90087-G
[23] J. P. Ballerini, S. Bergamaschi, and C. Sartori, ?The ODL-DESIGNER prototype,? inLOGIDATA +: Deductive Databases with complex objects edited by P. Atzeni, Springer-Verlag: Berlin, 1993.
[24] J. Heinsohn, D. Kudenko, B. Nebel, and H.-J. Profitlich, ?An empirical analysis of terminological representation systems,? inProc. 10th Natl. Conf. AAAI, San Jose, CA, July 1992. MIT Press: Cambridge, MA, pp. 767-773. · Zbl 0812.68113
[25] D. Beneventano and S. Bergamaschi, ?Subsumption for complex object data models,? inProc. Int. Conf. Database Theory, Berlin, Germany, 1992. Springer-Verlag: Berlin.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.