DROPS

Document

DOI: 10.4230/LIPIcs.ICDT.2026.21

First-Order Rewritability of Rule-Based Ontology Mediated Queries with Negation

Authors: Georg Gottlob, Marco Manna, Andreas Pieris, and Aldo Ricioppo

Published in: LIPIcs, Volume 365, 29th International Conference on Database Theory (ICDT 2026)

Abstract

The idea of using an ontology to enrich user queries with domain knowledge has attracted considerable attention from the database and KR communities during the last fifteen years or so. The ontology and the user query can be conveniently seen as two components of one composite query, called ontology-mediated query (omq), while an omq language (OL,QL) collects all such omqs where the ontology is expressed using the ontology language OL and the user query comes from the query language QL. The evaluation problem for rule-based omq languages of the form (OL,CQ), where OL is a rule-based ontology language, i.e., it collects ontologies modelled using tuple-generating dependencies (a.k.a. existential rules), and CQ is the language of conjunctive queries, has been extensively studied in the literature. In particular, the notion of first-order rewritability of such languages, i.e., the property of being able to rewrite every omq from the language in question to an equivalent first-order query, has been studied in depth. This research effort led an algorithmic characterization of when a rule-based omq language (OL,CQ) is first-order rewritable. More precisely, there is a uniform algorithm Rewrite such that, for every rule-based ontology language OL, the omq language (OL,CQ) is first-order rewritable iff for every omq O from (OL,CQ), the algorithm Rewrite on input O terminates and constructs a first-order rewriting of O. The question that we are interested in is whether the above algorithmic characterization can be extended to rule-based omq languages of the form (OL,nCQ), where nCQ is the language of conjunctive queries with the useful feature of negation. The goal of this work is to initiate effort towards the settlement of the above highly non-trivial question. To this end, we provide a new algorithm, which is a non-trivial extension of the algorithm Rewrite for positive omqs, and show the following: under the Skolem semantics, a well-established approach for defining the answer to a rule-based omq when the user query can use negation, the proposed algorithm is a first-order rewriter for (OL,nCQ), where OL is the language of linear or acyclic tuple-generating dependencies, two central rule-based ontology languages that ensure first-order rewritability for positive omqs. We strongly believe that the new algorithm can serve as a good starting point towards the full settlement of our main question.

Cite as

Georg Gottlob, Marco Manna, Andreas Pieris, and Aldo Ricioppo. First-Order Rewritability of Rule-Based Ontology Mediated Queries with Negation. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 21:1-21:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gottlob_et_al:LIPIcs.ICDT.2026.21,
  author =	{Gottlob, Georg and Manna, Marco and Pieris, Andreas and Ricioppo, Aldo},
  title =	{{First-Order Rewritability of Rule-Based Ontology Mediated Queries with Negation}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{21:1--21:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-413-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{365},
  editor =	{ten Cate, Balder and Funk, Maurice},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2026.21},
  URN =		{urn:nbn:de:0030-drops-256353},
  doi =		{10.4230/LIPIcs.ICDT.2026.21},
  annote =	{Keywords: ontology-mediated queries, tuple-generating dependencies, conjunctive queries with negation, first-order rewritability}
}

Document

DOI: 10.4230/OASIcs.ICLP.2017.1

Entity set expansion from the Web via ASP

Authors: Weronika T. Adrian, Marco Manna, Nicola Leone, Giovanni Amendola, and Marek Adrian

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

Abstract

Knowledge on the Web in a large part is stored in various semantic resources that formalize, represent and organize it differently. Combining information from several sources can improve results of tasks such as recognizing similarities among objects. In this paper, we propose a logic-based method for the problem of entity set expansion (ESE), i.e. extending a list of named entities given a set of seeds. This problem has relevant applications in the Information Extraction domain, specifically in automatic lexicon generation for dictionary-based annotating tools. Contrary to typical approaches in natural languages processing, based on co-occurrence statistics of words, we determine the common category of the seeds by analyzing the semantic relations of the objects the words represent. To do it, we integrate information from selected Web resources. We introduce a notion of an entity network that uniformly represents the combined knowledge and allow to reason over it. We show how to use the network to disambiguate word senses by relying on a concept of optimal common ancestor and how to discover similarities between two entities. Finally, we show how to expand a set of entities, by using answer set programming with external predicates.

Cite as

Weronika T. Adrian, Marco Manna, Nicola Leone, Giovanni Amendola, and Marek Adrian. Entity set expansion from the Web via ASP. In Technical Communications of the 33rd International Conference on Logic Programming (ICLP 2017). Open Access Series in Informatics (OASIcs), Volume 58, pp. 1:1-1:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{adrian_et_al:OASIcs.ICLP.2017.1,
  author =	{Adrian, Weronika T. and Manna, Marco and Leone, Nicola and Amendola, Giovanni and Adrian, Marek},
  title =	{{Entity set expansion from the Web via ASP}},
  booktitle =	{Technical Communications of the 33rd International Conference on Logic Programming (ICLP 2017)},
  pages =	{1:1--1: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.1},
  URN =		{urn:nbn:de:0030-drops-84629},
  doi =		{10.4230/OASIcs.ICLP.2017.1},
  annote =	{Keywords: answer set programming, entity set expansion, information extraction, natural language processing, word sense disambiguation}
}

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 Manna, Marco

First-Order Rewritability of Rule-Based Ontology Mediated Queries with Negation

Abstract

Cite as

Entity set expansion from the Web via ASP

Abstract

Cite as

Reasoning on anonymity in Datalog+/-

Abstract

Cite as

Thanks for your feedback!

Could not send message