## Finite Open World Querying with Number Restrictionss

* Antoine Amarilli * and * Michael
Benedikt*
Open-world query answering is the problem of deciding, given a set of facts,
conjunction of constraints, and query, whether the
facts and constraints imply the query.
This amounts to
reasoning over all instances that include the facts and satisfy the constraints.
We study finite open-world query answering (FQA), which assumes that the underlying world
is finite and thus only reasons on the finite
completions of the instance.
The major known decidable cases of FQA
derive from the following: the guarded fragment of first-order logic, which can express referential constraints (data in one
place points to data in another) but cannot express number restrictions such
as functional dependencies; and the guarded fragment with number restrictions but
on a signature of arity only two.
In this paper, we give the first decidability results for FQA that
combine both referential constraints and number
restrictions
for arbitrary
signatures: we show that, for unary inclusion dependencies and functional
dependencies, the finiteness assumption of FQA can be lifted up to taking the finite implication closure of
the dependencie.
Our result relies on new techniques to construct finite universal models of such
constraints, for any bound on maximal query size.

*Accepted at LICS* 2015. 12 pages.

© 2015 Antoine Amarilli and Michael Benedikt.