Andreas Pieris

KR Conference 2025 Conference Paper

Finite Axiomatizability by Disjunctive Existential Rules

• Marco Calautti
• Marco Console
• Andreas Pieris

Rule-based languages lie at the core of several areas of central importance to databases and artificial intelligence such as deductive databases and knowledge representation and reasoning. Disjunctive existential rules (a. k. a. disjunctive tuple-generating dependencies in the database literature) form such a prominent rule-based language. The goal of this work is to pinpoint the expressive power of disjunctive existential rules in terms of insightful model-theoretic properties. More precisely, given a collection C of relational structures, we show that C is axiomatizable via a finite set R of disjunctive existential rules (i. e. , C is precisely the set of models of R) iff C enjoys certain model-theoretic properties. This is achieved by using the well-known property of criticality, a refined version of closure under direct products, and a novel property called diagrammatic compatibility that relies on the method of diagrams. We further establish analogous characterizations for the well-behaved classes of linear and guarded disjunctive existential rules by adopting refined versions of diagrammatic compatibility that consider the syntactic restrictions imposed by linearity and guardedness; this illustrates the robustness of diagrammatic compatibility. We finally exploit diagrammatic compatibility to rewrite a set of guarded disjunctive existential rules into an equivalent set that falls in the weaker class of linear disjunctive existential rules, if one exists.

AAAI Conference 2024 Conference Paper

Computing the Why-Provenance for Datalog Queries via SAT Solvers

• Marco Calautti
• Ester Livshits
• Andreas Pieris
• Markus Schneider

Explaining an answer to a Datalog query is an essential task towards Explainable AI, especially nowadays where Datalog plays a critical role in the development of ontology-based applications. A well-established approach for explaining a query answer is the so-called why-provenance, which essentially collects all the subsets of the input database that can be used to obtain that answer via some derivation process, typically represented as a proof tree. It is well known, however, that computing the why-provenance for Datalog queries is computationally expensive, and thus, very few attempts can be found in the literature. The goal of this work is to demonstrate how off-the-shelf SAT solvers can be exploited towards an efficient computation of the why-provenance for Datalog queries. Interestingly, our SAT-based approach allows us to build the why-provenance in an incremental fashion, that is, one explanation at a time, which is much more useful in a practical context than the one-shot computation of the whole set of explanations as done by existing approaches.

AIJ Journal 2023 Journal Article

Polynomial combined first-order rewritings for linear and guarded existential rules

• Georg Gottlob
• Marco Manna
• Andreas Pieris

AIJ Journal 2022 Journal Article

Inconsistency-tolerant query answering for existential rules

• Thomas Lukasiewicz
• Enrico Malizia
• Maria Vanina Martinez
• Cristian Molinaro
• Andreas Pieris
• Gerardo I. Simari

KR Conference 2020 Conference Paper

Multi-head Guarded Existential Rules Over Fixed Signatures

• Georg Gottlob
• Marco Manna
• Andreas Pieris

Guarded existential rules form a robust rule-based language for modelling ontologies. The central problem of ontology-based query answering, as well as the notion of polynomial combined rewritability, have been extensively studied during the last years for this formalism. However, the relevant setting where the underlying signature is considered to be fixed is far from being well understood. All the existing results on ontology-based query answering and polynomial combined rewritability assume rule heads with one atom, while existential rules in real ontologies are typically coming with multi-heads consisting of several atoms. We aim to fill this gap.

Highlights Conference 2020 Conference Abstract

The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs

• Andreas Pieris

Ontology-mediated querying and querying in the presence of constraints are two key database problems where tuple-generating dependencies (TGDs) play a central role. In ontology-mediated querying, TGDs can formalize the ontology and thus derive additional facts from the given data, while in querying in the presence of constraints, they restrict the set of admissible databases. In this work, we study the limits of efficient query evaluation in the context of the above two problems, focusing on guarded and frontier-guarded TGDs and on UCQs as the actual queries.

JELIA Conference 2019 Invited Paper

Vadalog: Recent Advances and Applications

• Georg Gottlob
• Andreas Pieris
• Emanuel Sallinger

Abstract Vadalog is a logic-based reasoning language for modern AI applications, in particular for knowledge graph systems. In this paper, we present recent advances and applications, with a focus on the Vadalog language itself. We first give an easy-to-access self-contained introduction to Warded Datalog+/−, the logical core of Vadalog. We then discuss some recent advances: Datalog rewritability of Warded Datalog+/−, and the piece-wise linear fragment of Warded Datalog+/− that achieves space efficiency. We then proceed with some recent practical applications of the Vadalog language: detection of close links in financial knowledge graphs, as well as the detection of family-owned businesses.

IJCAI Conference 2018 Conference Paper

Finite Model Reasoning in Hybrid Classes of Existential Rules

• Georg Gottlob
• Marco Manna
• Andreas Pieris

