Polynomial Combined Rewritings for Existential Rules

ABSTRACT. We consider the scenario of ontology-based data access where a conjunctive query is evaluated against an ontological database. It is generally accepted that true scalability of conjunctive query answering in this setting can only be achieved by using standard relational database management systems (RDBMSs). An approach to conjunctive query answering that enables the use of RDBMSs is the so-called polynomial combined approach. We investigate this approach for the main guarded- and sticky-based classes of existential rules, and we highlight the assumptions on the underlying schema which are sufficient for the polynomial combined first-order rewritability of those classes. To the best of our knowledge, this is the first work which explicitly studies the polynomial combined approach for existential rules.