4 papers · 1 filter
How Hard is it to Decide if a Fact is Relevant to a Query?
Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade
We consider the following fundamental problem: given a database D, Boolean conjunctive query (CQ) q, and fact f in D, decide whether f is relevant to q wrt. D, i.e., does f belong…
Responsibility Measures for Conjunctive Queries with Negation
Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade
We contribute to the recent line of work on responsibility measures that quantify the contributions of database facts to obtaining a query result. In contrast to existing work whic…
Shapley Revisited: Tractable Responsibility Measures for Query Answers
Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade
The Shapley value, originating from cooperative game theory, has been employed to define responsibility measures that quantify the contributions of database facts to obtaining a gi…
When is Shapley Value Computation a Matter of Counting?
Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade
The Shapley value provides a natural means of quantifying the contributions of facts to database query answers. In this work, we seek to broaden our understanding of Shapley value…