product iamge

Querying Description Logic Knowledge Bases [PhD Thesis]

This document was uploaded by one of our users. The uploader already confirmed that they had the permission to publish it. If you are author/publisher or own the copyright of this documents, please report to us by using this DMCA report form.

Download
Search on Amazon

Simply click on the Download Book button.

Yes, Book downloads on Ebookily are 100% Free.

Sometimes the book is free on Amazon As well, so go ahead and hit "Search on Amazon"

Author(s): Birte Glimm
Publisher: University of Manchester
Year: 2007

Language: English
Pages: 192

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