Relaxing and Restraining Queries for OBDA

Medina Andresel, Yazmín Ibáñez-García, Magdalena Ortiz, Mantas SimkusAAAI 2019 · DOI

This paper, presented at AAAI-19, explores how to make database exploration more intuitive by using ontologies to automatically broaden or narrow user queries. The authors extend the popular DL-Lite framework for Ontology-Based Data Access (OBDA) to support "Complex Role Inclusions," allowing queries to navigate hierarchical data (like geography or time) more effectively.

The Challenge of Multi-Dimensional Hierarchies

In Ontology-Based Data Access (OBDA), users query a database through a conceptual "lens" (the ontology). While standard OBDA is great at finding exact answers, it is often a "hit or miss" experience. If a query for "Concerts in Vienna" returns zero results, the user might want to relax the query to "Cultural Events in Vienna" or "Concerts in Austria." Conversely, if there are too many results, they might want to restrain it to "Opera Performances in the State Opera."

Hierarchical relationship between venues, cities, and countries used as a running example for query relaxation.

The challenge is that standard OBDA logics (like the DL-Lite family) struggle with multi-dimensional hierarchies. For example, expressing that "an event occurring in a venue, which is located in a city, occurs in that city" requires Complex Role Inclusions (CRIs). Usually, adding CRIs makes query answering much harder (computationally expensive), often breaking the "First-Order (FO) rewritability" that allows OBDA to work efficiently with standard SQL databases.

Proposed Methods: Balancing Expressivity and Performance

The authors propose a middle ground that adds expressive power without sacrificing performance through several key innovations:

  1. Recursion-Safe DL-Lite$^{HR}$: They introduce a restricted version of DL-Lite that allows CRIs (e.g., $role1 \cdot role2 \sqsubseteq role3$) but prevents "dangerous" cycles that would lead to infinite loops or exponential complexity.
  2. k-bounded ABoxes: They identify a condition on the data (the ABox) where hierarchical paths have a limited length. In these settings, they prove that queries remain FO-rewritable—meaning they can still be translated into efficient SQL.
  3. Reformulation Rules: They define two types of rules for modifying queries:
  4. Ontology-based: Uses the schema (TBox) to move up or down a hierarchy (e.g., changing "Concert" to "Event").
  5. Data-dependent: Uses the actual state of the database to suggest changes. If the data shows that every "Venue" in the system is currently located in a "City," the system can use that specific fact to help the user navigate, even if it's not a universal rule in the ontology.
  6. Dimensional Navigation: They formalize "roll-up" and "drill-down" operations—standard in business intelligence (OLAP)—within the logic-based OBDA framework.

Key Insights and Results

  • Duality of Rewriting: The authors realized that the same logic used to answer queries in OBDA can be "flipped" to relax them. Standard rewriting rules move from specific to general; by formalizing the "counterparts" to these rules, they created a systematic way to broaden searches.
  • Guarded Recursion: You don't have to ban recursion entirely to keep things fast. By ensuring recursive roles are "guarded" by simple roles that aren't existentially implied, you can maintain tractability.
  • Complexity Bounds: They proved that for their "recursion-safe" fragment, checking if a dataset is compatible with these rules is feasible in PTIME (Polynomial Time), and query answering remains in $AC^0$ for data complexity (the gold standard for database efficiency).
  • Formalized OLAP in OBDA: They provided the first rigorous logical foundation for performing "drill-down" and "roll-up" operations over ontology-mediated databases.

Limitations and Future Work

The efficiency of this approach relies on "k-boundedness." While common in many hierarchical datasets (like geography), it might not hold for data with very deep or arbitrary graph structures. Furthermore, while the paper provides the rules for relaxation, it doesn't address the ranking problem: if a query can be relaxed in ten different ways, the system must determine which is most relevant to the user. The authors suggest that the next step is to create a user-friendly query language that incorporates these "relax" and "restrain" operators as first-class citizens.

Summary updated

BibTeX
@inproceedings{andresel2019relaxing,
  author = {Medina Andresel and Yazmín Ibáñez-García and Magdalena Ortiz and Mantas Simkus},
  title = {{Relaxing and Restraining Queries for OBDA}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33012654},
}
Figure