Ontology-Mediated Query Answering Using Graph Patterns with Conditions

This paper proposes an extension of graph patterns, referred to as ontological graph patterns (OGPs), to accelerate ontology-mediated query answering. OGPs employ graph patterns to support topological queries, attach conditions to both vertices and edges to specify additional restrictions, and support conditional partial matching semantics. Hence, OG Ps can express conjunctive queries (CQs) under ontological constraints. We develop a PTIME algorithm to generate an equivalent OGP from a CQ over the ontology specified by description logic$DL-Lite_{\mathcal{R}}$, and design a matching algorithm to match OGPs in graphs. Using real-life and synthetic data, we experimentally verify that the proposed approach outperforms the state-of-the-art algorithms for ontology-mediated query answering by 2–3 orders of magnitude.