5 de junio de 2022 · 1 Min. de lectura

Query Games in Databases

RL2, Publisher: ACM SIGMOD Record, Link>


Benny Kimelfeld, Ester Livshits, Leopoldo Bertossi, Moshe Sebag


Database tuples can be seen as players in the game of jointly realizing the answer to a query. Some tuples may contribute more than others to the outcome, which can be a binary value in the case of a Boolean query, a number for a numerical aggregate query, and so on. To quantify the contributions of tuples, we use the Shapley value that was introduced in cooperative game theory and has found applications in a plethora of domains. Specifically, the Shapley value of an individual tuple quantifies its contribution to the query. We investigate the applicability of the Shapley value in this setting, as well as the computational aspects of its calculation in terms of complexity, algorithms, and approximation.

64 visualizaciones