Batya Kenig

Dr. Batya Kenig


Research Focus & Metrics

Representative Publications

View All Publications
18 June 2023
Verified
Conference Paper
Open access
BKBatya Kenig
Batya Kenig
NWNIR WEINBERGER
NIR WEINBERGER
Acyclic schemes posses known benefits for database design, speeding up queries, and reducing space requirements. An acyclic join dependency (AJD) is lossless with respect to a universal relation if joining the projections associated with the schema results in the original universal relation. An intuitive and standard measure of loss entailed by an AJD is the number of redundant tuples generated by the acyclic join. Recent work has shown that the loss of an AJD can also be characterized by an information-theoretic measure. Motivated by the problem of automatically fitting an acyclic schema to a universal relation, we investigate the connection between these two characterizations of loss. We first show that the loss of an AJD is captured using the notion of KL-Divergence. We then show that the KL-divergence can be used to bound the number of redundant tuples. We prove a deterministic lower bound on the percentage of redundant tuples. For an upper bound, we propose a random database model, and establish a high probability bound on the percentage of redundant tuples, which coincides with the lower bound for large databases.


22 June 2025
Verified
Conference Paper
Open access
NCNoam Chen
Noam Chen
AZAnna Zeng
Anna Zeng
MCMichael Cafarella
Michael Cafarella
BKBatya Kenig
Batya Kenig
MMMarkos Markakis
Markos Markakis
BSBabak Salimi
Babak Salimi

21 April 2025 in arXiv
Verified
Preprint
Open access
PDF file
AZAnna Zeng
Anna Zeng
MCMichael Cafarella
Michael Cafarella
BKBatya Kenig
Batya Kenig
MMMarkos Markakis
Markos Markakis
BYBrit Youngmann
Brit Youngmann
BSBabak Salimi
Babak Salimi
Causal inference aids researchers in discovering cause-and-effect relationships, leading to scientific insights. Accurate causal estimation requires identifying confounding variables to avoid false discoveries. Pearl's causal model uses causal DAGs to identify confounding variables, but incorrect DAGs can lead to unreliable causal conclusions. However, for high dimensional data, the causal DAGs are often complex beyond human verifiability. Graph summarization is a logical next step, but current methods for general-purpose graph summarization are inadequate for causal DAG summarization. This paper addresses these challenges by proposing a causal graph summarization objective that balances graph simplification for better understanding while retaining essential causal information for reliable inference. We develop an efficient greedy algorithm and show that summary causal DAGs can be directly used for inference and are more robust to misspecification of assumptions, enhancing robustness for causal inference. Experimenting with six real-life datasets, we compared our algorithm to three existing solutions, showing its effectiveness in handling high-dimensional data and its ability to generate summary DAGs that ensure both reliable causal inference and robustness against misspecifications.