2025-06-04 - Paper accepted at PODS 2025

Finding a Smallest Synthetic Witness

Congrats to Aryan for getting yet another paper [1] accepted to PODS 2025! Thanks to Aryan, Xiao, and Stavros for letting me join the fun on this one.

The problem studied in this work is the following: Given a query $Q$ and result $R$, find the smallest database $D$ such that $Q(D) = R$. One can think about this as a generalization of provenance and the smallest witness problem that Xiao and Stavros did study in their recent ICDT best paper where an initial database $D'$ with $Q(D') = R$ was given and the goal was to find a smallest $D \subseteq D'$ such that $Q(D) = R$. Alternatively, this can be viewed as a view update / reverse data management problem: Given an empty database and query result, insert $R$ into the view defined by $Q$.

On the technical side, we show that for head-dominated conjunctive queries, the problem can be solved in polynomial time in data complexity (the size of $R$) and present a full dichotomy for Berge-acyclic queries which include the important class of path queries. Interestingly, testing whether the problem has a solution (there exists at least one $D$ such that $Q(D) = R$ ) is in PTIME.

1. 1 J PODS Smallest Synthetic Witnesses for Conjunctive Queries
   Aryan Esmailpourlialestani, Boris Glavic, Xiao Hu and Stavros Sintos
   PODS. 3, 2 (2025) , 113:1–113:25.
   • BibTex
   • doi
   • pdf
   • details

   @article{EG25,
     author = {Esmailpourlialestani, Aryan and Glavic, Boris and Hu, Xiao and Sintos, Stavros},
     title = {Smallest Synthetic Witnesses for Conjunctive Queries},
     booktitle = {PODS},
     year = {2025},
     journal = {Proc. {ACM} Manag. Data},
     volume = {3},
     number = {2},
     pages = {113:1--113:25},
     url = {https://doi.org/10.1145/3725250},
     doi = {10.1145/3725250},
     pdfurl = {http://www.cs.uic.edu/%7ebglavic/dbgroup/assets/pdfpubls/EG25.pdf},
     venueshort = {{PODS}},
     keywords = {Provenance}
   }
   

   
   
   details