Two paradigmatic restrictions that have been studied for ensuring the decidability of query answering under existential rules are guardedness and stickiness. With the aim of consolidating these restrictions, a flexible condition, called tameness, has been proposed a few years ago, which relies on hybrid reasoning, i. e. , a combination of forward and backward procedures. The complexity of query answering under this hybrid class of existential rules is by now well-understood. However, the complexity of finite query answering, i. e. , query answering under finite models, has remained an open problem. Closing this problem is the main goal of this work.

IJCAI Conference 2018 Conference Paper

First-Order Rewritability of Frontier-Guarded Ontology-Mediated Queries

• Pablo Barceló
• Gerald Berger
• Carsten Lutz
• Andreas Pieris

We focus on ontology-mediated queries (OMQs) based on (frontier-)guarded existential rules and (unions of) conjunctive queries, and we investigate the problem of FO-rewritability, i. e. , whether an OMQ can be rewritten as a first-order query. We adopt two different approaches. The first approach employs standard two-way alternating parity tree automata. Although it does not lead to a tight complexity bound, it provides a transparent solution based on widely known tools. The second approach relies on a sophisticated automata model, known as cost automata. This allows us to show that our problem is 2EXPTIME-complete. In both approaches, we provide semantic characterizations of FO-rewritability that are of independent interest.

IJCAI Conference 2017 Conference Paper

Making Cross Products and Guarded Ontology Languages Compatible

• Pierre Bourhis
• Michael Morak
• Andreas Pieris

Cross products form a useful modelling tool that allows us to express natural statements such as "elephants are bigger than mice", or, more generally, to define relations that connect every instance in a relation with every instance in another relation. Despite their usefulness, cross products cannot be expressed using existing guarded ontology languages, such as description logics (DLs) and guarded existential rules. The question that comes up is whether cross products are compatible with guarded ontology languages, and, if not, whether there is a way of making them compatible. This has been already studied for DLs, while for guarded existential rules remains unanswered. Our goal is to give an answer to the above question. To this end, we focus on the guarded fragment of first-order logic (which serves as a unifying framework that subsumes many of the aforementioned ontology languages) extended with cross products, and we investigate the standard tasks of satisfiability and query answering. Interestingly, we isolate relevant fragments that are compatible with cross products.

IJCAI Conference 2017 Conference Paper

Swift Logic for Big Data and Knowledge Graphs

• Luigi Bellomarini
• Georg Gottlob
• Andreas Pieris
• Emanuel Sallinger

Many modern companies wish to maintain knowledge in the form of a corporate knowledge graph and to use and manage this knowledge via a knowledge graph management system (KGMS). We formulate various requirements for a fully fledged KGMS. In particular, such a system must be capable of performing complex reasoning tasks but, at the same time, achieve efficient and scalable reasoning over Big Data with an acceptable computational complexity. Moreover, a KGMS needs interfaces to corporate databases, the web, and machine-learning and analytics packages. We present KRR formalisms and a system achieving these goals.

IJCAI Conference 2016 Conference Paper

Ontology-Mediated Queries Distributing over Components

• Gerald Berger
• Andreas Pieris

Ontology-based data access is concerned with the problem of querying incomplete data sources in the presence of an ontology. A key notion in this setting is that of ontology-mediated query, which is a database query coupled with an ontology. An interesting issue is whether the answer to an ontology-mediated query can be computed by parallelizing it over the connected components of the database, i. e. , whether the query distributes over components. This allows us to evaluate the query in a distributed and coordination-free manner. We investigate distribution over components for classes of ontology-mediated queries where the database query is a conjunctive query and the ontology is formulated using existential rules. For each such class, we syntactically characterize its fragment that distributes over components, and we study the problem of deciding whether a query distributes over components.

IJCAI Conference 2015 Conference Paper

Beyond SPARQL under OWL 2 QL Entailment Regime: Rules to the Rescue

• Georg Gottlob
• Andreas Pieris

SPARQL is the de facto language for querying RDF data, since its standardization in 2008. A new version, called SPARQL 1. 1, was released in 2013, with the aim of enriching the 2008 language with reasoning capabilities to deal with RDFS and OWL vocabularies, and a mechanism to express navigation patterns through regular expressions. However, SPARQL 1. 1 is not powerful enough for expressing some relevant navigation patterns, and it misses a general form of recursion. In this work, we focus on OWL 2 QL and we propose TriQ-Lite 1. 0, a tractable rule-based formalism that supports the above functionalities, and thus it can be used for querying RDF data. Unlike existing composite approaches, our formalism has simple syntax and semantics in the same spirit as good old Datalog.

AAAI Conference 2015 Conference Paper

From Classical to Consistent Query Answering under Existential Rules

• Thomas Lukasiewicz
• Maria Vanina Martinez
• Andreas Pieris
• Gerardo Simari

Querying inconsistent ontologies is an intriguing new problem that gave rise to a flourishing research activity in the description logic (DL) community. The computational complexity of consistent query answering under the main DLs is rather well understood; however, little is known about existential rules. The goal of the current work is to perform an in-depth analysis of the complexity of consistent query answering under the main decidable classes of existential rules enriched with negative constraints. Our investigation focuses on one of the most prominent inconsistency-tolerant semantics, namely, the AR semantics. We establish a generic complexity result, which demonstrates the tight connection between classical and consistent query answering. This result allows us to obtain in a uniform way a relatively complete picture of the complexity of our problem.

