Search

Your search keyword '"Benny Kimelfeld"' showing total 331 results
Start Over Author "Benny Kimelfeld"
331 results on '"Benny Kimelfeld"'

191. Query Games in Databases

Author

Benny Kimelfeld, Moshe Sebag, Leopoldo Bertossi, and Ester Livshits

Subjects
Database, Computer science, Aggregate (data warehouse), InformationSystems_DATABASEMANAGEMENT, Cooperative game theory, computer.software_genre, Shapley value, Outcome (game theory), Tuple, Binary Value, computer, Software, Boolean conjunctive query, Information Systems
Abstract

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.

Published
2021
Full Text
View/download PDF

192. Counting subset repairs with functional dependencies

Author

Jef Wijsen, Ester Livshits, and Benny Kimelfeld

Subjects
Discrete mathematics, Computer Networks and Communications, Computer science, Applied Mathematics, 0102 computer and information sciences, 02 engineering and technology, Data complexity, 01 natural sciences, Graph, Complete metric space, Theoretical Computer Science, Decidability, Computational Theory and Mathematics, 010201 computation theory & mathematics, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, Maximal independent set, Functional dependency, Time complexity
Abstract

We study the problem of counting the repairs of an inconsistent database in the case where constraints are Functional Dependencies (FDs). A repair is then a maximal independent set of the conflict graph, wherein nodes represent facts and edges represent violations. We establish a dichotomy in data complexity for the complete space of FDs: when the FD set has, up to equivalence, what we call a “left-hand-side chain,” the repairs can be counted in polynomial time; otherwise, the problem is ♯ P -complete. Moreover, the property of having a left-hand-side chain up to equivalence coincides with the condition that the conflict graph of every inconsistent database for the schema is P 4 -free, and it is polynomial-time decidable.

Published
2021
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results