Reasonable Highly Expressive Query Languages


Pierre Bourhis, Markus Krötzsch, Sebastian Rudolph

Reasonable Highly Expressive Query Languages

Abstract. Expressive query languages are gaining relevance in knowledge representation (KR), and new reasoning problems come to the fore. Especially query containment is interesting in this context. The problem is known to be decidable for many expressive query languages, but exact complexities are often missing. We introduce a new query language, guarded queries (GQ), which generalizes most known languages where query containment is decidable. GQs can be nested (more expressive), or restricted to linear recursion (less expressive). Our comprehensive analysis of the computational properties and expressiveness of (linear/nested) GQs also yields insights on many previous languages.

Published at IJCAI 2015 (Conference paper)

Download PDF (last update: Jul 25 2015)

Citation details


This work was awarded with the title IJCAI-15 Distinguished Paper (Honorable Mention) (as one of three award papers among 1996 submissions).

The PDF linked above is the camera ready version of the IJCAI paper. For further details, please see the extended technical report with full proofs. You can also download the poster presented at IJCAI.

You can view the presentation in any modern browser. It was prepared using Sozi and Inkscape; many thanks to these projects.


Query languages, Rule languages