Answering Metaqueries over Hi (OWL 2 QL) Ontologies

Maurizio Lenzerini, Lorenzo Lepore, Antonella PoggiIJCAI 2016

Abstract

Metaquerying—the ability to use variables that range over classes and properties—is a powerful tool for knowledge representation but faces significant semantic and computational hurdles in standard OWL 2 QL. This paper introduces $Hi(OWL 2 QL)$, a framework based on Higher-Order Semantics (HOS) that enables polymorphic entities and complex metaqueries. We propose the Lazy Metagrounding (LMG) algorithm, which optimizes query execution by evaluating schema-level constraints before data-level assertions. Our evaluation shows that LMG achieves dramatic performance improvements, often reducing query times from several hours to under two seconds, while preserving the desirable $AC^0$ data complexity for TBox-complete ontologies.

Introduction

In standard Semantic Web languages like OWL 2, a strict "typing constraint" separates individuals, classes, and properties. This rigid structure complicates metamodeling; for instance, treating a class like Lion as an instance of EndangeredSpecies is not natively supported under standard Direct Semantics. Furthermore, "metaqueries"—queries where variables can occupy predicate positions—are often computationally explosive or prohibited.

This research addresses these limitations by adopting $Hi(OWL 2 QL)$, which utilizes Higher-Order Semantics. This approach allows entities to act as individuals, classes, and properties simultaneously, enabling "full metaqueries" that integrate data (ABox) and schema (TBox) assertions without the traditional typing restrictions.

Methodology

The core of this work lies in the theoretical analysis of $Hi(OWL 2 QL)$ and the development of the Lazy Metagrounding (LMG) algorithm.

Higher-Order Semantics and TBox-Completeness

By employing a semantics based on HiLog, variables can appear in predicate positions without compromising the underlying logic. The authors identify a class of "TBox-complete" ontologies where schema-level uncertainty is minimized. For these ontologies, query answering remains highly efficient, maintaining $AC^0$ data complexity.

The Lazy Metagrounding (LMG) Algorithm

Standard metagrounding involves replacing every meta-variable with every possible class or property name, leading to a combinatorial explosion. LMG avoids this "blind" approach by building a dependency graph of query atoms and prioritizing TBox-First Evaluation. Since the schema is typically much smaller than the data, LMG uses these results to "bind" variables before querying the massive ABox. This heuristic prunes the search space significantly before expensive data-level operations occur.

Experimental Evaluation

The approach was tested using a knowledge base consisting of approximately 100,000 ABox axioms and 260 TBox axioms. Eight benchmark metaqueries ($Q_1$ through $Q_8$) were designed to evaluate various combinations of individual and predicate variables.

Results

The LMG algorithm was compared against a "Naive" metagrounding approach. The results, summarized in Figure 1, demonstrate the efficiency of the LMG strategy.

Comparison of Lazy Metagrounding (LMG) vs. Naive approach across eight benchmark queries.

As shown in the table, LMG provides orders-of-magnitude improvements in execution time. For queries $Q_3$ through $Q_7$, where the Naive approach timed out after 3 hours, LMG returned results in less than 2 seconds. Even in cases like $Q_2$ and $Q_8$, where the Naive approach eventually finished, LMG reduced the processing time from minutes to sub-second intervals. These results validate the "TBox-first" heuristic, showing that solving logic at the schema level effectively manages the scale of the data.

Discussion and Future Work

The research proves that metaquerying does not necessarily add to the data complexity of OWL 2 QL, making it viable for big data applications. However, the current efficiency gains are most pronounced in "TBox-complete" ontologies. Future work will explore extending this framework to include data properties (attributes like price or age) and investigating more expressive variants of $Hi(OWL 2 QL)$ that incorporate integrity constraints or complex property chains.

Summary updated

BibTeX
@inproceedings{lenzerini2016answering,
  author = {Maurizio Lenzerini and Lorenzo Lepore and Antonella Poggi},
  title = {{Answering Metaqueries over Hi (OWL 2 QL) Ontologies}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}

Loading related content...

Figure