Abstract
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