Author name cluster

Pierre Bourhis

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

14 papers

2 author rows

KR Conference 2022 Conference Paper

Revisiting Semiring Provenance for Datalog

Camille Bourgaux
Pierre Bourhis
Liat Peterfreund
Michaël Thomazo

Data provenance consists in bookkeeping meta information during query evaluation, in order to enrich query results with their trust level, likelihood, evaluation cost, and more. The framework of semiring provenance abstracts from the specific kind of meta information that annotates the data. While the definition of semiring provenance is uncontroversial for unions of conjunctive queries, the picture is less clear for Datalog. Indeed, the original definition might include infinite computations, and is not consistent with other proposals for Datalog semantics over annotated data. In this work, we propose and investigate several provenance semantics, based on different approaches for defining classical Datalog semantics. We study the relationship between these semantics, and introduce properties that allow us to analyze and compare them.

PDF Details DOI

KR Conference 2020 Conference Paper

Balancing Expressiveness and Inexpressiveness in View Design

Michael Benedikt
Pierre Bourhis
Louis Jachiet
Efthymia Tsamoura

We study the design of data publishing mechanisms that allow a collection of autonomous distributed datasources to collaborate to support queries. A common mechanism for data publishing is via views: functions that expose derived data to users, usually specified as declarative queries. Our autonomy assumption is that the views must be on individual sources, but with the intention of supporting integrated queries. In deciding what data to expose to users, two considerations must be balanced. The views must be sufficiently expressive to support queries that users want to ask -- the utility of the publishing mechanism. But there may also be some expressiveness restriction. Here we consider two restrictions, a minimal information requirement, saying that the views should reveal as little as possible while supporting the utility query, and a non-disclosure requirement, formalizing the need to prevent external users from computing information that data owners do not want revealed. We investigate the problem of designing views that satisfy both an expressiveness and an inexpressiveness requirement, for views in a restricted declarative language (conjunctive queries), and for arbitrary views.

PDF Details DOI

IJCAI Conference 2019 Conference Paper

Mixed-World Reasoning with Existential Rules under Active-Domain Semantics

Meghyn Bienvenu
Pierre Bourhis

In this paper, we study reasoning with existential rules in a setting where some of the predicates may be closed (i. e. , their content is fully specified by the data instance) and the remaining open predicates are interpreted under active-domain semantics. We show, unsurprisingly, that the main reasoning tasks (satisfiability and certainty / possibility of Boolean queries) are all intractable in data complexity in the general case. However, several positive (PTIME data) results are obtained for the linear fragment, and interestingly, these tractability results hold also for various extensions, e. g. , with negated closed atoms and disjunctive rule heads. This motivates us to take a closer look at the linear fragment, exploring its expressivity and defining a fixpoint extension to approximate non-linear rules.

PDF Details

IJCAI Conference 2019 Conference Paper

Oblivious and Semi-Oblivious Boundedness for Existential Rules

Pierre Bourhis
Michel Leclère
Marie-Laure Mugnier
Sophie Tison
Federico Ulliana
Lily Gallois

We study the notion of boundedness in the context positive existential rules, that is, wether there exists an upper bound to the depth of the chase procedure, that is independent from the initial instance. By focussing our attention on the oblivious and the semi-oblivious chase variants, we give a characterization of boundedness in terms of FO-rewritability and chase termination. We show that it is decidable to recognize if a set of rules is bounded for several classes of rules and outline the complexity of the problem.

PDF Details

IJCAI Conference 2019 Conference Paper

Reasoning about Disclosure in Data Integration in the Presence of Source Constraints

Michael Benedikt
Pierre Bourhis
Louis Jachiet
Michaël Thomazo

Data integration systems allow users to access data sitting in multiple sources by means of queries over a global schema, related to the sources via mappings. Datasources often contain sensitive information, and thus an analysis is needed to verify that a schema satisfies a privacy policy, given as a set of queries whose answers should not be accessible to users. Such an analysis should take into account not only knowledge that an attacker may have about the mappings, but also what they may know about the semantics of the sources. In this paper, we show that source constraints can have a dramatic impact on disclosure analysis. We study the problem of determining whether a given data integration system discloses a source query to an attacker in the presence of constraints, providing both lower and upper bounds on source-aware disclosure analysis.

PDF Details

JAIR Journal 2018 Journal Article

Query Answering with Transitive and Linear-Ordered Data

Antoine Amarilli
Michael Benedikt
Pierre Bourhis
Michael Vanden Boom