IJCAI Conference 2015 Conference Paper

Polynomial Rewritings for Linear Existential Rules

• Georg Gottlob
• Marco Manna
• Andreas Pieris

We consider the scenario of ontology-based query answering. It is generally accepted that true scalability in this setting can only be achieved via query rewriting, which in turn allows for the exploitation of standard RDBMSs. In this work, we close two open fundamental questions related to query rewriting. We establish that linear existential rules are polynomially combined rewritable, while full linear rules are polynomially (purely) rewritable; in both cases, the target query language consists of first-order or non-recursive Datalog queries. An immediate consequence of our results is that DLR- LiteR, the extension of DL-LiteR with n-ary roles, is polynomially combined rewritable.

KR Conference 2014 Conference Paper

Polynomial Combined Rewritings for Existential Rules

• Georg Gottlob
• Marco Manna
• Andreas Pieris

We consider the scenario of ontology-based data access where a conjunctive query is evaluated against a database enriched with intensional knowledge via an ontology. It is generally accepted that true scalability of query answering in this setting can only be achieved by using standard relational database management systems (RDBMSs). An approach to query answering that enables the use of RDBMSs is the so-called polynomial combined approach. We investigate this approach for the main guarded- and sticky-based classes of existential rules, and we highlight the assumptions on the underlying schema which are sufficient for the polynomial combined first-order rewritability of those classes. To the best of our knowledge, this is the first work which explicitly studies the polynomial combined approach for existential rules.

IJCAI Conference 2013 Conference Paper

The Impact of Disjunction on Query Answering under Guarded-Based Existential Rules

• Pierre Bourhis
• Michael Morak
• Andreas Pieris

We study the complexity of conjunctive query answering under (weakly-)(frontier-)guarded disjunctive existential rules, i. e. , existential rules extended with disjunction, and their main subclasses, linear rules and inclusion dependencies (IDs). Our main result states that conjunctive query answering under a fixed set of disjunctive IDs is 2EXPTIME-hard. This quite surprising result together with a 2EX- PTIME upper bound for weakly-frontier-guarded disjunctive rules, obtained by exploiting recent results on guarded negation first-order logic, gives us a complete picture of the computational complexity of our problem. We also consider a natural subclass of disjunctive IDs, namely frontier-one (only one variable is propagated), for which the combined complexity decreases to EXPTIME. Finally, we show that frontier-guarded rules, combined with negative constraints, are strictly more expressive than DL-LiteH bool, one of the most expressive languages of the DL-Lite family. We also show that query answering under DL-LiteH bool is 2EXPTIMEcomplete in combined complexity.

MFCS Conference 2012 Conference Paper

On the Complexity of Ontological Reasoning under Disjunctive Existential Rules

• Georg Gottlob
• Marco Manna
• Michael Morak
• Andreas Pieris

Abstract Ontology-based data access is an emerging yet powerful technology that allows to enhance a classical relational database with an ontology in order to infer new intensional knowledge. Recently, Datalog+/- was introduced with the purpose of providing tractable reasoning algorithms for expressive ontology languages. In this framework, Datalog is extended by features such as existential quantification in rule heads, and at the same time the rule syntax is restricted to guarantee decidability, and also tractability, of relevant reasoning tasks. In this paper, we enrich Datalog even more by allowing not only existential quantification but also disjunction in rule heads, and we investigate the complexity of reasoning under the obtained formalism.

AIJ Journal 2012 Journal Article

Towards more expressive ontology languages: The query answering problem

• Andrea Cali`
• Georg Gottlob
• Andreas Pieris

AAAI Conference 2011 Conference Paper

New Expressive Languages for Ontological Query Answering

• Andrea Calì
• Georg Gottlob
• Andreas Pieris

Ontology-based data access is a powerful form of extending database technology, where a classical extensional database (EDB) is enhanced by an ontology that generates new intensional knowledge which may contribute to answer a query. Recently, the Datalog± family of ontology languages was introduced; in Datalog±, rules are tuple-generating dependencies (TGDs), i. e. , Datalog rules with the possibility of having existentially-quantified variables in the head. In this paper we introduce a novel Datalog± language, namely sticky sets of TGDs, which allows for a wide class of joins in the body, while enjoying at the same time a low query-answering complexity. We establish complexity results for answering conjunctive queries under sticky sets of TGDs, showing, in particular, that ontological conjunctive queries can be compiled into first-order and thus SQL queries over the given EDB instance. We also show some extensions of sticky sets of TGDs, and how functional dependencies and so-called negative constraints can be added to a sticky set of TGDs without increasing the complexity of query answering. Our language thus properly generalizes both classical database constraints and most widespread tractable description logics.

AAAI Conference 2010 Conference Paper

Ontological Reasoning with F-logic Lite and its Extensions

• Andrea Cali
• Georg Gottlob
• Michael Kifer
• Thomas Lukasiewicz
• Andreas Pieris