Table of Contents
List of contributors ix
Preface to the second edition xiii
Preface xv
1 An Introduction to Description Logics D. Nardi R. J. Brachman 1
1.1 Introduction 1
1.2 From networks to Description Logics 5
1.3 knowledge representation in Description Logics 13
1.4 From theory to practice: Description Logic systems 17
1.5 Applications developed with Description Logic systems 22
1.6 Extensions of Description Logics 32
1.7 Relationship to other fields of Computer Science 39
1.8 Conclusion 42
Part I Theory 45
2 Basic Description Logics F. Baader W. Nutt 47
2.1 Introduction 47
2.2 Definition of the basic formalism 50
2.3 Reasoning algorithms 81
2.4 Language extensions 98
3 Complexity of Reasoning F. M. Donini 105
3.1 Introduction 105
3.2 OR-branching: finding a model 109
3.3 AND-branching: finding a clash 117
3.4 Combining sources of complexity 124
3.5 Reasoning in the presence of axioms 127
3.6 Undecidability 133
3.7 Reasoning about individuals in ABoxes 140
3.8 Discussion 144
3.9 A list of complexity results for subsumption and satisfiability 145
4 Relationships with other Formalisms U. Sattler D. Calvanese R. Molitor 149
4.1 AI knowledge representation formalisms 149
4.2 Logical formalisms 161
4.3 Database models 174
5 Expressive Description Logics D. Calvanese G. De Giacomo 193
5.1 Introduction 193
5.2 Correspondence between Description Logics and Propositional Dynamic Logics 195
5.3 Functional restrictions 202
5.4 Qualified number restrictions 209
5.5 Objects 213
5.6 Fixpoint constructs 217
5.7 Relations of arbitrary arity 221
5.8 Finite model reasoning 226
5.9 Undecidability results 232
6 Extensions to Description Logics F. Baader R. Küsters F. Wolter 237
6.1 Introduction 237
6.2 Language extensions 238
6.3 Non-standard inference problems 270
Part II Implementation 283
7 From Description Logic Provers to Knowledge Representation Systems D. L. McGuinness P. F. Patel-Schneider 285
7.1 Introduction 285
7.2 Basic access 287
7.3 Advanced application access 290
7.4 Advanced human access 295
7.5 Other technical concerns 301
7.6 Public relations concerns 301
7.7 Summary 303
8 Description Logic Systems R. Möller V. Haarslev 304
8.1 New light through old windows? 304
8.2 The first generation 305
8.3 Second generation Description Logic systems 313
8.4 The next generation: FaCT, DLP and RACER 324
8.5 Lessons learned 327
9 Implementation and Optimization Techniques I. Horrocks 329
9.1 Introduction 329
9.2 Preliminaries 331
9.3 Subsumption-testing algorithms 336
9.4 Theory versus practice 341
9.5 Optimization techniques 347
9.6 Discussion 371
Part III Applications 375
10 Conceptual Modeling with Description Logics A. Borgida R. J. Brachman 377
10.1 Background 377
10.2 Elementary Description Logic modeling 379
10.3 Individuals in the world 381
10.4 Concepts 384
10.5 Subconcepts 387
10.6 Modeling relationships 390
10.7 Modeling ontological aspects of relationships 392
10.8 A conceptual modeling methodology 399
10.9 The ABox: modeling specific states of the world 399
10.10 Conclusions 401
11 Software Engineering C. A. Welty 402
11.1 Introduction 402
11.2 Background 402
11.3 LaSSIE 403
11.4 CODEBASE 408
11.5 CSIS and CBMS 409
12 Configuration D. L. McGuinness 417
12.1 Introduction 417
12.2 Configuration description and requirements 419
12.3 The PROSE and QUESTAR family of configurators 433
12.4 Summary 434
13 Medical Informatics A. Rector 436
13.1 Background and history 437
13.2 Example applications 441
13.3 Technical issues in medical ontologies 447
13.4 Ontological issues in medical ontologies 453
13.5 Architectures: terminology servers, views, and change management 456
13.6 Discussion: key lessons from medical ontologies 457
14 OWL: a Description-Logic-Based Ontology Language for the Semantic Web I. Horrocks P. F. Patel-Schneider D. L. McGuinness C. A. Welty 458
14.1 Background and history 458
14.2 Steps towards integration with the Semantic Web: OIL and DAML+OIL 461
14.3 Full integration into the Semantic Web: OWL 467
14.4 Summary 484
15 Natural Language Processing E. Franconi 487
15.1 Introduction 487
15.2 Semantic interpretation 488
15.3 Reasoning with the logical form 492
15.4 Knowledge-based natural language generation 497
16 Description Logics for Databases A. Borgida M. Lenzerini R. Rosati 500
16.1 Introduction 500
16.2 Data models and Description Logics 504
16.3 Description Logics and database querying 513
16.4 Data integration 517
16.5 Conclusions 523
Appendix Description Logic Terminology F. Baader 525
A.l Notational conventions 525
A.2 Syntax and semantics of common Description Logics 526
A.3 Additional constructors 531
A.4 A note on the naming scheme for Description Logics 534
Bibliography 537
Index 593
