Document Open Access Logo

A Dichotomy for Homomorphism-Closed Queries on Probabilistic Graphs

Authors Antoine Amarilli , İsmail İlkan Ceylan

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2020.5.pdf
  • Filesize: 0.6 MB
  • 20 pages

Document Identifiers

Author Details

Antoine Amarilli
  • LTCI, Télécom Paris, Institut Polytechnique de Paris, France
İsmail İlkan Ceylan
  • University of Oxford, United Kingdom

Funding

This work was supported by the UK EPSRC grant EP/R013667/1.

Cite As Get BibTex

Antoine Amarilli and İsmail İlkan Ceylan. A Dichotomy for Homomorphism-Closed Queries on Probabilistic Graphs. In 23rd International Conference on Database Theory (ICDT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 155, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICDT.2020.5

Abstract

We study the problem of probabilistic query evaluation (PQE) over probabilistic graphs, namely, tuple-independent probabilistic databases (TIDs) on signatures of arity two. Our focus is the class of queries that is closed under homomorphisms, or equivalently, the infinite unions of conjunctive queries, denoted UCQ∞. Our main result states that all unbounded queries in UCQ∞ are #P-hard for PQE. As bounded queries in UCQ∞ are already classified by the dichotomy of Dalvi and Suciu [Dalvi and Suciu, 2012], our results and theirs imply a complete dichotomy on PQE for UCQ∞ queries over probabilistic graphs. This dichotomy covers in particular all fragments in UCQ∞ such as negation-free (disjunctive) Datalog, regular path queries, and a large class of ontology-mediated queries on arity-two signatures. Our result is shown by reducing from counting the valuations of positive partitioned 2-DNF formulae (#PP2DNF) for some queries, or from the source-to-target reliability problem in an undirected graph (#U-ST-CON) for other queries, depending on properties of minimal models.

Subject Classification

ACM Subject Classification
  • Theory of computation → Database query processing and optimization (theory)
Keywords
  • Tuple-independent database
  • #P-hardness
  • recursive queries
  • homomorphism-closed queries

Metrics

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

Related Versions

Supplementary Materials

References

  1. Serge Abiteboul, Richard Hull, and Victor Vianu. http://webdam.inria.fr/Alice/pdfs/all.pdf. Addison-Wesley, 1995. URL: http://webdam.inria.fr/Alice/pdfs/all.pdf.
  2. Antoine Amarilli, Pierre Bourhis, and Pierre Senellart. https://arxiv.org/abs/1604.02761. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS-16), pages 355-370. ACM, 2016. URL: https://arxiv.org/abs/1604.02761.
  3. Antoine Amarilli and İsmail İlkan Ceylan. https://arxiv.org/abs/1910.02048, 2020. Full version with proofs: URL: https://arxiv.org/abs/1910.02048.
  4. Antoine Amarilli and Benny Kimelfeld. https://arxiv.org/abs/1908.07093. CoRR, abs/1908.07093, 2019. URL: https://arxiv.org/abs/1908.07093.
  5. Franz Baader, Diego Calvanese, Deborah L McGuinness, Daniele Nardi, and Peter F. Patel-Schneider, editors. https://www.researchgate.net/publication/230745455_The_Description_Logic_Handbook_Theory_Implementation_and_Applications. Cambridge University Press, 2007. URL: https://www.researchgate.net/publication/230745455_The_Description_Logic_Handbook_Theory_Implementation_and_Applications.
  6. Pablo Barceló, Diego Figueira, and Miguel Romero. Boundedness of conjunctive regular path queries, 2019. URL: https://hal.archives-ouvertes.fr/hal-02056388/.
  7. Michael Benedikt, Balder Ten Cate, Thomas Colcombet, and Michael Vanden Boom. https://web.comlab.ox.ac.uk/people/michael.vandenboom/papers/LICS15-gnfpb-long.pdf. In 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 293-304. IEEE, 2015. URL: https://web.comlab.ox.ac.uk/people/michael.vandenboom/papers/LICS15-gnfpb-long.pdf.
  8. Meghyn Bienvenu, Balder Ten Cate, Carsten Lutz, and Frank Wolter. https://arxiv.org/abs/1301.6479. ACM Transactions on Database Systems (TODS), 39(4):33:1-33:44, 2014. URL: https://arxiv.org/abs/1301.6479.
  9. Stefan Borgwardt, İsmail İlkan Ceylan, and Thomas Lukasiewicz. https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/download/14365/13881. In Proceedings of the 31th AAAI Conference on Artificial Intelligence (AAAI-17), pages 1063-1069. AAAI Press, 2017. URL: https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/download/14365/13881.
  10. Stefan Borgwardt, İsmail İlkan Ceylan, and Thomas Lukasiewicz. https://lat.inf.tu-dresden.de/research/papers/2019/BoCL-AAAI19.pdf. In Proceedings of the 33rd National Conference on Artificial Intelligence (AAAI-19). AAAI Press, 2019. URL: https://lat.inf.tu-dresden.de/research/papers/2019/BoCL-AAAI19.pdf.
  11. Andrea Calì, Georg Gottlob, and Michael Kifer. https://www.jair.org/index.php/jair/article/view/10837. JAIR, 48:115-174, 2013. URL: https://www.jair.org/index.php/jair/article/view/10837.
  12. Andrea Calì, Georg Gottlob, and Thomas Lukasiewicz. https://www.cs.ox.ac.uk/files/3608/rr1021.pdf. J. Web Sem., 14:57-83, 2012. URL: https://www.cs.ox.ac.uk/files/3608/rr1021.pdf.
  13. İsmail İlkan Ceylan. https://lat.inf.tu-dresden.de/research/theses/2017/Ceylan-Diss-2017.pdf. Doctoral thesis, TU Dresden, 2017. URL: https://lat.inf.tu-dresden.de/research/theses/2017/Ceylan-Diss-2017.pdf.
  14. İsmail İlkan Ceylan, Adnan Darwiche, and Guy Van den Broeck. https://www.aaai.org/ocs/index.php/KR/KR16/paper/download/12908/12490. In Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning (KR-16), pages 339-348. AAAI Press, 2016. URL: https://www.aaai.org/ocs/index.php/KR/KR16/paper/download/12908/12490.
  15. Stephen A. Cook. https://www.cs.toronto.edu/~sacook/homepage/1971.pdf. In Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (STOC-71), pages 151-158. ACM, 1971. URL: https://www.cs.toronto.edu/~sacook/homepage/1971.pdf.
  16. Nilesh Dalvi and Dan Suciu. https://homes.cs.washington.edu/~suciu/vldbj-probdb.pdf. The VLDB Journal, 16(4):523-544, 2007. URL: https://homes.cs.washington.edu/~suciu/vldbj-probdb.pdf.
  17. Nilesh Dalvi and Dan Suciu. https://homes.cs.washington.edu/~suciu/jacm-dichotomy.pdf. J. ACM, 59(6), 2012. URL: https://homes.cs.washington.edu/~suciu/jacm-dichotomy.pdf.
  18. Anuj Dawar and Stephan Kreutzer. https://ora.ox.ac.uk/objects/uuid:73527af8-31b9-4108-a07d-058967ba97e4/download_file?safe_filename=08-icalp.pdf&file_format=application%2Fpdf&type_of_work=Conference+item. In International Colloquium on Automata, Languages, and Programming, pages 160-171. Springer, 2008. URL: https://ora.ox.ac.uk/objects/uuid:73527af8-31b9-4108-a07d-058967ba97e4/download_file?safe_filename=08-icalp.pdf&file_format=application%2Fpdf&type_of_work=Conference+item.
  19. Xin Dong, Evgeniy Gabrilovich, Geremy Heitz, Wilko Horn, Ni Lao, Kevin Murphy, Thomas Strohmann, Shaohua Sun, and Wei Zhang. https://www.cs.ubc.ca/~murphyk/Papers/kv-kdd14.pdf. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 601-610. ACM, 2014. URL: https://www.cs.ubc.ca/~murphyk/Papers/kv-kdd14.pdf.
  20. Thomas Eiter, Magdalena Ortiz, Mantas Šimkus, Trung-Kien Tran, and Guohui Xiao. https://pdfs.semanticscholar.org/9716/6f9b284d8e7da46bd6cd43b43a7af14b773c.pdf. In AAAI, 2012. URL: https://pdfs.semanticscholar.org/9716/6f9b284d8e7da46bd6cd43b43a7af14b773c.pdf.
  21. Robert Fink and Dan Olteanu. http://www.cs.ox.ac.uk/people/Dan.Olteanu/papers/fo-tods16.pdf. ACM Transactions on Database Systems (TODS), 41(1):4:1-4:47, 2016. URL: http://www.cs.ox.ac.uk/people/Dan.Olteanu/papers/fo-tods16.pdf.
  22. Haim Gaifman, Harry Mairson, Yehoshua Sagiv, and Moshe Y. Vardi. Undecidable optimization problems for database logic programs. J. ACM, 40(3):683-713, July 1993. Google Scholar
  23. Georg Gottlob and Thomas Schwentick. http://ceur-ws.org/Vol-745/paper_21.pdf. In KR, 2012. URL: http://ceur-ws.org/Vol-745/paper_21.pdf.
  24. Gerd G Hillebrand, Paris C Kanellakis, Harry G Mairson, and Moshe Y Vardi. https://www.sciencedirect.com/science/article/pii/074310669500051K. The Journal of Logic Programming, 25(2):163-190, 1995. URL: https://www.sciencedirect.com/science/article/pii/074310669500051K.
  25. Johannes Hoffart, Fabian M. Suchanek, Klaus Berberich, and Gerhard Weikum. https://www.sciencedirect.com/science/article/pii/S0004370212000719. Artificial Intelligence, 194:28-61, 2013. URL: https://www.sciencedirect.com/science/article/pii/S0004370212000719.
  26. Jean Christoph Jung. http://www.informatik.uni-bremen.de/~jeanjung/pub/phdjung.pdf. PhD thesis, University of Bremen, 2014. URL: http://www.informatik.uni-bremen.de/~jeanjung/pub/phdjung.pdf.
  27. Jean Christoph Jung and Carsten Lutz. https://iswc2012.semanticweb.org/sites/default/files/76490177.pdf. In Proceedings of the 11th International Conference on The Semantic Web - Volume Part I, pages 182-197. Springer-Verlag, 2012. URL: https://iswc2012.semanticweb.org/sites/default/files/76490177.pdf.
  28. T. Mitchell, W. Cohen, E. Hruschka, P. Talukdar, J. Betteridge, A. Carlson, B. Dalvi, M. Gardner, B. Kisiel, J. Krishnamurthy, N. Lao, K. Mazaitis, T. Mohamed, N. Nakashole, E. Platanios, A. Ritter, M. Samadi, B. Settles, R. Wang, D. Wijaya, A. Gupta, X. Chen, A. Saparov, M. Greaves, and J. Welling. https://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/10049/9557. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI-15), pages 2302-2310, 2015. URL: https://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/10049/9557.
  29. Dan Olteanu and Jiewen Huang. https://www.cs.ox.ac.uk/people/dan.olteanu/papers/oh-sum08.pdf. In Proceedings of the 2nd International Conference on Scalable Uncertainty Management (SUM-08), volume 5291 of LNCS, pages 326-340, 2008. URL: https://www.cs.ox.ac.uk/people/dan.olteanu/papers/oh-sum08.pdf.
  30. Dan Olteanu and Jiewen Huang. https://www.cs.ox.ac.uk/people/dan.olteanu/papers/oh-sigmod09.pdf. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data, pages 389-402. ACM, 2009. URL: https://www.cs.ox.ac.uk/people/dan.olteanu/papers/oh-sigmod09.pdf.
  31. J. Scott Provan and Michael O. Ball. The complexity of counting cuts and of computing the probability that a graph is connected. SIAM Journal on Computing, 12(4), 1983 . Google Scholar
  32. Christopher Ré and Dan Suciu. https://www.cs.stanford.edu/people/chrismre/papers/journal_having_queries.pdf. The VLDB Journal, 18(5):1091-1116, 2009. URL: https://www.cs.stanford.edu/people/chrismre/papers/journal_having_queries.pdf.
  33. Dan Suciu, Dan Olteanu, Christopher Ré, and Christoph Koch. Probabilistic databases, volume 3. Morgan-Claypool, 2011. Google Scholar
  34. Leslie Gabriel Valiant. https://www.sciencedirect.com/science/article/pii/0304397579900446. TCS, 8(2):189-201, 1979. URL: https://www.sciencedirect.com/science/article/pii/0304397579900446.
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