License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ICLP.2017.3
URN: urn:nbn:de:0030-drops-84587
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8458/
Go to the corresponding OASIcs Volume Portal

Amendola, Giovanni ; Leone, Nicola ; Manna, Marco ; Veltri, Pierfrancesco

Reasoning on anonymity in Datalog+/-

pdf-format:
OASIcs-ICLP-2017-3.pdf (0.4 MB)

Abstract

In this paper we empower the ontology-based query answering framework with the ability to reason on the properties of “known” (non-anonymous) and anonymous individuals. To this end, we extend Datalog+/- with epistemic variables that range over “known” individuals only. The resulting framework, called datalog^{\exists,K}, offers good and novel knowledge representation capabilities, allowing for reasoning even on the anonymity of individuals. To guarantee effective computability, we define shyK, a decidable subclass of datalog^{\exists,K}, that fully generalizes (plain) Datalog, enhancing its knowledge modeling features without any computational overhead: OBQA for shyK keeps exactly the same (data and combined) complexity as for Datalog. To measure the expressiveness of shyK, we borrow the notion of uniform equivalence from answer set programming, and show that shyK is strictly more expressive than the DL ELH. Interestingly, shyK keeps a lower complexity, compared to other Datalog+/- languages that can express this DL.

BibTeX - Entry

@InProceedings{amendola_et_al:OASIcs:2018:8458,
  author =	{Giovanni Amendola and Nicola Leone and Marco Manna and Pierfrancesco Veltri},
  title =	{{Reasoning on anonymity in Datalog+/-}},
  booktitle =	{Technical Communications of the 33rd International Conference on Logic Programming (ICLP 2017)},
  pages =	{3:1--3:5},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-058-3},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{58},
  editor =	{Ricardo Rocha and Tran Cao Son and Christopher Mears and Neda Saeedloei},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8458},
  URN =		{urn:nbn:de:0030-drops-84587},
  doi =		{10.4230/OASIcs.ICLP.2017.3},
  annote =	{Keywords: Datalog, query answering, Datalog+/-, ontologies, expressiveness}
}

Keywords: Datalog, query answering, Datalog+/-, ontologies, expressiveness
Collection: Technical Communications of the 33rd International Conference on Logic Programming (ICLP 2017)
Issue Date: 2018
Date of publication: 14.02.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI