Abstract:
In the field of computer science known as “knowledge representation,” the following paradigm has become standard in recent years. A knowledge base refers to an architecture that combines data, general knowledge, and a reasoning mechanism that can generate new information from the underlying data and knowledge, using it to answer user queries. In this survey, we focus on the scenario where the data consists of a set of ground atoms, the knowledge is represented by an ontology in some description logic, and the query language is conjunctive queries. The aim of this work is to consolidate both theoretical and practical results about the computational complexity of query answering procedures, depending on the semantics, that is, the formal definition of what constitutes an answer to a query.
Fulltext:
PDF file (659 kB)