Expressive Recursive Answers for Ontological Knowledge Bases

A fundamental use of knowledge bases (KBs) is query answering, i.e., retrieving the information entailed by the KB in response to a user query. When both the KB and the query are specified as logical formulae, the standard form of answer provided to users is certain answers (CAs): tuples of constants that satisfy the query in every model of the KB. Despite their wide adoption, CAs are known to be just a lossy representation of the information that a KB and a query provide. However, while several alternative forms of answers have been proposed, no general consensus has emerged on the most suitable approach to answer queries over ontological KBs. In this paper, we introduce Regularly Recurrent Answers (RRAs), a novel form of answer for queries over ontological KBs. RRAs support the representation of infinite sets of tuples via a generation mechanism based on regular expressions. Such a simple mechanism allows RRAs to represent a fundamental fragment of the certain information entailed by Unions of Conjunctive Queries over DL-Lite KBs. The contribution of this paper includes the formal definition of RRAs, a formal characterization of their informativeness, and a study of their computational characteristics.