` degli Studi di Roma “La Sapienza” Universita Dottorato di Ricerca in Informatica
Unrestricted and Finite Model Reasoning in Class-Based Representation Formalisms
Diego Calvanese VIII-96-2
Diego Calvanese
Unrestricted and Finite Model Reasoning in Class-Based Representation Formalisms
Dottorato di Ricerca in Informatica
VIII-96-2
` degli Studi di Roma “La Sapienza” Universita
Author’s address: Diego Calvanese Dipartimento di Informatica e Sistemistica ` degli Studi di Roma “La Sapienza” Universita Via Salaria 113, I-00198 Roma, Italy e-mail:
[email protected] www: http://www.dis.uniroma1.it/∼calvanes
Contents Acknowledgments
v
Abstract
vii
1 Representing Structured Information 1.1 Semantic Networks and Frame Based Systems 1.2 Description Logics . . . . . . . . . . . . . . . 1.3 Semantic Data Models . . . . . . . . . . . . . 1.4 Object-Oriented Data Models . . . . . . . . . 1.5 Goal of the Thesis and Main Results . . . . . 1.6 Structure of the Thesis . . . . . . . . . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
1 2 2 5 6 6 8
2 Representing Intensional Knowledge by L-Schemata 2.1 Syntax and Semantics of L-Languages . . . . . . . . . 2.1.1 The Core Language (L0 , L− ) . . . . . . . . . . 2.1.2 Disjunction (LU) . . . . . . . . . . . . . . . . . 2.1.3 Qualified Existential Quantification (LE) . . . 2.1.4 Number Restrictions (LN , LF, LQ) . . . . . . 2.1.5 Inverse Attributes (LI) . . . . . . . . . . . . . 2.1.6 General Negation (LC) . . . . . . . . . . . . . . 2.1.7 Arbitrary Links (LL, LD, L∆, LV) . . . . . . 2.1.8 Structured Objects (LO) . . . . . . . . . . . . 2.1.9 Achieving Maximum Expressivity (LT , LT − ) . 2.1.10 Summary . . . . . . . . . . . . . . . . . . . . . 2.2 L-Schemata . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Cycles in L-Schemata . . . . . . . . . . . . . . 2.2.2 Primitive L-Schemata . . . . . . . . . . . . . . 2.2.3 Free L-Schemata . . . . . . . . . . . . . . . . . 2.2.4 Summary and Examples . . . . . . . . . . . . . 2.3 Schema Level Reasoning . . . . . . . . . . . . . . . . . 2.3.1 Reasoning Services . . . . . . . . . . . . . . . . 2.3.2 Equivalence of Schemata . . . . . . . . . . . . . 2.4 Finite versus Unrestricted Models . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . .