  We investigate the problem of finite entailment of ontology-mediated queries.
We consider the expressive query language, unions of conjunctive regular path
queries (UCRPQs), extending the well-known class of union of conjunctive
queries, with regular expressions over roles. We look at ontologies formulated
using the description logic ALC, and show a tight 2EXPTIME upper bound for
entailment of UCRPQs. At the core of our decision procedure, there is a novel
automata-based technique introducing a stratification of interpretations
induced by the deterministic finite automaton underlying the input UCRPQ
