Query Answering over Ontologies
Using Controlled Natural Languages




Abstract xiii
1 Introduction 1
1.1 Controlled Languages and their Scalability to Data . . . . . . . . . . . . . . . . 1
1.1.1 Natural Language Interfaces and the Usability Gap . . . . . . . . . . . . 1
1.1.2 Ontology-Based Data Access Systems . . . . . . . . . . . . . . . . . . . 2
1.1.3 Controlled Languages and the Ambiguity Problem . . . . . . . . . . . . 3
1.1.4 Semantic Complexity and the Scalability Problem . . . . . . . . . . . . 7
1.2 Aims and Methodology of this Thesis . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.1 Aims and Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.2 Methodology and Scope . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Structure of this Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 Compositionality and Semantic Complexity 11
2.1 Formal And Computational Semantics . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.1 First Order Logic and Higher Order Logic . . . . . . . . . . . . . . . . 11
2.1.2 Compositional Translations and Grammars . . . . . . . . . . . . . . . . 14
2.2 Semantic Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 Pratt and Third’s Fragments of English . . . . . . . . . . . . . . . . . . . . . . . 19
2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3 Ontology Languages and Conjunctive Queries 23
3.1 Description Logic Ontologies . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1.1 Ontology Languages and DL-Lite . . . . . . . . . . . . . . . . . . . . . 23
3.1.2 Basic Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Conjunctive and Tree-Shaped Queries . . . . . . . . . . . . . . . . . . . . . . . 28
3.3 Reasoning Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.4 Related Formalisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.5 Expressing Ontologies and Queries with Controlled English . . . . . . . . . . . 33
3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4 Expressing DL-Lite and Tree-Shaped Queries 35
4.1 Lite-English . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.1.1 Expressing DL-Liteu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.1.2 Expressing DL-LiteF,u and DL-LiteR,u . . . . . . . . . . . . . . . . . . 41
4.1.3 Expressive Power of Lite-English . . . . . . . . . . . . . . . . . . . . . 45
v
vi Contents
4.1.4 DL-Liteu and Disjunction . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.2 GCQ-English . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3 Data and Combined Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5 Expressing Aggregate Queries 57
5.1 Aggregate Tree-Shaped Queries . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.1.1 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.1.2 Certain Answers Semantics . . . . . . . . . . . . . . . . . . . . . . . . 60
5.2 ATCQ-English . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.2.1 Expressing Aggregate and Non-Aggregate Queries . . . . . . . . . . . . 64
5.2.2 Adequateness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.3 Bags, Nested Queries and Ambiguity . . . . . . . . . . . . . . . . . . . . . . . . 75
5.4 Comparisons, _, ¬ and 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.5 Data Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.5.1 _-(A)TCQs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.5.2 ¬- and 8-(A)TCQs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.5.3 (¬)-(A)TCQs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6 DL-English and the {IS-Ai}i2[0,7] Family 85
6.1 Expressing the Description Logic ALCI with DL-English . . . . . . . . . . . . 85
6.2 The family {IS-Ai}i2[0,7] of Controlled Languages. . . . . . . . . . . . . . . . . 93
6.3 Data Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.3.1 Minimal Intractable Constructs . . . . . . . . . . . . . . . . . . . . . . . 97
6.3.2 Maximal Tractable Constructs . . . . . . . . . . . . . . . . . . . . . . . 97
6.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
7 The Complexity of Pratt and Third’s Fragments 99
7.1 First Order Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
7.2 Refinements of Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
7.3 Resolution Decision Procedures and Data Complexity . . . . . . . . . . . . . . . 108
7.4 The Positive Fragments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
7.5 The Fragments of English. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
7.5.1 Fragments with Tractable Data Complexity . . . . . . . . . . . . . . . . 114
7.5.2 Fragments with Intractable Data Complexity . . . . . . . . . . . . . . . 118
7.5.3 Combined Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
7.5.4 Undecidable Fragments . . . . . . . . . . . . . . . . . . . . . . . . . . 122
7.5.5 Enriching the Interrogative and Declarative Fragments . . . . . . . . . . 122
7.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
8 Conclusions 129
Bibliography 133
Index 141
Curriculum Vitae and Publications 143