Search

• < Previous
• 1
• Next >

---

The Dichotomy of Evaluating Homomorphism-Closed Queries on Probabilistic Graphs

Antoine Amarilli ; İsmail İlkan Ceylan.

We 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&nbsp;[&hellip;]

---

Uniform Reliability of Self-Join-Free Conjunctive Queries

Antoine Amarilli ; Benny Kimelfeld.

The 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&nbsp;[&hellip;]

---

When Can We Answer Queries Using Result-Bounded Data Interfaces?

Antoine Amarilli ; Michael Benedikt.

We 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&nbsp;[&hellip;]

---

Locality and Centrality: The Variety ZG

Antoine Amarilli ; Charles Paperman.

We study the variety ZG of monoids where the elements that belong to a group are central, i.e., commute with all other elements. We show that ZG is local, that is, the semidirect product ZG * D of ZG by definite semigroups is equal to LZG, the variety of semigroups where all local monoids are in ZG.&nbsp;[&hellip;]

---