Document Open Access Logo

Connecting Width and Structure in Knowledge Compilation

Authors Antoine Amarilli, Mikaël Monet, Pierre Senellart

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2018.6.pdf
  • Filesize: 433 kB
  • 17 pages

Document Identifiers

Author Details

Antoine Amarilli
Mikaël Monet
Pierre Senellart

Cite As Get BibTex

Antoine Amarilli, Mikaël Monet, and Pierre Senellart. Connecting Width and Structure in Knowledge Compilation. In 21st International Conference on Database Theory (ICDT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 98, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICDT.2018.6

Abstract

Several query evaluation tasks can be done via knowledge compilation: the query result is compiled as a lineage circuit from which the answer can be determined. For such tasks, it is important to leverage some width parameters of the circuit, such as bounded treewidth or pathwidth, to convert the circuit to structured classes, e.g., deterministic structured NNFs (d-SDNNFs) or OBDDs. In this work, we show how to connect the width of circuits to the size of their structured representation, through upper and lower bounds. For the upper bound, we show how bounded-treewidth circuits can be converted to a d-SDNNF, in time linear in the circuit size. Our bound, unlike existing results, is constructive and only singly exponential in the treewidth. We show a related lower bound on monotone DNF or CNF formulas, assuming a constant bound on the arity (size of clauses) and degree (number of occurrences of each variable). Specifically, any d-SDNNF (resp., SDNNF) for such a DNF (resp., CNF) must be of exponential size in its treewidth; and the same holds for pathwidth when compiling to OBDDs. Our lower bounds, in contrast with most previous work, apply to any formula of this class, not just a well-chosen family. Hence, for our language of DNF and CNF, pathwidth and treewidth respectively characterize the efficiency of compiling to OBDDs and (d-)SDNNFs, that is, compilation is singly exponential in the width parameter. We conclude by applying our lower bound results to the task of query evaluation.

Subject Classification

Keywords
  • knowledge compilation
  • probabilistic databases
  • treewidth
  • circuits

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Antoine Amarilli. https://tel.archives-ouvertes.fr/tel-01345836. PhD thesis, https://www.telecom-paristech.fr/, 2016.
  2. Antoine Amarilli, Pierre Bourhis, Louis Jachiet, and Stefan Mengel. https://arxiv.org/abs/1702.05589. In http://icalp17.mimuw.edu.pl/, 2017.
  3. Antoine Amarilli, Pierre Bourhis, Mikaël Monet, and Pierre Senellart. https://arxiv.org/abs/1612.04203. CoRR, abs/1612.04203, 2017. Extended version of [4].
  4. Antoine Amarilli, Pierre Bourhis, Mikaël Monet, and Pierre Senellart. https://doi.org/10.4230/LIPIcs.ICDT.2017.6. In ICDT, 2017.
  5. Antoine Amarilli, Pierre Bourhis, and Pierre Senellart. https://arxiv.org/abs/1511.08723v1. CoRR, abs/1511.08723, 2015. Extended version of [6].
  6. Antoine Amarilli, Pierre Bourhis, and Pierre Senellart. Provenance circuits for trees and treelike instances. In ICALP, 2015. Google Scholar
  7. Antoine Amarilli, Pierre Bourhis, and Pierre Senellart. https://arxiv.org/abs/1604.02761. In http://sigmod2016.org/, 2016.
  8. Antoine Amarilli, Mikaël Monet, and Pierre Senellart. https://arxiv.org/abs/1709.06188. CoRR, abs/1709.06188, 2017.
  9. Paul Beame and Vincent Liew. https://arxiv.org/abs/1506.02639v2. In UAI, 2015.
  10. Hans L Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6), 1996. Google Scholar
  11. Simone Bova. https://arxiv.org/abs/1601.00501. In AAAI, 2016.
  12. Simone Bova, Florent Capelli, Stefan Mengel, and Friedrich Slivovsky. https://arxiv.org/abs/1411.1995v3. CoRR, abs/1411.1995, 2015.
  13. Simone Bova, Florent Capelli, Stefan Mengel, and Friedrich Slivovsky. https://www.ijcai.org/Proceedings/16/Papers/147.pdf. In IJCAI, 2016.
  14. Simone Bova and Friedrich Slivovsky. https://arxiv.org/abs/1411.5494. In CSR, 2015.
  15. Simone Bova and Friedrich Slivovsky. https://link.springer.com/article/10.1007/s00224-016-9715-z. TCS, 61(2), 2017.
  16. Simone Bova and Stefan Szeider. https://arxiv.org/abs/1701.04626. In PODS, 2017.
  17. Randal E. Bryant. http://repository.cmu.edu/cgi/viewcontent.cgi?article=1217&context=compsci. ACM Comput. Surv., 24(3), 1992.
  18. Andrea Calì, Florent Capelli, and Igor Razgon. https://arxiv.org/abs/1708.07767v1. CoRR, abs/1708.07767, 2017.
  19. Florent Capelli. https://www.dcs.bbk.ac.uk/~florent/these_capelli.pdf. PhD thesis, Université Paris-Diderot, 2016.
  20. Florent Capelli. https://arxiv.org/abs/1701.01461. In LICS, 2017.
  21. Chandra Chekuri and Julia Chuzhoy. https://arxiv.org/abs/1305.6577. In STOC, 2014.
  22. Adnan Darwiche. https://arxiv.org/abs/cs/0003044. J. Applied Non-Classical Logics, 11(1-2), 2001.
  23. Adnan Darwiche. https://doi.org/10.1145/765568.765570. JACM, 50(3), 2003.
  24. Adnan Darwiche. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-143. In IJCAI, 2011.
  25. Srinivas Devadas. https://pdfs.semanticscholar.org/38dc/b31dc422e6b68bf5f20ffa000d75606dc9f4.pdf. IEEE TCAD, 12(5), 1993.
  26. Andrea Ferrara, Guoqiang Pan, and Moshe Y Vardi. https://www.cs.rice.edu/~vardi/papers/lpar052.pdf. In LPAR, 2005.
  27. Daan Fierens, Guy Van den Broeck, Joris Renkens, Dimitar Shterionov, Bernd Gutmann, Ingo Thon, Gerda Janssens, and Luc De Raedt. https://www.cambridge.org/core/journals/theory-and-practice-of-logic-programming/article/inference-and-learning-in-probabilistic-logic-programs-using-weighted-boolean-formulas/9455B07774BA31AA4F6AB81FB0A6B013. TPLP, 15(3), 2015.
  28. Jörg Flum, Markus Frick, and Martin Grohe. Query evaluation via tree-decompositions. J. ACM, 49(6), 2002. Google Scholar
  29. Martin Grohe and Dániel Marx. http://www.sciencedirect.com/science/article/pii/S0095895608000683. J. Combinatorial Theory, Series B, 99(1), 2009.
  30. Abhay Kumar Jha, Dan Olteanu, and Dan Suciu. http://www.cs.ox.ac.uk/dan.olteanu/papers/jos-edbt10.pdf. In EDBT, 2010.
  31. Abhay Kumar Jha and Dan Suciu. http://openproceedings.org/2011/conf/icdt/JhaS11.pdf. In ICDT, 2011.
  32. Abhay Kumar Jha and Dan Suciu. https://homes.cs.washington.edu/~suciu/file37_paper.pdf. In ICDT, 2012.
  33. Steffen L. Lauritzen and David J. Spiegelhalter. Local computations with probabilities on graphical structures and their application to expert systems. J. Royal Statistical Society. Series B, 1988. Google Scholar
  34. Joakim Alme Nordstrand. http://bora.uib.no/handle/1956/16325. Master’s thesis, University of Bergen, 2017.
  35. Knot Pipatsrisawat and Adnan Darwiche. https://www.aaai.org/Papers/AAAI/2008/AAAI08-082.pdf. In AAAI, 2008.
  36. Knot Pipatsrisawat and Adnan Darwiche. https://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/view/1856/1991. In AAAI, 2010.
  37. Igor Razgon. https://www.aaai.org/ocs/index.php/KR/KR14/paper/download/7982/7918. In KR, 2014.
  38. Neil Robertson and P.D Seymour. Graph minors X. Obstructions to tree-decomposition. Journal of Combinatorial Theory, Series B, 52(2), 1991. Google Scholar
  39. Dan Suciu, Dan Olteanu, Christopher Ré, and Christoph Koch. Probabilistic Databases. Morgan &Claypool, 2011. Google Scholar
  40. Martin Vatshelle. https://www.ii.uib.no/~martinv/Papers/MartinThesis.pdf. PhD thesis, University of Bergen, 2012.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact