TLDR: This research paper explores Controlled Query Evaluation (CQE) using Epistemic Dependencies (EDs) to manage sensitive information in ontologies. It focuses on “IGA-entailment,” where queries are answered based on information common to all maximal safe disclosures. While generally computationally hard, the paper identifies a class of EDs (full and expandable) for which efficient First-Order (FO) rewriting is possible. Experiments validate the practical feasibility of their rewriting algorithm, demonstrating its potential for secure data access in real-world applications.
In the evolving landscape of data management, particularly with the increasing volume of structured and semantically rich data, ensuring data security and privacy has become paramount. Fields like healthcare and finance heavily rely on ontologies – formal systems that define shared vocabularies and relationships – to organize and retrieve complex information. While these systems offer powerful querying capabilities, they also present a challenge: how to prevent the unintentional disclosure of sensitive information through seemingly harmless queries, especially when considering the underlying logical rules of the ontology.
This is where Controlled Query Evaluation (CQE) comes into play. CQE is a framework designed to mediate access to data, ensuring that only information compliant with a predefined data protection policy is revealed through queries. Traditionally, these policies have been expressed using “denials,” which specify information that must remain hidden. However, recent advancements have introduced a more expressive language for these policies: Epistemic Dependencies (EDs).
A new research paper, titled CQE under Epistemic Dependencies: Algorithms and Experiments, delves into the application of CQE over ontologies, specifically integrating these advanced Epistemic Dependencies. The paper focuses on a particular approach within CQE known as “optimal GA censors.” A GA censor is essentially a maximal set of factual statements (ground atoms) that can be safely disclosed from an ontology without violating the data protection policy. The core idea explored in this research is answering queries with respect to the intersection of all such optimal GA censors – a method referred to as IGA-entailment. This approach is known to offer strong security guarantees and favorable computational behavior in other contexts.
Understanding Epistemic Dependencies and IGA-Entailment
Epistemic Dependencies (EDs) are logical rules that dictate information disclosure. They are expressed as implications between two queries, each within the scope of a “knowledge” operator (K). For instance, a policy might state: “If it is known that someone has a salary, then it must also be known that they are a manager.” This means that if the system can infer a salary, it must also be able to disclose the managerial status, or the salary information cannot be revealed. If the head of an ED is “false” (K⊥), it acts as a denial, meaning the body of the ED must never be revealed.
The concept of IGA-entailment is central to this work. When a query is IGA-entailed, it means that the query is true not just in one safe disclosure scenario, but in the intersection of *all* possible maximal safe disclosures. This ensures that only information common to all optimal ways of protecting data is revealed, providing a very robust security posture.
Computational Challenges and Solutions
A significant part of the research addresses the computational complexity of IGA-entailment, particularly when dealing with DL-LiteR ontologies – a family of Description Logics designed for efficient query answering. The paper investigates whether IGA-entailment can be “FO-rewritable,” meaning the query can be transformed into a standard First-Order (FO) logic query that can then be efficiently evaluated over a database. FO-rewritability is highly desirable as it implies the same computational efficiency as evaluating a typical SQL query.
The findings reveal that while IGA-entailment is generally computationally challenging (NL-hard for linear EDs and coNP-hard for full EDs), the researchers identified a specific class of EDs – “full and expandable EDs” – for which FO-rewritability is indeed possible. Full EDs are those where no existential variable appears in the head of the rule, and expandable EDs are those for which a certain set of logical dependencies is UCQ-rewritable (a property related to how queries can be rewritten).
To achieve this, the paper presents a detailed first-order rewriting algorithm. This algorithm transforms a Boolean Union of Conjunctive Queries (BUCQs) into a new FO query that depends only on the ontology’s TBox (intensional axioms) and the policy, not on the specific data (ABox). This rewritten query can then be evaluated directly on the ABox, which is typically stored in a relational database.
Experimental Validation
To demonstrate the practical feasibility of their rewriting function, the researchers conducted experiments using the OWL2Bench benchmark, a standard for OWL ontologies. They tested their approach on ABoxes of varying sizes, representing data about 5 and 10 universities (approximately 325,000 and 710,000 factual assertions, respectively). The ABoxes were stored in an SQL database, allowing the rewritten FO queries to be evaluated by the SQL system.
The experiments focused on two specific classes of EDs: full and linear EDs (specifically, a subclass called “binary EDs”) and full and acyclic EDs. The results showed that in most cases, the query evaluation time was acceptable, typically within seconds. The time required to compute the rewritten query itself was consistently low, usually under 3 seconds, and did not significantly depend on the size of the ABox. This empirical validation confirms that the proposed method is not only theoretically sound but also practically viable for real-world applications.
Also Read:
- Bridging Open and Closed Worlds: A New Approach to Automated Planning with Ontologies
- Unpacking the Nuances of AI Explanations: Facets and Diversity in Abductive Reasoning
Future Directions
The research opens several avenues for future work. The authors plan to develop practical algorithms for the cases where IGA-entailment is not FO-rewritable. They also aim to extend the identified FO-rewritable cases to broader subclasses of EDs or even entirely new policy languages. Furthermore, exploring the complexity of CQE under EDs for Description Logics other than DL-LiteR, and integrating this approach into the broader framework of ontology-based data access (OBDA), are also key future objectives.
