Indistinguishability in controlled query evaluation over prioritized description logic ontologies
In this paper we study Controlled Query Evaluation (CQE), a declarative approach to privacy-preserving query answering over databases, knowledge bases, and ontologies. CQE is based on the notion of censor, which defines the answers to each query posed to the data/knowledge base. We investigate both...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2025-01-01
|
| Series: | Web Semantics |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S1570826824000271 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841545582012792832 |
|---|---|
| author | Gianluca Cima Domenico Lembo Lorenzo Marconi Riccardo Rosati Domenico Fabio Savo |
| author_facet | Gianluca Cima Domenico Lembo Lorenzo Marconi Riccardo Rosati Domenico Fabio Savo |
| author_sort | Gianluca Cima |
| collection | DOAJ |
| description | In this paper we study Controlled Query Evaluation (CQE), a declarative approach to privacy-preserving query answering over databases, knowledge bases, and ontologies. CQE is based on the notion of censor, which defines the answers to each query posed to the data/knowledge base. We investigate both semantic and computational properties of CQE in the context of OWL ontologies, and specifically in the description logic DL-LiteR, which underpins the OWL 2 QL profile. In our analysis, we focus on semantics of CQE based on censors (called optimal GA censors) that enjoy the so-called indistinguishability property, analyzing the trade-off between maximizing the amount of data disclosed by query answers and minimizing the computational cost of privacy-preserving query answering. We first study the data complexity of skeptical entailment of unions of conjunctive queries under all the optimal GA censors, showing that the computational cost of query answering in this setting is intractable. To overcome this computational issue, we then define a different semantics for CQE centered around the notion of intersection of all the optimal GA censors. We show that query answering over OWL 2 QL ontologies under the new intersection-based semantics for CQE enjoys tractability and is first-order rewritable, i.e. amenable to be implemented through SQL query rewriting techniques and the use of standard relational database systems; on the other hand, this approach shows limitations in terms of amount of data disclosed. To improve this aspect, we add preferences between ontology predicates to the CQE framework, and identify a semantics under which query answering over OWL 2 QL ontologies maintains the same computational properties of the intersection-based approach without preferences. |
| format | Article |
| id | doaj-art-59010b62b2b8400896aeff001f48e09f |
| institution | Kabale University |
| issn | 1570-8268 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Web Semantics |
| spelling | doaj-art-59010b62b2b8400896aeff001f48e09f2025-01-12T05:24:29ZengElsevierWeb Semantics1570-82682025-01-0184100841Indistinguishability in controlled query evaluation over prioritized description logic ontologiesGianluca Cima0Domenico Lembo1Lorenzo Marconi2Riccardo Rosati3Domenico Fabio Savo4Sapienza Università di Roma, ItalySapienza Università di Roma, Italy; Corresponding author.Sapienza Università di Roma, ItalySapienza Università di Roma, ItalyUniversità degli Studi di Bergamo, ItalyIn this paper we study Controlled Query Evaluation (CQE), a declarative approach to privacy-preserving query answering over databases, knowledge bases, and ontologies. CQE is based on the notion of censor, which defines the answers to each query posed to the data/knowledge base. We investigate both semantic and computational properties of CQE in the context of OWL ontologies, and specifically in the description logic DL-LiteR, which underpins the OWL 2 QL profile. In our analysis, we focus on semantics of CQE based on censors (called optimal GA censors) that enjoy the so-called indistinguishability property, analyzing the trade-off between maximizing the amount of data disclosed by query answers and minimizing the computational cost of privacy-preserving query answering. We first study the data complexity of skeptical entailment of unions of conjunctive queries under all the optimal GA censors, showing that the computational cost of query answering in this setting is intractable. To overcome this computational issue, we then define a different semantics for CQE centered around the notion of intersection of all the optimal GA censors. We show that query answering over OWL 2 QL ontologies under the new intersection-based semantics for CQE enjoys tractability and is first-order rewritable, i.e. amenable to be implemented through SQL query rewriting techniques and the use of standard relational database systems; on the other hand, this approach shows limitations in terms of amount of data disclosed. To improve this aspect, we add preferences between ontology predicates to the CQE framework, and identify a semantics under which query answering over OWL 2 QL ontologies maintains the same computational properties of the intersection-based approach without preferences.http://www.sciencedirect.com/science/article/pii/S1570826824000271Description logicsOntologiesConfidentiality preservationQuery answeringData complexity |
| spellingShingle | Gianluca Cima Domenico Lembo Lorenzo Marconi Riccardo Rosati Domenico Fabio Savo Indistinguishability in controlled query evaluation over prioritized description logic ontologies Web Semantics Description logics Ontologies Confidentiality preservation Query answering Data complexity |
| title | Indistinguishability in controlled query evaluation over prioritized description logic ontologies |
| title_full | Indistinguishability in controlled query evaluation over prioritized description logic ontologies |
| title_fullStr | Indistinguishability in controlled query evaluation over prioritized description logic ontologies |
| title_full_unstemmed | Indistinguishability in controlled query evaluation over prioritized description logic ontologies |
| title_short | Indistinguishability in controlled query evaluation over prioritized description logic ontologies |
| title_sort | indistinguishability in controlled query evaluation over prioritized description logic ontologies |
| topic | Description logics Ontologies Confidentiality preservation Query answering Data complexity |
| url | http://www.sciencedirect.com/science/article/pii/S1570826824000271 |
| work_keys_str_mv | AT gianlucacima indistinguishabilityincontrolledqueryevaluationoverprioritizeddescriptionlogicontologies AT domenicolembo indistinguishabilityincontrolledqueryevaluationoverprioritizeddescriptionlogicontologies AT lorenzomarconi indistinguishabilityincontrolledqueryevaluationoverprioritizeddescriptionlogicontologies AT riccardorosati indistinguishabilityincontrolledqueryevaluationoverprioritizeddescriptionlogicontologies AT domenicofabiosavo indistinguishabilityincontrolledqueryevaluationoverprioritizeddescriptionlogicontologies |