Reasonable Highly Expressive Query Languages

Pierre BourhisPierre Bourhis, Markus KrötzschMarkus Krötzsch, Sebastian RudolphSebastian Rudolph

Download

Pierre Bourhis, Markus Krötzsch, Sebastian Rudolph
Reasonable Highly Expressive Query Languages
In Qiang Yang, Michael Wooldridge, eds., Proc. 24th International Joint Conference on Artificial Intelligence (IJCAI'15), 2826-2832, 2015. AAAI Press

Details
Bibtex

KurzfassungAbstract
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.
Bemerkung: Note: This work was awarded with the title IJCAI-15 Distinguished Paper (Honorable Mention) (as one of three award papers among 1996 submissions). Full proofs are found in the extended technical report.

You can view the presentation in any modern browser. It was prepared using Sozi and Inkscape; many thanks to these projects.
Projekt:Project: DIAMOND
Forschungsgruppe:Research Group: Computational LogicComputational Logic, Wissensbasierte SystemeKnowledge-Based Systems

@inproceedings{BKR2015,
  author    = {Pierre Bourhis and Markus Kr{\"{o}}tzsch and Sebastian Rudolph},
  title     = {Reasonable Highly Expressive Query Languages},
  editor    = {Qiang Yang and Michael Wooldridge},
  booktitle = {Proc. 24th International Joint Conference on Artificial
               Intelligence (IJCAI'15)},
  publisher = {AAAI Press},
  year      = {2015},
  pages     = {2826-2832}
}