On taxonomic reasoning in conceptual design

ABSTRACT

Taxonomic reasoning is a typical task performed by many AI knowledge representation systems. In this paper, the effectiveness of taxonomic reasoning techniques as an active support to knowledge acquisition and conceptual schema design is shown. The idea developed is that by extending conceptual models with defined concepts and giving them rigorous logic semantics, it is possible to infer isa relationships between concepts on the basis of their descriptions. From a theoretical point of view, this approach makes it possible to give a formal definition for consistency and minimality of a conceptual schema. From a pragmatic point of view it is possible to develop an active environment that allows automatic classification of a new concept in the right position of a given taxonomy, ensuring the consistency and minimality of a conceptual schema. A formalism that includes the data semantics of models giving prominence to type constructors (E/R, TAXIS, GALILEO) and algorithms for taxonomic inferences are presented: their soundness, completeness, and tractability properties are proved. Finally, an extended formalism and taxonomic inference algorithms for models giving prominence to attributes (FDM, IFO) are given.

REFERENCES

• 1: Serge Abiteboul , Stéphane Grumbach, COL: A Logic-Based Language for Complex Objects, Proceedings of the International Conference on Extending Database Technology: Advances in Database Technology, p.271-293, March 14-18, 1988
• 2: Serge Abiteboul , Richard Hull, IFO: a formal semantic database model, ACM Transactions on Database Systems (TODS), v.12 n.4, p.525-565, Dec. 1987 [doi>10.1145/32204.32205]
• 3: H Ait-Kaci, Type subsumption as a model of computation, Proceedings from the first international workshop on Expert database systems, p.115-139, January 1986, Kiawah Island, South Carolina, United States
• 4: Antonio Albano , Luca Cardelli , Renzo Orsini, GALILEO: a strongly-typed, interactive conceptual language, ACM Transactions on Database Systems (TODS), v.10 n.2, p.230-260, June 1985 [doi>10.1145/3857.3859]
• 5: P. Atzeni , D. S. Parker, Jr., Formal properties of net-based knowledge representation schemes, Data & Knowledge Engineering, v.3 n.3, p.137-147, Nov. 1988 [doi>10.1016/0169-023X(88)90011-0 ]
• 6: Pasolo Atzeni , D. Scott Parker, Set containment inference and syllogisms, Theoretical Computer Science, v.62 n.1-2, p.39-65, December 1988 [doi>10.1016/0304-3975(86)90011-3 ]
• 7: Carlo Batini , Stefano Ceri , Shamkant B. Navathe, Conceptual database design: an Entity-relationship approach, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1991
• 8: Howard W. Beck , Sunit K. Gala , Shamkant B. Navathe, Classification as a Query Processing Technique in the CANDIDE Semantic Data Model, Proceedings of the Fifth International Conference on Data Engineering, p.572-581, February 06-10, 1989
• 9: S. Bergamaschi , F. Bonfatti , L. Cavazza , C. Sartori , P. Tibiero, Relational database design for the intensional aspects of a knowledge base, Information Systems, v.13 n.3, p.245-256, May 1, 1988 [doi>10.1016/0306-4379(88)90037-3]
• 10: Sonia Bergamaschi , Lorenzo Cavedoni , Claudio Sartori , Paolo Tiberio, On Taxonomic Reasoning in E/R Environment, Proceedings of the Seventh International Conference on Enity-Relationship Approach: A Bridge to the User, p.443-454, November 16-18, 1988
• 11: BERGAMASCHI, S., AND NEBEL, B. The complexity of multiple inheritance in complex object data models. In Workshop on AI and Objects--IJCAI '91 (Sidney~ Australia, Aug. 1991).
• 12: BERGAMASCHI, S., AND SARTORI, C. On taxonomic reasoning in conceptual design. Tech. Rep. 78, CIOC-CNR, Bologna, Italy, 1991.
• 13: Alexander Borgida , Ronald J. Brachman , Deborah L. McGuinness , Lori Alperin Resnick, CLASSIC: a structural data model for objects, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.58-67, June 1989, Portland, Oregon, United States
• 14: BOUZEGHOUB, M., GARDARIN, G., AND METAIS, E. Database design tools: An expert system approach. In Proceedtngs of the International Conference on Ve~ Large Databases (Stockolm, Aug., 1985), pp. 82-95.
• 15: BRACHMAN, R. J., GILBERT, V. P., AND LEVESQUE, H. J. An essential hybrid reasoning system: Knowledge and symbol level accounts of KRYPTON. In IJCAI (Los Angeles, Aug, 1985), pp. 532-539.
• 16: BP~CHMAN, R. J., AND LEVESQUE, H.J. The tractability of subsumption in frame-based description languages. In AAA/(Austin, Tex, 1984), pp. 34 37.
• 17: BRACHMAN, R. J., AND SCHMOLZE, J.G. An overview of the KL-ONE knowledge representation system. Cognitive Sci. 9, 2 (1985), 171-216.
• 18: Michael L Brodie , John Mylopoulos, On knowledge base management systems: integrating artificial intelligence and d atabase technologies, Springer-Verlag New York, Inc., New York, NY, 1986
• 19: Peter Buneman , Robert E. Frankel, FQL: a functional query language, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582104]
• 20: Luca Cardelli, A semantics of multiple inheritance., Proc. of the international symposium on Semantics of data types, p.51-67, July 1984, Sophia-Antipolis, France
• 21: Stefano Ceri, Methodology and Tools for Data Design, Elsevier Science Inc., New York, NY, 1983
• 22: Peter Pin-Shan Chen, The entity-relationship model—toward a unified view of data, ACM Transactions on Database Systems (TODS), v.1 n.1, p.9-36, March 1976 [doi>10.1145/320434.320440]
• 23: CHEN, P. ER-Designer. Chen, Baton-Rouge, La., 1987.
• 24: J. Choobineh , M. V. Mannino , J. F. Nunamaker, Jr. , B. R. Konsynski, An Expert Database Design System Based on Analysis of Forms, IEEE Transactions on Software Engineering, v.14 n.2, p.242-253, February 1988 [doi>10.1109/32.4641 ]
• 25: DAYAL, V. ET AL. PROBE: A research project in knowledge oriented database systems--Preliminary analysis. Tech. Rep. 85-03,, Computer Corporation of America, 1985.
• 26: O. De Troyer, RIDL*: a tool for the computer-assisted engineering of large databases in the presence of integrity constraints, ACM SIGMOD Record, v.18 n.2, p.418-429, June 1989
• 27: Lois M. L. Delcambre , Karen C. Davis, Automatic Validation of Object-Oriented Database Structures, Proceedings of the Fifth International Conference on Data Engineering, p.2-9, February 06-10, 1989
• 28: Giuseppe Di Battista , M. Lenzerini, A deductive method for entity-relationship modeling, Proceedings of the 15th international conference on Very large data bases, p.13-21, July 1989, Amsterdam, The Netherlands
• 29: DONINI, F. M., LENZERINI, M., NARDI, D., AND NUTT, W. The complexity of concept languages. In KR '91. In Proceedings of the 2nd International Conference on Principles of Knowledge Representation and Reasoning (Cambridge, Apr. 1991), J. Allen, R. Fikes, and E. Sandewall, Ed., Morgan Kauffmann, Palo Alto, Calif., 1991, pp. 151-162.
• 30: DONINI, F. M., LENZERINI, M., NARDI, D., AND NUTT, W. Tractable concept languages. In IJCAI 91 (Australia, Aug., 1991), pp. 458-463.
• 31: Fabrizio Massimo Ferrara, Easy ER - An Integrated System for the Design and Documentation of Data Base Applications, Proceedings of the Fourth International Conference on Entity-Relationship Approach, p.104-113, October 29-30, 1985
• 32: T Finin , D Silverman, Interactive classification of conceptual knowledge, Proceedings from the first international workshop on Expert database systems, p.79-90, January 1986, Kiawah Island, South Carolina, United States
• 33: Michael Hammer , Dennis Mc Leod, Database description with SDM: a semantic database model, ACM Transactions on Database Systems (TODS), v.6 n.3, p.351-386, Sept. 1981 [doi>10.1145/319587.319588]
• 34: Richard Hull , Roger King, Semantic database modeling: survey, applications, and research issues, ACM Computing Surveys (CSUR), v.19 n.3, p.201-260, Sept. 1987 [doi>10.1145/45072.45073]
• 35: Richard Hull , Chee K. Yap, The Format Model: A Theory of database Organization, Journal of the ACM (JACM), v.31 n.3, p.518-544, July 1984 [doi>10.1145/828.832]
• 36: C. Lécluse , P. Richard, Modeling complex structures in object-oriented logic programming, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.360-368, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73756]
• 37: C. Lécluse , P. Richard, The O2 database programming language, Proceedings of the 15th international conference on Very large data bases, p.423-432, July 1989, Amsterdam, The Netherlands
• 38: C. Lecluse , P. Richard , F. Velez, O2, an object-oriented data model, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.424-433, June 01-03, 1988, Chicago, Illinois, United States
• 39: LucK, YON K., NEBEL, B.. PELTASON, C., AND SCHMIEDEL, A. The BACK System. KIT 41, Tech. Univ. Berlin, 1987.
• 40: 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]
• 41: B. Nebel, Computational complexity of terminological reasoning in BACK, Artificial Intelligence, v.34 n.3, p.371-383, April 1988 [doi>10.1016/0004-3702(88)90066-5 ]
• 42: Bernhard Nebel, Reasoning and revision in hybrid representation systems, Springer-Verlag New York, Inc., New York, NY, 1990
• 43: B. Nebel, Terminological reasoning is inherently intractable (research note), Artificial Intelligence, v.43 n.2, p.235-249, May 1990 [doi>10.1016/0004-3702(90)90087-G ]
• 44: PATEL-SCHNEIDER, P F. Small can be beautiful in knowledge representation. In Proceedings of the Workshop on Principles of Knowledge-Based Systems (Denver, Colo., Dec. 1984), IEEE, New York, 1984, pp. 11-16.
• 45: PATEL-SCHNEIDER, P.F. A four-valued semantics for frame-based description languages. In Proceedmgs AAAI (Philadelphia, Pa., 1986), pp. 344-348.
• 46: REITER, R. Towards a logical reconstruction of relational database theory. In On Conceptual Modellmg, M. L. Brodie, J. Mylopoulos, and J. W. Schmidt, Eds. Springer, New York, 1984, pp. 191 233.
• 47: Manfred Schmidt-Schaubß, Subsumption in KL-ONE is undecidable, Proceedings of the first international conference on Principles of knowledge representation and reasoning, p.421-431, December 1989
• 48: Manfred Schmidt-Schaubß , Gert Smolka, Attributive concept descriptions with complements, Artificial Intelligence, v.48 n.1, p.1-26, Feb. 1991 [doi>10.1016/0004-3702(91)90078-X ]
• 49: SC~MOLZE, J. G., AND ISRAEL, D.J. KL-ONE: Semantics and classification. In Research in Knowledge Representation and Natural Language. BBN Tech. Rep. N.5421. Bolt, Beranek and Newman, Cambridge, Mass., 1983.
• 50: David W. Shipman, The functional data model and the data languages DAPLEX, ACM Transactions on Database Systems (TODS), v.6 n.1, p.140-173, March 1981 [doi>10.1145/319540.319561]
• 51: SIBLEY, g. H., AND KERSHBERG, L. Data architecture and data model considerations. In Proceed,ngs of the Natwnal Computer Conference (Dallas, Tex., 1977), AFIPS, pp. 85 96.
• 52: John Miles Smith , Diane C. P. Smith, Database abstractions: aggregation, Communications of the ACM, v.20 n.6, p.405-413, June 1977 [doi>10.1145/359605.359620]
• 53: John Miles Smith , Diane C. P. Smith, Database abstractions: aggregation and generalization, ACM Transactions on Database Systems (TODS), v.2 n.2, p.105-133, June 1977 [doi>10.1145/320544.320546]
• 54: VILAIN, M. The restricted language architecture of a hybrid representation system. In Proceedings of the 9th IJCAI Conference (Los Angeles, Aug., 1985), pp. 547 551.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Frames and scripts; Representation languages

General Terms:
Design, Languages, Theory, Verification

Keywords:
schema consistency, schema minimality, semantic models, taxonomic reasoning