TL;DR
This paper introduces a novel rule-based ontology language for querying JSON data stored in key-value (KV) stores. By translating these rules into first-order logic and leveraging word rewriting techniques, they achieve efficient query answering, with complexity bounds that are tractable for practical applications.
What Problem Does This Paper Address?
The increasing prevalence of semi-structured data, particularly in JSON format, stored in NoSQL key-value stores presents a challenge for traditional knowledge representation and reasoning systems. While ontology-mediated query answering (OMQA) has been successful with relational and RDF databases, adapting it to KV stores requires new approaches. The core problem is how to leverage domain ontologies to enrich queries over KV stores without requiring data migration to relational formats, thereby benefiting from the native optimizations of these stores.
Methods
The authors propose a new rule language for JSON records that allows expressing hierarchical properties, path inclusions, and mandatory paths. They establish a formal translation of these rules and queries into first-order logic, connecting them to existing ontology languages like description logics and existential rules. A key contribution is the development of a query reformulation technique. Instead of materializing the entire knowledge base, they reformulate the original query into a set of equivalent queries that can be executed directly on the KV store. This reformulation process is elegantly mapped to word rewriting systems, specifically extended rewriting suffix systems (ERS), which allows them to derive tight complexity bounds.
Datasets
Not discussed in the paper. The paper focuses on a formal framework and theoretical results, using a running example to illustrate concepts rather than evaluating on specific datasets.
Key Insights and Ideas
- Bridging the Gap: The paper successfully bridges the gap between semantic web technologies (ontologies) and modern NoSQL data stores (KV stores), a crucial step for integrating diverse data sources.
- Query Reformulation for KV Stores: The core idea of query reformulation is particularly well-suited for KV stores, as it avoids modifying the underlying data and leverages the store's native query capabilities.
- Word Rewriting as a Unifying Tool: The connection established between ontology rule application and word rewriting systems is a powerful theoretical insight, enabling the derivation of precise complexity bounds.
- Contextual Rules are Key (and Costly): The introduction of "contextual rules" is a significant feature for modeling the hierarchical nature of JSON, but it also increases the combined complexity of query answering.
Key Results
- Decidability and Tractability: The proposed framework guarantees decidability of query answering.
- Complexity Bounds:
- Data complexity is in NLSpace.
- Combined complexity is in PSpace.
- Combined complexity without contextual rules is in NLSpace.
- Lower Bounds: The paper establishes PSpace-hardness for combined complexity and NLSpace-hardness for combined complexity with context-free rules, suggesting their upper bounds are tight.
- Theoretical Foundation: The work provides a solid theoretical foundation for OMQA over KV stores, with a clear translation to first-order logic and existential rules.
Limitations and Future Work
- Complexity of Contextual Rules: While powerful, contextual rules significantly increase the combined complexity. The paper notes that this feature makes the combined complexity jump from NLogSpace-complete (without contexts) to PSpace-complete.
- Data Complexity Lower Bound: The paper explicitly states that the lower bound for data complexity remains an open question.
- Future Directions: The authors suggest extending the rule language to represent concepts associated with nodes and investigating query reformulation for richer KV queries, such as tree queries (e.g., as supported by MongoDB). They also mention the potential for using data-guides for more efficient query evaluation in practice.
Summary updated