Nested Regular Path Queries in Description Logics (Extended Abstract)

Proc. of the 8th Alberto Mendelzon Int. Workshop on Foundations of Data Management (AMW 2014). Volume 1189 of CEUR Workshop Proceedings, https://ceur-ws.org/. 2014.

We consider the extension of two-way regular path queries (2RPQs) with nesting, which allows one to require that objects along a path satisfy complex conditions, in turn expressed through (nested) 2RPQs. We study the computational complexity of answering nested 2RPQs and conjunctions thereof (CN2RPQs) in the presence of domain knowledge expressed in description logics (DLs). We establish tight complexity bounds in data and combined complexity for a variety of DLs, ranging from lightweight DLs up to highly expressive ones.

@inproceedings{AMW-2014-nested-rpqs,
   title = "Nested Regular Path Queries in Description Logics (Extended
Abstract)",
   year = "2014",
   author = "Meghyn Bienvenu and Diego Calvanese and Magdalena Ortiz and
Mantas Simkus",
   booktitle = "Proc. of the 8th Alberto Mendelzon Int. Workshop on
Foundations of Data Management (AMW 2014)",
   volume = "1189",
   publisher = "CEUR-WS.org",
   series = "CEUR Workshop Proceedings, https://ceur-ws.org/",
}