This repository is the official implementation of "Computing the Shapley Value of Tuples in Query Answering".

1. Installation of PostgreSQL >= 9.5
2. Installation of ProvSQL
3. Installation of c2d

Download and import the following databases to PostgreSQL.

1. IMDB
2. TPC-H

Each table should be tracked by ProvSQL.

SET search_path TO public, provsql;

SELECT add_provenance('[Table name]');
SELECT create_provenance_mapping('[Table name]_id', '[Table name]', '[Table primary index]');

Example.ipynb depict how to compute the exact Shapley value of tuples given a provenance as a d-DNNF.

notebooks directory depicts subset of the results presented in the paper.

Results include:

• Exact computation present the computation of exact Shapley values. We investigate the running time as a function of the provenance complexity.
• Inexact computation compare several approximation and heuristics over a wide range of metics.