Description Logics (DLs) are a family of logics specially tailored for knowledge representation and reasoning, widely appreciated for their suitability for representing complex structures of knowledge. They provide reasoning services over knowledge bases describing application domains, and have been deployed in a wide range of fields. Current DL systems, however, lack suitable means access the information they describe, which is a big limitation in several application areas.
For this reason, answering database-like queries over knowledge bases has become an important research topic. However, for the so-call expressive DLs only few algorithms for query answering were available and little was known about the computational costs of the problem. In this thesis we study query answering in expressive DLs, explore novel reasoning techniques with the emphasis on worst-case optimal algorithms, and derive new computational complexity results. First we use rich models of automata to develop a query answering algorithm that supports most of the popular modeling constructs. This allows us to significantly push the frontier of decidability and complexity upper bounds for query answering to very expressive DLs and very reach query languages. As second tool we employ the knot technique to develop algorithms with a more refined control of the sources of complexity, obtaining improved complexity upper bounds in some cases. Such algorithms are also optimal in data complexity. They are also appealing for implementations, as they support knowledge compilation and encodings into Datalog. Finally, we identify transitive roles and role inclusions as a costly pair of constructors that makes query answering theoretically harder that standard reasoning.
This helps us to characterize the precise complexity of query answering in a wide range of expressive DLs.