1,915 research outputs found
When Can We Answer Queries Using Result-Bounded Data Interfaces?
No full textWe consider answering queries on data available through access methods, that
provide lookup access to the tuples matching a given binding. Such interfaces
are common on the Web; further, they often have bounds on how many results they
can return, e.g., because of pagination or rate limits. We thus study
result-bounded methods, which may return only a limited number of tuples. We
study how to decide if a query is answerable using result-bounded methods,
i.e., how to compute a plan that returns all answers to the query using the
methods, assuming that the underlying data satisfies some integrity
constraints. We first show how to reduce answerability to a query containment
problem with constraints. Second, we show "schema simplification" theorems
describing when and how result-bounded services can be used. Finally, we use
these theorems to give decidability and complexity results about answerability
for common constraint classes.Comment: journal version of the PODS'18 paper arXiv:1706.0793
Front Matter, Table of Contents, Preface, Conference Organization
No full textFront Matter, Table of Contents, Preface, Conference Organizatio
OASIcs, Volume 119, Tannen's Festschrift, Complete Volume
No full textOASIcs, Volume 119, Tannen's Festschrift, Complete Volum
Weighted Counting of Matchings in Unbounded-Treewidth Graph Families
No full textWe consider a weighted counting problem on matchings, denoted
, on an arbitrary fixed graph family
. The input consists of a graph and of rational
probabilities of existence on every edge of , assuming independence. The
output is the probability of obtaining a matching of in the resulting
distribution, i.e., a set of edges that are pairwise disjoint. It is known
that, if has bounded treewidth, then
can be solved in polynomial time. In this
paper we show that, under some assumptions, bounded treewidth in fact
characterizes the tractable graph families for this problem. More precisely, we
show intractability for all graph families satisfying the
following treewidth-constructibility requirement: given an integer in
unary, we can construct in polynomial time a graph with
treewidth at least . Our hardness result is then the following: for any
treewidth-constructible graph family , the problem
is intractable. This generalizes known
hardness results for weighted matching counting under some restrictions that do
not bound treewidth, e.g., being planar, 3-regular, or bipartite; it also
answers a question left open in Amarilli, Bourhis and Senellart (PODS'16). We
also obtain a similar lower bound for the weighted counting of edge covers.Comment: This is the full version with proofs of the MFCS'22 articl
Inférence automatique de la classe de document à partir de la littérature scientifique
No full textInternational audienceThe purpose of this report is to summarize what I have achieved in the framework of Télécom Paris’ AIoption research project. My project, entitled “Automatically inferring the document class used in a scientific article”, is carried out within the École Normale Supérieure, and more particularly within the Valda team at Inria Paris. It is co-supervised by Pierre Senellart, university professor at École Normale Supérieure and head of the Valda team, and Antoine Amarilli, associate professor at Télécom Paris
Recommended from our members
Letter to Philippe-Antoine Merlin, 1802 November 12.
No full textLetter to Philippe-Antoine Merlin, concerning a conflict involving charges of plagarism between the author and C. Laucuouque, dated "21 brumaire, an 11." The author's signature is not entirely legible. Accompanying enveloped shows traces of red wax seal
Uniform Reliability for Unbounded Homomorphism-Closed Graph Queries
No full textWe study the uniform query reliability problem, which asks, for a fixed
Boolean query Q, given an instance I, how many subinstances of I satisfy Q.
Equivalently, this is a restricted case of Boolean query evaluation on
tuple-independent probabilistic databases where all facts must have probability
1/2. We focus on graph signatures, and on queries closed under homomorphisms.
We show that for any such query that is unbounded, i.e., not equivalent to a
union of conjunctive queries, the uniform reliability problem is #P-hard. This
recaptures the hardness, e.g., of s-t connectedness, which counts how many
subgraphs of an input graph have a path between a source and a sink.
This new hardness result on uniform reliability strengthens our earlier
hardness result on probabilistic query evaluation for unbounded
homomorphism-closed queries (ICDT'20). Indeed, our earlier proof crucially used
facts with probability 1, so it did not apply to the unweighted case. The new
proof presented in this paper avoids this; it uses our recent hardness result
on uniform reliability for non-hierarchical conjunctive queries without
self-joins (ICDT'21), along with new techniques.Comment: Full version with proofs of the ICDT'23 articl
Uniform Reliability of Self-Join-Free Conjunctive Queries
No full textThe reliability of a Boolean Conjunctive Query (CQ) over a tuple-independent
probabilistic database is the probability that the CQ is satisfied when the
tuples of the database are sampled one by one, independently, with their
associated probability. For queries without self-joins (repeated relation
symbols), the data complexity of this problem is fully characterized by a known
dichotomy: reliability can be computed in polynomial time for hierarchical
queries, and is #P-hard for non-hierarchical queries.
Inspired by this dichotomy, we investigate a fundamental counting problem for
CQs without self-joins: how many sets of facts from the input database satisfy
the query? This is equivalent to the uniform case of the query reliability
problem, where the probability of every tuple is required to be 1/2. Of course,
for hierarchical queries, uniform reliability is solvable in polynomial time,
like the reliability problem. We show that being hierarchical is also necessary
for this tractability (under conventional complexity assumptions). In fact, we
establish a generalization of the dichotomy that covers every restricted case
of reliability in which the probabilities of tuples are determined by their
relation.Comment: Extended version of the ICDT'21 pape
Dynamic Membership for Regular Tree Languages
No full textInternational audienceWe study the dynamic membership problem for regular tree languages under relabeling updates: we fix an alphabet Σ and a regular tree language L over Σ (expressed, e.g., as a tree automaton), we are given a tree T with labels in Σ, and we must maintain the information of whether the tree T belongs to L while handling relabeling updates that change the labels of individual nodes in T. Our first contribution is to show that this problem admits an O(log n / log log n) algorithm for any fixed regular tree language, improving over known O(log n) algorithms. This generalizes the known O(log n / log log n) upper bound over words, and it matches the lower bound of Ω(log n / log log n) from dynamic membership to some word languages and from the existential marked ancestor problem. Our second contribution is to introduce a class of regular languages, dubbed almost-commutative tree languages, and show that dynamic membership to such languages under relabeling updates can be decided in constant time per update. Almost-commutative languages generalize both commutative languages and finite languages: they are the analogue for trees of the ZG languages enjoying constant-time dynamic membership over words. Our main technical contribution is to show that this class is conditionally optimal when we assume that the alphabet features a neutral letter, i.e., a letter that has no effect on membership to the language. More precisely, we show that any regular tree language with a neutral letter which is not almost-commutative cannot be maintained in constant time under the assumption that the prefix-U1 problem from [Antoine Amarilli et al., 2021] also does not admit a constant-time algorithm
The Dichotomy of Evaluating Homomorphism-Closed Queries on Probabilistic Graphs
No full textWe study the problem of query evaluation on probabilistic graphs, namely,
tuple-independent probabilistic databases over signatures of arity two. We
focus on the class of queries closed under homomorphisms, or, equivalently, the
infinite unions of conjunctive queries. Our main result states that the
probabilistic query evaluation problem is #P-hard for all unbounded queries
from this class. As bounded queries from this class are equivalent to a union
of conjunctive queries, they are already classified by the dichotomy of Dalvi
and Suciu (2012). Hence, our result and theirs imply a complete data complexity
dichotomy, between polynomial time and #P-hardness, on evaluating
homomorphism-closed queries over probabilistic graphs. This dichotomy covers in
particular all fragments of infinite unions of conjunctive queries over
arity-two signatures, such as negation-free (disjunctive) Datalog, regular path
queries, and a large class of ontology-mediated queries. The dichotomy also
applies to a restricted case of probabilistic query evaluation called
generalized model counting, where fact probabilities must be 0, 0.5, or 1. We
show the main result by reducing from the problem of counting the valuations of
positive partitioned 2-DNF formulae, or from the source-to-target reliability
problem in an undirected graph, depending on properties of minimal models for
the query
- …
