An Introduction to Description Logic

Contents......Page 6
1.1 What are DLs and where do they come from?......Page 10
1.2 What are they good for and how are they used?......Page 12
1.3 A brief history of description logic......Page 13
1.4 How to use this book......Page 16
2.1 The concept language of the DL ALC......Page 19
2.2 ALC knowledge bases......Page 25
2.2.1 ALC TBoxes......Page 26
2.2.2 ALC ABoxes......Page 28
2.2.3 Restricted TBoxes and concept definitions......Page 32
2.3 Basic reasoning problems and services......Page 37
2.4 Using reasoning services......Page 45
2.5.1 Inverse roles......Page 46
2.5.2 Number restrictions......Page 48
2.5.3 Nominals......Page 50
2.5.5 Transitive roles......Page 51
2.6.1 DLs as decidable fragments of first-order logic......Page 53
2.6.2 DLs as cousins of modal logic......Page 55
2.7 Historical context and literature review......Page 57
3 A Little Bit of Model Theory......Page 59
3.1 Bisimulation......Page 60
3.2 Expressive power......Page 62
3.3 Closure under disjoint union......Page 64
3.4 Finite model property......Page 66
3.5 Tree model property......Page 72
3.6 Historical context and literature review......Page 76
4 Reasoning in DLs with Tableau Algorithms......Page 78
4.1 Tableau basics......Page 79
4.2 A tableau algorithm for ALC......Page 80
4.2.1 ABox consistency......Page 81
4.2.2 Acyclic knowledge base consistency......Page 91
4.2.3 General knowledge base consistency......Page 92
4.3.1 Inverse roles......Page 99
4.3.2 Number restrictions......Page 102
4.3.3 Combining inverse roles and number restrictions......Page 106
4.4.1 Or-branching......Page 110
4.4.2 And-branching......Page 112
4.5 Historical context and literature review......Page 113
5 Complexity......Page 115
5.1 Concept satisfiability in ALC......Page 116
5.1.1 Acyclic TBoxes and no TBoxes......Page 117
5.1.2 General TBoxes......Page 126
5.2.1 ALC with inverse roles and nominals......Page 132
5.2.2 Further adding number restrictions......Page 134
5.3.1 Role value maps......Page 139
5.3.2 Concrete domains......Page 143
5.4 Historical context and literature review......Page 146
6 Reasoning in the EL Family of Description Logics......Page 149
6.1 Subsumption in EL......Page 150
6.1.1 Normalisation......Page 151
6.1.2 The classification procedure......Page 156
6.2.1 Normalisation......Page 160
6.2.2 The classification procedure......Page 161
6.3.1 Comparing the classification rules......Page 168
6.3.2 A more abstract point of view......Page 171
6.4 Historical context and literature review......Page 174
7 Query Answering......Page 177
7.1 Conjunctive queries and FO queries......Page 178
7.2 FO-rewritability and DL-Lite......Page 183
7.2.1 Introducing DL-Lite......Page 184
7.2.2 Universal models......Page 189
7.2.3 FO-rewritability in DL-Lite......Page 193
7.3 Datalog-rewritability in EL and ELI......Page 201
7.3.1 Fundamentals of Datalog......Page 202
7.3.2 Datalog-rewritings in ELI......Page 204
7.3.3 Short Datalog-rewritings in EL......Page 207
7.4 Complexity aspects......Page 208
7.5 Historical context and literature review......Page 211
8 Ontology Languages and Applications......Page 214
8.1.1 OWL and RDF......Page 215
8.1.2 OWL and SROIQ......Page 218
8.1.3 OWL ontologies......Page 222
8.1.4 Non-DL features......Page 226
8.1.5 OWL profiles......Page 231
8.2.1 The OWL API......Page 232
8.2.3 Ontology engineering tools......Page 233
8.2.4 OWL applications......Page 234
A.1 Syntax and semantics of concept and role constructors......Page 237
A.2 Syntax and semantics of knowledge bases......Page 239
A.3 Naming schemes for description logics......Page 240
References......Page 243
Index......Page 261