Unrestricted and finite model reasoning in class-based representation formalisms

vii 1 Representing Structured Information 1 1.1 Semantic Networks and Frame Based Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Description Logics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Semantic Data Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 Object-Oriented Data Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.5 Goal of the Thesis and Main Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.6 Structure of the Thesis .  Syntax and Semantics of L-Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1.1 The Core Language (L0, L−) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.1.2 Disjunction (LU) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.1.3 Qualified Existential Quantification (LE) . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.1.4 Number Restrictions (LN , LF , LQ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.1.5 Inverse Attributes (LI) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.1.6 General Negation (LC) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.1.7 Arbitrary Links (LL, LD, L∆, LV) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.1.8 Structured Objects (LO) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.1.9 Achieving Maximum Expressivity (LT , LT −) . . . . . . . . . . . . . . . . . . . . . . . 17 2.1.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2 L-Schemata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.2.1 Cycles in L-Schemata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.2.2 Primitive L-Schemata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2.3 Free L-Schemata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2.4 Summary and Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.3 Schema Level Reasoning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.3.1 Reasoning Services . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.3.2 Equivalence of Schemata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.4 Finite versus Unrestricted Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3 Modeling Known Formalisms 29 3.1 Comparison with Description Logics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.2 Modeling Frame Based Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.2.1 Syntax of Frame Based Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.2.2 Semantics of Frame Based Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.2.3 Relationship between Frame Based Systems and L-Schemata . . . . . . . . . . . . . . 32 3.3 Modeling Semantic Data Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.3.1 Syntax of the Entity-Relationship Model . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.3.2 Semantics of the Entity-Relationship Model . . . . . . . . . . . . . . . . . . . . . . . . 36 3.3.3 Relationship between ER-Schemata and L-Schemata . . . . . . . . . . . . . . . . . . .