We consider entailment problems involving powerful constraint languages such as frontier-guarded existential rules in which we impose additional semantic restrictions on a set of distinguished relations. We consider restricting a relation to be transitive, restricting a relation to be the transitive closure of another relation, and restricting a relation to be a linear order. We give some natural variants of guardedness that allow inference to be decidable in each case, and isolate the complexity of the corresponding decision problems. Finally we show that slight changes in these conditions lead to undecidability.

PDF Details DOI

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.

PDF Details

IJCAI Conference 2017 Conference Paper

Ontology-Mediated Query Answering for Key-Value Stores

Meghyn Bienvenu
Pierre Bourhis
Marie-Laure Mugnier
Sophie Tison
Federico Ulliana

We propose a novel rule-based ontology language for JSON records and investigate its computational properties. After providing a natural translation into first-order logic, we identify relationships to existing ontology languages, which yield decidability of query answering but only rough complexity bounds. By establishing an interesting and non-trivial connection to word rewriting, we are able to pinpoint the exact combined complexity of query answering in our framework and obtain tractability results for data complexity. The upper bounds are proven using a query reformulation technique, which can be implemented on top of key-value stores, thereby exploiting their querying facilities.

PDF Details

KR Conference 2016 Conference Paper

Containment in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics

Pierre Bourhis
Carsten Lutz

We study query containment in three closely related formalisms: monadic disjunctive Datalog (MDDLog), MMSNP (a logical generalization of constraint satisfaction problems), and ontology-mediated queries (OMQs) based on expressive description logics and unions of conjunctive queries. Containment in MMSNP was known to be decidable due to a result by Feder and Vardi, but its exact complexity has remained open. We prove 2NExpTime-completeness and extend this result to monadic disjunctive Datalog and to OMQs.

Highlights Conference 2016 Conference Abstract

Probabilities and Provenance on Trees and Treelike Instances

Antoine Amarilli
Pierre Bourhis
Pierre Senellart

We present our recent results at PODS 2016 and ICALP 2015 about the evaluation of queries on probabilistic databases and graphs. Our upper bound result shows that this task can be efficiently performed (in data complexity, i. e. , for a fixed query) for Boolean Monadic Second-Order (MSO) queries, on databases of treewidth bounded by a constant. We do so using Courcelle’s method of compiling MSO to tree automata, and extend it to compute probabilities, via a provenance representation that describes which possible worlds satisfy the query. Our lower bound shows that, on graphs, there is a first-order query which is always intractable to evaluate on database families of unbounded treewidth (under a constructibility assumption), no matter which other restrictions we impose on the databases.

Details

IJCAI Conference 2016 Conference Paper

Query Answering with Transitive and Linear-Ordered Data

Antoine Amarilli
Michael Benedikt
Pierre Bourhis
Michael Vanden Boom

We consider entailment problems involving powerful constraint languages such as guarded existential rules, in which additional semantic restrictions are put on a set of distinguished relations. We consider restricting a relation to be transitive, restricting a relation to be the transitive closure of another relation, and restricting a relation to be a linear order. We give some natural generalizations of guardedness that allow inference to be decidable in each case, and isolate the complexity of the corresponding decision problems. Finally we show that slight changes in our conditions lead to undecidability.

PDF Details

IJCAI Conference 2015 Conference Paper

IJCAI-15 Distinguished Paper, Honorary Mention Reasonable Highly Expressive Query Languages

Pierre Bourhis
Markus Kr
ouml; tzsch
Sebastian Rudolph

Expressive query languages are gaining relevance in knowledge representation (KR), and new reasoning problems come to the fore. Especially query containment is interesting in this context. The problem is known to be decidable for many expressive query languages, but exact complexities are often missing. We introduce a new query language, guarded queries (GQ), which generalizes most known languages where query containment is decidable. GQs can be nested (more expressive), or restricted to linear recursion (less expressive). Our comprehensive analysis of the computational properties and expressiveness of (linear/nested) GQs also yields insights on many previous languages.

PDF Details

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.

PDF Details DOI

TIME Conference 2009 Invited Paper

The AXML Artifact Model

Serge Abiteboul
Pierre Bourhis
Alban Galland
Bogdan Marinoiu

Towards a data-centric workflow approach, we introduce an artifact model to capture data and workflow management activities in distributed settings. The model is built on Active XML, i. e. , XML trees including Web service calls. We argue that the model captures the essential features of business artifacts as described informally in [A. Nigam and N. Caswell (2003)] or discussed in [R. Hull (2008)]. To illustrate, we briefly consider the monitoring of distributed systems and the verification of temporal properties for them.

Details