Navigational Queries Based on Frontier-Guarded Datalog: Preliminary Results.
Meghyn Bienvenu, Magdalena Ortiz, Mantas Šimkus · AMW · 2015
In this paper, we introduce a navigational query language that extends binary frontier-guarded Datalog by allowing regular expressions in rule bodies and a limited use of higher-arity intensional predicates. Our query language strictly extends conjunctive two-way regular path queries (C2RPQs) and captures some of the key features advocated in recent works aimed at extending C2RPQs. We compare our language to existing proposals and establish decidability with elementary complexity of query evaluation in the presence of ontologies.