Circuits and Databases

This is a collection of papers at the intersection of circuits and databases. To contribute, add an entry in cdb.bib. Make sure to copy directly from DBLP when possible, and do not change the citation ID. If you want to compile on your machine, install pandoc and run make.

[1]
Amarilli, A. et al. 2023. Conjunctive queries on probabilistic graphs: The limits of approximability. CoRR. abs/2309.13287, (2023). DOI:https://doi.org/10.48550/ARXIV.2309.13287.
[2]
Amarilli, A. et al. 2018. Connecting width and structure in knowledge compilation. 21st international conference on database theory, ICDT 2018, march 26-29, 2018, vienna, austria (2018), 6:1–6:17.
[3]
Amarilli, A. et al. 2015. Provenance circuits for trees and treelike instances. Automata, languages, and programming - 42nd international colloquium, ICALP 2015, kyoto, japan, july 6-10, 2015, proceedings, part II (2015), 56–68.
[4]
Amarilli, A. et al. 2023. Ranked enumeration for MSO on trees via knowledge compilation. CoRR. abs/2310.00731, (2023). DOI:https://doi.org/10.48550/ARXIV.2310.00731.
[5]
Amarilli, A. et al. 2016. Tractable lineages on treelike instances: Limits and extensions. Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI symposium on principles of database systems, PODS 2016, san francisco, CA, USA, june 26 - july 01, 2016 (2016), 355–370.
[6]
Deutch, D. et al. 2014. Circuits for datalog provenance. Proc. 17th international conference on database theory (ICDT), athens, greece, march 24-28, 2014 (2014), 201–212.
[7]
Jha, A.K. and Suciu, D. 2013. Knowledge compilation meets database theory: Compiling queries to decision diagrams. Theory Comput. Syst. 52, 3 (2013), 403–440. DOI:https://doi.org/10.1007/S00224-012-9392-5.
[8]
Jha, A.K. and Suciu, D. 2012. On the tractability of query compilation and bounded treewidth. 15th international conference on database theory, ICDT ’12, berlin, germany, march 26-29, 2012 (2012), 249–261.
[9]
Lam, M.S. et al. 2005. Context-sensitive program analysis as database queries. Proceedings of the twenty-fourth ACM SIGACT-SIGMOD-SIGART symposium on principles of database systems, june 13-15, 2005, baltimore, maryland, USA (2005), 1–12.
[10]
Monet, M. 2020. Solving a special case of the intensional vs extensional conjecture in probabilistic databases. Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI symposium on principles of database systems, PODS 2020, portland, OR, USA, june 14-19, 2020 (2020), 149–163.
[11]
Olteanu, D. 2016. Factorized databases: A knowledge compilation perspective. Beyond NP, papers from the 2016 AAAI workshop, phoenix, arizona, USA, february 12, 2016 (2016).
[12]
Olteanu, D. and Huang, J. 2008. Using OBDDs for efficient query evaluation on probabilistic databases. Scalable uncertainty management, second international conference, SUM 2008, naples, italy, october 1-3, 2008. proceedings (2008), 326–340.
[13]
Olteanu, D. and Závodný, J. 2015. Size bounds for factorised representations of query results. ACM Trans. Database Syst. 40, 1 (2015), 2:1–2:44. DOI:https://doi.org/10.1145/2656335.