Document Open Access Logo

Answer Counting Under Guarded TGDs

Authors Cristina Feier, Carsten Lutz, Marcin Przybyłko

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2021.11.pdf
  • Filesize: 0.84 MB
  • 22 pages

Document Identifiers

Author Details

Cristina Feier
  • Department of Computer Science, Universität Bremen, Germany
Carsten Lutz
  • Department of Computer Science, Universität Bremen, Germany
Marcin Przybyłko
  • Department of Computer Science, Universität Bremen, Germany

Funding

This research was funded by ERC consolidator grant 647289 CODA and by DFG project QTEC.

Acknowledgements

We thank the anonymous reviewers for useful comments.

Cite As Get BibTex

Cristina Feier, Carsten Lutz, and Marcin Przybyłko. Answer Counting Under Guarded TGDs. In 24th International Conference on Database Theory (ICDT 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 186, pp. 11:1-11:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ICDT.2021.11

Abstract

We study the complexity of answer counting for ontology-mediated queries and for querying under constraints, considering conjunctive queries and unions thereof (UCQs) as the query language and guarded TGDs as the ontology and constraint language, respectively. Our main result is a classification according to whether answer counting is fixed-parameter tractable (FPT), W[1]-equivalent, #W[1]-equivalent, #W[2]-hard, or #A[2]-equivalent, lifting a recent classification for UCQs without ontologies and constraints due to Dell et al. [Holger Dell et al., 2019]. The classification pertains to various structural measures, namely treewidth, contract treewidth, starsize, and linked matching number. Our results rest on the assumption that the arity of relation symbols is bounded by a constant and, in the case of ontology-mediated querying, that all symbols from the ontology and query can occur in the data (so-called full data schema). We also study the meta-problems for the mentioned structural measures, that is, to decide whether a given ontology-mediated query or constraint-query specification is equivalent to one for which the structural measure is bounded.

Subject Classification

ACM Subject Classification
  • Theory of computation → Database theory
Keywords
  • Ontology-Mediated Querying
  • Querying under Constraints
  • Answer Counting
  • Parameterized Complexity

Metrics

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

Related Versions

References

  1. Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995. URL: http://webdam.inria.fr/Alice/.
  2. Franz Baader, Ian Horrocks, Carsten Lutz, and Ulrike Sattler. An Introduction to Description Logic. Cambridge University Press, 2017. URL: https://doi.org/10.1017/9781139025355.
  3. Jean-François Baget, Michel Leclère, Marie-Laure Mugnier, and Eric Salvat. On rules with existential variables: Walking the decidability line. Artif. Intell., 175(9-10):1620-1654, 2011. URL: https://doi.org/10.1016/j.artint.2011.03.002.
  4. Pablo Barceló, Gerald Berger, and Andreas Pieris. Containment for rule-based ontology-mediated queries. In PODS, pages 267-279, 2018. URL: https://doi.org/10.1145/3196959.3196963.
  5. Pablo Barceló, Victor Dalmau, Cristina Feier, Carsten Lutz, and Andreas Pieris. The limits of efficiency for open- and closed-world query evaluation under guarded TGDs. In Proc. of PODS, 2020. URL: https://doi.org/10.1145/3375395.3387653.
  6. Pablo Barceló, Cristina Feier, Carsten Lutz, and Andreas Pieris. When is ontology-mediated querying efficient? In Proc. of LICS, pages 1-13, 2019. URL: https://doi.org/10.1109/LICS.2019.8785823.
  7. Pablo Barceló, Diego Figueira, Georg Gottlob, and Andreas Pieris. Semantic optimization of conjunctive queries. J. ACM, 67(6), 2020. URL: https://doi.org/10.1145/3424908.
  8. Pablo Barceló, Georg Gottlob, and Andreas Pieris. Semantic acyclicity under constraints. In PODS, pages 343-354, 2016. URL: https://doi.org/10.1145/2902251.2902302.
  9. Meghyn Bienvenu, Quentin Manière, and Michaël Thomazo. Answering counting queries over DL-Lite ontologies. In Proc. of IJCAI, 2020. URL: https://doi.org/10.24963/ijcai.2020/223.
  10. Meghyn Bienvenu and Magdalena Ortiz. Ontology-mediated query answering with data-tractable description logics. In Proc. of Reasoning Web, volume 9203 of LNCS, pages 218-307. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21768-0_9.
  11. Meghyn Bienvenu, Balder ten Cate, Carsten Lutz, and Frank Wolter. Ontology-based data access: A study through disjunctive datalog, CSP, and MMSNP. ACM Trans. Database Syst., 39(4):33:1-33:44, 2014. URL: https://doi.org/10.1145/2661643.
  12. Andrea Calì, Georg Gottlob, and Michael Kifer. Taming the infinite chase: Query answering under expressive relational constraints. J. Artif. Intell. Res., 48:115-174, 2013. URL: https://doi.org/10.1613/jair.3873.
  13. Andrea Calì, Georg Gottlob, and Andreas Pieris. Towards more expressive ontology languages: The query answering problem. Artif. Intell., 193:87-128, 2012. URL: https://doi.org/10.1016/j.artint.2012.08.002.
  14. Diego Calvanese, Julien Corman, Davide Lanti, and Simon Razniewski. Counting query answers over DL-Lite knowledge base. In Proc. of IJCAI, 2020. URL: https://doi.org/10.24963/ijcai.2020/230.
  15. Diego Calvanese, Giuseppe De Giacomo, and Maurizio Lenzerini. On the decidability of query containment under constraints. In Proc. of PODS, pages 149-158. ACM Press, 1998. URL: https://doi.org/10.1145/275487.275504.
  16. Hubie Chen and Stefan Mengel. A trichotomy in the complexity of counting answers to conjunctive queries. In Proc. of ICDT, pages 110-126, 2015. URL: https://doi.org/10.4230/LIPIcs.ICDT.2015.110.
  17. Hubie Chen and Stefan Mengel. Counting answers to existential positive queries: A complexity classification. In Proc. of PODS, pages 315-326, 2016. URL: https://doi.org/10.1145/2902251.2902279.
  18. Víctor Dalmau and Peter Jonsson. The complexity of counting homomorphisms seen from the other side. J. Theor. Comput. Sci., 329(1-3):315-323, 2004. URL: https://doi.org/10.1016/j.tcs.2004.08.008.
  19. Holger Dell, Marc Roth, and Philip Wellnitz. Counting answers to existential questions. In Proc. of ICALP, pages 113:1-113:15, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.113.
  20. Arnaud Durand and Stefan Mengel. The complexity of weighted counting for acyclic conjunctive queries. J. Comput. Syst. Sci., 80(1):277-296, 2014. URL: https://doi.org/10.1016/j.jcss.2013.08.001.
  21. Arnaud Durand and Stefan Mengel. Structural tractability of counting of solutions to conjunctive queries. J. Theory Comput. Syst., 57(4):1202-1249, 2015. URL: https://doi.org/10.1007/s00224-014-9543-y.
  22. Ronald Fagin, Phokion G. Kolaitis, Renée J. Miller, and Lucian Popa. Data exchange: semantics and query answering. J. Theor. Comput. Sci., 336(1):89-124, 2005. URL: https://doi.org/10.1016/j.tcs.2004.10.033.
  23. Cristina Feier, Carsten Lutz, and Marcin Przybyłko. Answer counting under guarded TGDs, 2021. URL: http://arxiv.org/abs/2101.03058.
  24. Diego Figueira. Semantically acyclic conjunctive queries under functional dependencies. In Proc. of LICS, page 847–856. ACM, 2016. URL: https://doi.org/10.1145/2933575.2933580.
  25. Jörg Flum and Martin Grohe. The parameterized complexity of counting problems. SIAM J. Comput., 33(4):892-922, 2004. URL: https://doi.org/10.1137/S0097539703427203.
  26. Martin Grohe. The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM, 54(1):1:1-1:24, 2007. URL: https://doi.org/10.1145/1206035.1206036.
  27. David S. Johnson and Anthony C. Klug. Testing containment of conjunctive queries under functional and inclusion dependencies. J. Comput. Syst. Sci., 28(1):167-189, 1984. URL: https://doi.org/10.1016/0022-0000(84)90081-3.
  28. Bogdan Kostov and Petr Kremen. Count distinct semantic queries over multiple linked datasets. OJSW, 5(1):1-11, 2018. URL: http://nbn-resolving.de/urn:nbn:de:101:1-201712245426.
  29. Egor V. Kostylev and Juan L. Reutter. Complexity of answering counting aggregate queries over DL-Lite. J. Web Semant., 33:94-111, 2015. URL: https://doi.org/10.1016/j.websem.2015.05.003.
  30. Nicola Leone, Marco Manna, Giorgio Terracina, and Pierfrancesco Veltri. Fast query answering over existential rules. ACM Trans. Comput. Log., 20(2):12:1-12:48, 2019. URL: https://doi.org/10.1145/3308448.
  31. David Maier, Alberto O. Mendelzon, and Yehoshua Sagiv. Testing implications of data dependencies. ACM Trans. Database Syst., 4(4):455-469, 1979. URL: https://doi.org/10.1145/320107.320115.
  32. Reinhard Pichler and Sebastian Skritek. Tractable counting of the answers to conjunctive queries. J. Comput. Syst. Sci., 79(6):984-1001, 2013. URL: https://doi.org/10.1016/j.jcss.2013.01.012.
  33. Antonella Poggi, Domenico Lembo, Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Riccardo Rosati. Linking data to ontologies. J. Data Semantics, 4900:133-173, 2008. URL: https://doi.org/10.1007/978-3-540-77688-8_5.
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