Querying Description Logic Knowledge Bases [PhD Thesis]

Abstract 7
Declaration 8
Copyright 9
Acknowledgements 10
1 Introduction 11
1.1 Description Logics . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.1.1 Description Logic Knowledge Bases . . . . . . . . . . . . . 13
1.1.2 Historical Background of Description Logics . . . . . . . . 14
1.1.3 Application Areas of Description Logics . . . . . . . . . . . 15
1.1.4 Semantics of Description Logics . . . . . . . . . . . . . . . 17
1.2 Reasoning Services . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.2.1 Standard Reasoning Services . . . . . . . . . . . . . . . . . 18
1.2.2 Conjunctive Queries . . . . . . . . . . . . . . . . . . . . . 18
1.2.3 Challenges of Query Answering . . . . . . . . . . . . . . . 23
1.3 Aims and Objectives . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.4 A Guide for Readers . . . . . . . . . . . . . . . . . . . . . . . . . 27
2 Foundations of Description Logics 29
2.1 Syntax and Semantics . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2 Standard Reasoning Tasks . . . . . . . . . . . . . . . . . . . . . . 33
2.3 Conjunctive Queries . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.3.1 Query Answering . . . . . . . . . . . . . . . . . . . . . . . 40
2.3.2 Conjunctive Queries in Databases . . . . . . . . . . . . . . 41
2.3.3 Why Conjunctive Queries . . . . . . . . . . . . . . . . . . 41
2.4 Combined and Data Complexity . . . . . . . . . . . . . . . . . . . 42
3 Related Work and Alternative Approaches 44
3.1 Conjunctive Queries for Expressive Description Logics . . . . . . . 44
3.2 Conjunctive Queries for Tractable Description Logics . . . . . . . 45
3.3 Modal Correspondence Theory . . . . . . . . . . . . . . . . . . . . 46
3.4 Query Containment . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.4.1 The Difficulty of Regular Expressions . . . . . . . . . . . . 49
3.5 Rule Formalisms . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.5.1 The Carin System . . . . . . . . . . . . . . . . . . . . . . . 52
3.5.2 Extensions of the Carin System . . . . . . . . . . . . . . . 57
3.6 Hybrid Logics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.6.1 Hybrid Logic Binders for Query Answering . . . . . . . . . 60
3.7 First-Order Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4 Query Entailment for SHIQ 69
4.1 Query Rewriting by Example . . . . . . . . . . . . . . . . . . . . 70
4.1.1 Forest Bases and Canonical Interpretations . . . . . . . . . 70
4.1.2 The Running Example . . . . . . . . . . . . . . . . . . . . 79
4.1.3 The Rewriting Steps . . . . . . . . . . . . . . . . . . . . . 81
4.2 Query Rewriting . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.2.1 Tree- and Forest-Shaped Queries . . . . . . . . . . . . . . 87
4.2.2 From Graphs to Forests . . . . . . . . . . . . . . . . . . . 88
4.2.3 From Trees to Concepts . . . . . . . . . . . . . . . . . . . 90
4.2.4 Query Matches . . . . . . . . . . . . . . . . . . . . . . . . 92
4.2.5 Correctness of the Query Rewriting . . . . . . . . . . . . . 94
4.3 Deciding Query Entailment for SHIQ . . . . . . . . . . . . . . . 106
4.3.1 A Deterministic Decision Procedure . . . . . . . . . . . . . 106
4.3.2 A Non-Deterministic Decision Procedure . . . . . . . . . . 117
4.3.3 Consequential Results . . . . . . . . . . . . . . . . . . . . 118
4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5 Query Entailment for SHOQ 120
5.1 Forest Bases and Canonical Interpretations . . . . . . . . . . . . . 122
5.2 Query Rewriting . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
5.2.1 Query Shapes and Matches . . . . . . . . . . . . . . . . . 128
5.2.2 From Forest-Shaped Queries to Concept Conjuncts . . . . 133
5.2.3 Correctness of the Rewriting Steps . . . . . . . . . . . . . 135
5.3 Deciding Query Entailment for SHOQ . . . . . . . . . . . . . . . 138
5.3.1 Canonical Models of Bounded Branching Degree . . . . . . 139
5.3.2 Eliminating Transitivity . . . . . . . . . . . . . . . . . . . 141
5.3.3 Alternating Automata . . . . . . . . . . . . . . . . . . . . 146
5.3.4 Tree Relaxations . . . . . . . . . . . . . . . . . . . . . . . 148
5.3.5 Deciding Existence of Tree Relaxations . . . . . . . . . . . 154
5.3.6 Combined Complexity . . . . . . . . . . . . . . . . . . . . 161
5.3.7 Consequential Results . . . . . . . . . . . . . . . . . . . . 163
5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
6 Conclusions 165
6.1 Thesis Achievements . . . . . . . . . . . . . . . . . . . . . . . . . 165
6.2 Significance of the Results . . . . . . . . . . . . . . . . . . . . . . 166
6.3 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
Bibliography 171
Index 189