DROPS

Document

DOI: 10.4230/OASIcs.ICLP.2017.3

Reasoning on anonymity in Datalog+/-

Authors: Giovanni Amendola, Nicola Leone, Marco Manna, and Pierfrancesco Veltri

Published in: OASIcs, Volume 58, Technical Communications of the 33rd International Conference on Logic Programming (ICLP 2017)

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.

Cite as

Giovanni Amendola, Nicola Leone, Marco Manna, and Pierfrancesco Veltri. Reasoning on anonymity in Datalog+/-. In Technical Communications of the 33rd International Conference on Logic Programming (ICLP 2017). Open Access Series in Informatics (OASIcs), Volume 58, pp. 3:1-3:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{amendola_et_al:OASIcs.ICLP.2017.3,
  author =	{Amendola, Giovanni and Leone, Nicola and Manna, Marco and Veltri, Pierfrancesco},
  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 =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-058-3},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{58},
  editor =	{Rocha, Ricardo and Son, Tran Cao and Mears, Christopher and Saeedloei, Neda},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ICLP.2017.3},
  URN =		{urn:nbn:de:0030-drops-84587},
  doi =		{10.4230/OASIcs.ICLP.2017.3},
  annote =	{Keywords: Datalog, query answering, Datalog+/-, ontologies, expressiveness}
}

Search Results

Documents authored by Veltri, Pierfrancesco

Reasoning on anonymity in Datalog+/-

Abstract

Cite as

Thanks for your feedback!

Could not send message