Semantic Investigations in Distributed Ontologies [PhD Thesis]

Abstracts ix
Abstract in English . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
Abstrakt v Sloven£ine (Abstract in Slovak) . . . . . . . . . . . . . . . x
Keywords . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x
Contents xi
1 Introduction 1
1.1 Ontologies in Context of the Semantic Web . . . . . . . . . . . . 1
1.2 Modular and Distributed Ontology Frameworks . . . . . . . . . . 4
1.3 Contribution of This Work . . . . . . . . . . . . . . . . . . . . . 8
1.4 Roadmap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2 Description Logics 13
2.1 ALC, the basic DL . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.1 ALC Formulae . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.2 ALC Knowledge Bases . . . . . . . . . . . . . . . . . . . . 18
2.1.3 Reasoning with ALC . . . . . . . . . . . . . . . . . . . . . 23
2.1.4 Computational complexity . . . . . . . . . . . . . . . . . . 32
2.2 Transitivity, role hierarchies and inverses . . . . . . . . . . . . . . 33
2.2.1 SHI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2.2 Reasoning with SHI . . . . . . . . . . . . . . . . . . . . . 35
2.2.3 Computational complexity . . . . . . . . . . . . . . . . . . 39
2.3 Number restrictions . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.3.1 SHIQ, SHIN and SHIF . . . . . . . . . . . . . . . . . 40
2.3.2 Reasoning with SHIQ . . . . . . . . . . . . . . . . . . . . 42
2.3.3 Computational complexity . . . . . . . . . . . . . . . . . . 47
2.4 Nominals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.4.1 SHOIQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.4.2 Reasoning with SHOIQ. . . . . . . . . . . . . . . . . . . 49
2.4.3 Computational complexity . . . . . . . . . . . . . . . . . . 55
2.5 More Expressive DL . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.5.1 SROIQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.5.2 ALCQIb . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3 Distributed Description Logics 59
3.1 Formalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.2 Properties of DDL . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.3 Reasoning with DDL . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.4 Extensions of DDL . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4 Subsumption Propagation and Complex Concepts in DDL 77
4.1 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.2 Complex Concepts and Subsumption Propagation in Original DDL 81
4.3 Conjunctive Bridge Rules . . . . . . . . . . . . . . . . . . . . . . 84
4.4 Transformational Semantics . . . . . . . . . . . . . . . . . . . . . 89
4.5 Evaluation and Comparison . . . . . . . . . . . . . . . . . . . . . 90
4.6 DDL with Injective Domain Relations . . . . . . . . . . . . . . . 94
4.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5 Subsumption Propagation and Remote Ontologies in DDL 103
5.1 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.2 Coping with Chains of Bridge Rules . . . . . . . . . . . . . . . . 109
5.2.1 DDL with Compositionally Consistent Domain Relations 109
5.2.2 DDL with Restricted Compositionality . . . . . . . . . . . 117
5.2.3 DDL with Transitive Domain Relations . . . . . . . . . . 121
5.3 Distributed Tableaux Algorithm for Transitive DDL . . . . . . . 128
5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
6 Relating Distributed Ontology Representation Frameworks 137
6.1 Reference Distributed Ontology Framework . . . . . . . . . . . . 138
6.2 Distributed Description Logics . . . . . . . . . . . . . . . . . . . 139
6.2.1 Formalization . . . . . . . . . . . . . . . . . . . . . . . . . 140
6.2.2 Modeling with DDL . . . . . . . . . . . . . . . . . . . . . 142
6.2.3 DDL with Restricted Semantics . . . . . . . . . . . . . . . 145
6.3 E-connections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
6.3.1 Formalization . . . . . . . . . . . . . . . . . . . . . . . . . 146
6.3.2 Reasoning with E-connections . . . . . . . . . . . . . . . . 149
6.3.3 Modeling with E-connections . . . . . . . . . . . . . . . . 150
6.4 Package-based Description Logics . . . . . . . . . . . . . . . . . . 153
6.4.1 Formalization . . . . . . . . . . . . . . . . . . . . . . . . . 154
6.4.2 Reasoning with P-DL . . . . . . . . . . . . . . . . . . . . 155
6.4.3 Modeling with P-DL . . . . . . . . . . . . . . . . . . . . . 156
6.5 Integrated Distributed Description Logics . . . . . . . . . . . . . 158
6.5.1 Formalization . . . . . . . . . . . . . . . . . . . . . . . . . 158
6.5.2 Reasoning with IDDL . . . . . . . . . . . . . . . . . . . . 160
6.5.3 Modeling with IDDL . . . . . . . . . . . . . . . . . . . . . 160
6.6 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
6.6.1 DDL vs. E-connections . . . . . . . . . . . . . . . . . . . 163
6.6.2 P-DL vs. DDL . . . . . . . . . . . . . . . . . . . . . . . . 164
6.6.3 IDDL vs. DDL . . . . . . . . . . . . . . . . . . . . . . . . 170
6.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
7 Conclusion and Future Work 179
Bibliography 183
List of Figures 190
List of Tables 191