BKBenny Kimelfeld

Benny Kimelfeld

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Benny Kimelfeld has a total of 86 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Enumeration Theory through the Lens of Database Challenges

    by Florent Capelli, Nofar Carmeli, Alessio Conte, Benny Kimelfeld, Reinhard Pichler, Nikolaos Tziavelis

    Computational tasks that require producing many solutions arise throughout data management systems: database query engines return all qualifying tuples; search engines retrieve all relevant documents, albeit ranked; graph databases are tasked with producing all paths connecting two nodes; query optimizers routinely explore a vast space of candidate plans; and so on. Abstractly, these tasks are formalized as enumeration problems, solved by enumeration algorithms, and studied through the lens of enumeration complexity. This talk reflects on the evolution of enumeration in database research. It will begin with a brief survey of classic complexity-theoretic notions and algorithmic techniques that play a central role in enumeration across many domains. It will then review past results on enumeration problems arising in various areas of database systems. After that, it will delve deeper into the evolution of ideas and results on relational queries, with a special focus on join queries. It will conclude with challenges for future directions.

  • Open Access

    MonoTune: Analyzing Trend Deviations through Database Repair

    by Shunit Agmon, Itai Manor, Brit Youngmann, Benny Kimelfeld, Amir Gilad

    Datasets often violate expected monotonic trends. For instance, average income is typically expected to increase with education level, and housing prices to rise over time. Recent work studied how to quantify such deviations by introducing Aggregate Order Dependencies (AODs), an aggregation-centric extension of order dependencies, and by measuring the extent of violations via minimal repairs. Building on the AOD framework, this paper presents a demonstration of MonoTune, an interactive system for detecting, quantifying, and explaining violations of monotonic trends. MonoTune enables users to upload a dataset, specify an expected trend using an AOD, visualize violations directly in the results, compute repairs, and summarize the changes induced by these repairs. The system supports both optimal repair algorithms with high computational cost and fast heuristic alternatives that trade accuracy for efficiency. To enable interactive analysis, MonoTune further provides an incremental algorithm that produces a sequence of progressively improving repairs, starting from a heuristic solution and converging to an optimal one. We demonstrate MonoTune on several real-world datasets through a collection of scenarios illustrating how the system helps analysts explore expected trends, quantify deviations in both directions, compare the effectiveness and efficiency of different repair algorithms, and gain insights into the nature of the proposed repairs.

  • Open Access

    Analyzing Deviations from Monotonic Trends through Database Repair

    by Shunit Agmon, Jonathan Gal, Amir Gilad, Ester Livshits, Or Mutay, Brit Youngmann, Benny Kimelfeld

    Datasets often exhibit violations of expected monotonic trends—for example, higher education level correlating with higher average salary, newer homes being more expensive, or diabetes prevalence increasing with age. We address the problem of quantifying how far a dataset deviates from such trends. To this end, we introduce Aggregate Order Dependencies (AODs), an aggregation-centric extension of the previously studied order dependencies. An AOD specifies that the aggregated value of a target attribute (e.g., mean salary) should monotonically increase or decrease with the grouping attribute (e.g., education level). We formulate the AOD repair problem as finding the smallest set of tuples to delete from a table so that the given AOD is satisfied. We analyze the computational complexity of this problem and propose a general algorithmic template for solving it. We instantiate the template for common aggregation functions, introduce optimization techniques that substantially improve the runtime of the template instances, and develop efficient heuristic alternatives. Our experimental study, carried out on both real-world and synthetic datasets, demonstrates the practical efficiency of the algorithms and provides insight into the performance of the heuristics. We also present case studies that uncover and explain unexpected AOD violations using our framework.

  • Open Access

    Database Views as Explanations for Relational Deep Learning

    by Agapi Rissaki, Ilias Fountalis, Wolfgang Gatterbauer, Benny Kimelfeld

    In recent years, there has been significant progress in the development of deep learning models over relational databases, including architectures based on heterogeneous graph neural networks (hetero-GNNs) and heterogeneous graph transformers. In effect, such architectures state how the database records and links (e.g., foreign-key references) translate into a large, complex numerical expression, involving numerous learnable parameters. This complexity makes it hard to explain, in human-understandable terms, how a model uses the available data to arrive at a given prediction. We present a novel framework for explaining machine-learning models over relational databases, where explanations are view definitions that highlight focused parts of the database that mostly contribute to the model's prediction. We establish such global abductive explanations by adapting the classic notion of determinacy by Nash, Segoufin, and Vianu (2010). In addition to tuning the tradeoff between determinacy and conciseness, the framework allows controlling the level of granularity by adopting different fragments of view definitions, such as ones highlighting whole columns, foreign keys between tables, relevant groups of tuples, and so on. We investigate the realization of the framework in the case of hetero-GNNs, and develop a model-specific approach via the notion of learnable masks. For comparison, we propose model-agnostic heuristic baselines and show that our approach is both more efficient and achieves better explanation quality in most cases. Our extensive empirical evaluation on the RelBench collection across diverse domains and record-level tasks demonstrates both the usefulness of our explanations and the efficiency of their generation.

  • Open Access

    Analyzing Deviations from Monotonic Trends through Database Repair

    by Shunit Agmon, Jonathan Gal, Amir Gilad, Ester Livshits, Or Mutay, Brit Youngmann, Benny Kimelfeld

    Datasets often exhibit violations of expected monotonic trends - for example, higher education level correlating with higher average salary, newer homes being more expensive, or diabetes prevalence increasing with age. We address the problem of quantifying how far a dataset deviates from such trends. To this end, we introduce Aggregate Order Dependencies (AODs), an aggregation-centric extension of the previously studied order dependencies. An AOD specifies that the aggregated value of a target attribute (e.g., mean salary) should monotonically increase or decrease with the grouping attribute (e.g., education level). We formulate the AOD repair problem as finding the smallest set of tuples to delete from a table so that the given AOD is satisfied. We analyze the computational complexity of this problem and propose a general algorithmic template for solving it. We instantiate the template for common aggregation functions, introduce optimization techniques that substantially improve the runtime of the template instances, and develop efficient heuristic alternatives. Our experimental study, carried out on both real-world and synthetic datasets, demonstrates the practical efficiency of the algorithms and provides insight into the performance of the heuristics. We also present case studies that uncover and explain unexpected AOD violations using our framework.

  • Open Access

    Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries

    by Christoph Standke, Benny Kimelfeld

    In recent years, the Shapley value has emerged as a general game-theoretic measure for assessing the contribution of a tuple to the result of a database query. We study the complexity of calculating the Shapley value of a tuple for an aggregate conjunctive query, which applies an aggregation function to the result of a conjunctive query (CQ) based on a value function that assigns a number to each query answer. Prior work by Livshits, Bertossi, Kimelfeld, and Sebag (2020) established that this task is #P-hard for every nontrivial aggregation function when the query is non-hierarchical with respect to its existential variables, assuming the absence of self-joins. They further showed that this condition precisely characterizes the class of intractable CQs when the aggregate function is sum or count. In addition, they posed as open problems the complexity of other common aggregate functions such as min, max, count-distinct, average, and quantile (including median). Towards the resolution of these problems, we identify for each aggregate function a class of hierarchical CQs where the Shapley value is tractable with every value function, as long as it is local (i.e., determined by the tuples of one relation). We further show that each such class is maximal: for every CQ outside of this class, there is a local (easy-to-compute) value function that makes the Shapley value #P-hard. Interestingly, our results reveal that each aggregate function corresponds to a different generalization of the class of hierarchical CQs from Boolean to non-Boolean queries. In particular, max, min, and count-distinct match the class of CQs that are all-hierarchical (i.e., hierarchical with respect to all variables), and average and quantile match the narrower class of q-hierarchical CQs introduced by Berkholz, Keppeler, and Schweikardt (2017) in the context of the fine-grained complexity of query answering. Finally, we show an example of an aggregate function---''has-duplicates''---that gives rise to a new variation of hierarchy that is more restricted than q-hierarchy.

  • Open Access

    Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries

    by Christoph Standke, Benny Kimelfeld

    In recent years, the Shapley value has emerged as a general game-theoretic measure for assessing the contribution of a tuple to the result of a database query. We study the complexity of calculating the Shapley value of a tuple for an aggregate conjunctive query, which applies an aggregation function to the result of a conjunctive query (CQ) based on a value function that assigns a number to each query answer. Prior work by Livshits, Bertossi, Kimelfeld, and Sebag (2020) established that this task is #P-hard for every nontrivial aggregation function when the query is non-hierarchical with respect to its existential variables, assuming the absence of self-joins. They further showed that this condition precisely characterizes the class of intractable CQs when the aggregate function is sum or count. In addition, they posed as open problems the complexity of other common aggregate functions such as min, max, count-distinct, average, and quantile (including median). Towards the resolution of these problems, we identify for each aggregate function a class of hierarchical CQs where the Shapley value is tractable with every value function, as long as it is local (i.e., determined by the tuples of one relation). We further show that each such class is maximal: for every CQ outside of this class, there is a local (easy-to-compute) value function that makes the Shapley value #P-hard. Interestingly, our results reveal that each aggregate function corresponds to a different generalization of the class of hierarchical CQs from Boolean to non-Boolean queries. In particular, max, min, and count-distinct match the class of CQs that are all-hierarchical (i.e., hierarchical with respect to all variables), and average and quantile match the narrower class of q-hierarchical CQs introduced by Berkholz, Keppeler, and Schweikardt (2017) in the context of the fine-grained complexity of query answering.

  • Open Access

    Approval-based committee voting under incomplete information

    by Aviram Imber, Jonas Israel, Markus Brill, Benny Kimelfeld


  • Open Access

    Computing Inconsistency Measures Under Differential Privacy

    by Shubhankar Mohapatra, Amir Gilad, Xi He, Benny Kimelfeld

    Assessing data quality is crucial to knowing whether and how to use the data for different purposes. Specifically, given a collection of integrity constraints, various ways have been proposed to quantify the inconsistency of a database. Inconsistency measures are particularly important when we wish to assess the quality of private data without revealing sensitive information. We study the estimation of inconsistency measures for a database protected under Differential Privacy (DP). Such estimation is nontrivial since some measures intrinsically query sensitive information, and the computation of others involves functions on underlying sensitive data. Among five inconsistency measures that have been proposed in recent work, we identify that two are intractable in the DP setting. The major challenge for the other three is high sensitivity: adding or removing one tuple from the dataset may significantly affect the outcome. To mitigate that, we model the dataset using a conflict graph and investigate private graph statistics to estimate these measures. The proposed machinery includes adapting graph-projection techniques with parameter selection optimizations on the conflict graph and a DP variant of approximate vertex cover size. We experimentally show that we can effectively compute DP estimates of the three measures on five real-world datasets with denial constraints, where the density of the conflict graphs highly varies.


  • Open Access

    PACMMOD, V3, N2 (PODS), May 2025 Editorial

    by Nofar Carmeli, Floris Geerts, Ahmet Kara, Benny Kimelfeld

    We are excited to announce the third issue dedicated to the Principles of Database Systems (PODS) research track of the Proceedings of the ACM on Management of Data (PACMMOD) journal. In its current form, the journal hosts both a SIGMOD and a PODS research track. The PODS research track aims to provide a solid scientific foundation for methods, techniques, and solutions to the data management challenges that continually arise in our data-driven society. More specifically, articles in the PODS track of PACMMOD present principled contributions to modeling, application, system building, and both theoretical and experimental validation in the context of data management. Such articles may be based, among others, on establishing theoretical results, developing new concepts and frameworks that merit further exploration, providing experimental work that sheds light on the scientific foundations of the discipline, or conducting a rigorous analysis of widely used and/or recently developed industry artifacts.