Abstract
An ontology language for ontology mediated query answering (OMQA-language) isuniversal for a family of OMQA-languages if it is the most expressive one amongthis family. In this paper, we focus on three families of tractableOMQA-languages, including first-order rewritable languages and languages whosedata complexity of the query answering is in AC0 or PTIME. On the negativeside, we prove that there is, in general, no universal language for each ofthese families of languages. On the positive side, we propose a novel property,the locality, to approximate the first-order rewritability, and show that thereexists a language of disjunctive embedded dependencies that is universal forthe family of OMQA-languages with locality. All of these results apply to OMQAwith query languages such as conjunctive queries, unions of conjunctive queriesand acyclic conjunctive queries.