Abstract
This paper introduces $CFDI^\forall_{kc}$, a novel Description Logic designed for Ontology-Based Data Access (OBDA). While traditional feature logics often face exponential complexity when incorporating conjunctions or partial features, $CFDI^\forall_{kc}$ achieves polynomial-time tractability by introducing a parameter $k$ to limit conjunction size. We demonstrate how this logic effectively models "defined concepts" and simulates partial features—attributes that may be inapplicable to certain objects—within a total feature framework. Our results show that key reasoning tasks, including knowledge base consistency and conjunctive query answering, are parameter-tractable, offering a scalable solution for complex data modeling.
Introduction
In the domain of Ontology-Based Data Access (OBDA), formal logics serve as a bridge, providing a unified conceptual view over heterogeneous relational databases. The CFD family of logics has been a cornerstone in this field due to its ability to handle functional dependencies—such as an employee ID uniquely determining a name—while maintaining polynomial-time (PTIME) reasoning.
However, these logics have historically suffered from two significant limitations. First, they lacked support for "defined concepts," making it difficult to categorize objects based on intersections (e.g., defining a StudentWorker as both a Student and an Employee). Second, they operated under a "total features" assumption, where every attribute is assumed to apply to every object. In real-world databases, many attributes are inapplicable to certain categories (e.g., a Building does not have a salary). Adding the expressivity to handle these cases typically pushes reasoning complexity to EXPTIME-complete, rendering it unfeasible for large-scale data.
Formal Framework: Syntax and Semantics
To address these limitations, we propose the logic $CFDI^\forall_{kc}$. The core innovation is the introduction of a parameter $k$, which represents a limit on the number of conjunctions considered during reasoning. This allows for a "middle ground" that increases expressivity without sacrificing tractability.
The syntax of $CFDI^\forall_{kc}$ distinguishes between concept constructors $C$ and $D$. As shown in Figure 1, $C$ allows for atomic concepts, universal quantification over path functions, and conjunctions. The constructor $D$ extends this to include bottom ($\bot$), inverse feature existence, and a specialized $k$-ary dependency rule: $C : \text{Pf}_1, \dots, \text{Pf}_k \to \text{Pf}$. This rule captures the notion that within concept $C$, the values of path functions $\text{Pf}_1, \dots, \text{Pf}_k$ uniquely determine the value of $\text{Pf}$.
Reasoning and Parameter-Tractability
The tractability of $CFDI^\forall_{kc}$ hinges on the "restricted conjunction" condition. We posit that if a large conjunction implies a concept, a smaller subset of size at most $k$ must also imply it. This parameterization allows us to bound the complexity of reasoning.
The reasoning process involves two main stages:
- TBox Closure: A set of rules computes all "small" implied subsumptions. This process is polynomial in the size of the TBox ($|T|$) but exponential in $k$. Given that $k$ is typically small in practical applications, this remains efficient.
- ABox Completion: To verify the consistency of a database (ABox) against the TBox rules, completion rules propagate facts and manage equality across the data.
We formally prove that critical problems—including TBox diagnosis, concept satisfiability, knowledge base consistency, and conjunctive query answering—are all parameter-tractable in $k$. The reasoning complexity is bounded by $O(|T|^k + |T||A|^2)$, ensuring scalability with data size.
Simulating Partial Features
A significant contribution of this work is the simulation of partial features. In standard feature logics, features are total. We demonstrate that by utilizing a special "existence" concept and our new conjunction rules, we can model a world where features are partial (can be undefined). For instance, we can explicitly forbid certain attributes for specific categories (e.g., Building \sqcap \exists salary \sqsubseteq \bot), effectively modeling "null inapplicable" values within an open-world assumption. We provide a mapping that transforms any terminology with partial features into a standard $CFDI^\forall_{(k+1)c}$ terminology.
Conclusion and Future Work
$CFDI^\forall_{kc}$ provides a powerful yet tractable framework for OBDA, aligning Description Logics more closely with real-world data modeling practices like UML. By capping reasoning depth with $k$, we achieve a logic significantly more expressive than its predecessors while remaining in the PTIME complexity class for any fixed $k$.
Future research will focus on addressing "object ID invention"—the creation of placeholder identifiers for anonymous objects—and integrating this logic with "referring expressions." Additionally, empirical evaluation within a real-world OBDA engine is a necessary step to validate performance against traditional SQL-based systems.
Summary updated