TY - GEN
T1 - Ontology-mediated query answering for key-value stores
AU - Bienvenu, Meghyn
AU - Bourhis, Pierre
AU - Mugnier, Marie Laure
AU - Tison, Sophie
AU - Ulliana, Federico
PY - 2017/1/1
Y1 - 2017/1/1
N2 - We propose a novel rule-based ontology language for JSON records and investigate its computational properties. After providing a natural translation into first-order logic, we identify relationships to existing ontology languages, which yield decidability of query answering but only rough complexity bounds. By establishing an interesting and nontrivial connection to word rewriting, we are able to pinpoint the exact combined complexity of query answering in our framework and obtain tractability results for data complexity. The upper bounds are proven using a query reformulation technique, which can be implemented on top of key-value stores, thereby exploiting their querying facilities.
AB - We propose a novel rule-based ontology language for JSON records and investigate its computational properties. After providing a natural translation into first-order logic, we identify relationships to existing ontology languages, which yield decidability of query answering but only rough complexity bounds. By establishing an interesting and nontrivial connection to word rewriting, we are able to pinpoint the exact combined complexity of query answering in our framework and obtain tractability results for data complexity. The upper bounds are proven using a query reformulation technique, which can be implemented on top of key-value stores, thereby exploiting their querying facilities.
UR - https://www.scopus.com/pages/publications/85031913562
U2 - 10.24963/ijcai.2017/117
DO - 10.24963/ijcai.2017/117
M3 - Conference contribution
AN - SCOPUS:85031913562
T3 - IJCAI International Joint Conference on Artificial Intelligence
SP - 844
EP - 851
BT - 26th International Joint Conference on Artificial Intelligence, IJCAI 2017
A2 - Sierra, Carles
PB - International Joint Conferences on Artificial Intelligence
T2 - 26th International Joint Conference on Artificial Intelligence, IJCAI 2017
Y2 - 19 August 2017 through 25 August 2017
ER -