Checking the Data Complexity of Ontology-Mediated Queries: A Case Study with Non-uniform CSPs and Polyanna | SpringerLink
Skip to main content
Springer Nature Link
Log in

Checking the Data Complexity of Ontology-Mediated Queries: A Case Study with Non-uniform CSPs and Polyanna

  • Chapter
  • First Online:
Description Logic, Theory Combination, and All That

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 11560))

  • 721 Accesses

Abstract

It has recently been shown that first-order- and datalog-rewritability of ontology-mediated queries (OMQs) with expressive ontologies can be checked in NExpTime using a reduction to CSPs. In this paper, we present a case study for OMQs with Boolean conjunctive queries and a fixed ontology consisting of a single covering axiom \(A \sqsubseteq F \sqcup T\), possibly supplemented with a disjointness axiom for T and F. The ultimate aim is to classify such OMQs according to their data complexity: \(\textsc {AC}^0\), L, NL, P or coNP. We report on our experience with trying to distinguish between OMQs in P and coNP using the reduction to CSPs and the Polyanna software for finding polymorphisms.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    http://sws.ifi.uio.no/project/npd-v2/.

  2. 2.

    Path CQs of length 5 produce templates of size 16, and it takes over an hour to detect its core.

References

  1. Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading (1995)

    MATH  Google Scholar 

  2. Afrati, F.N., Gergatsoulis, M., Toni, F.: Linearisability on datalog programs. Theor. Comput. Sci. 308(1–3), 199–226 (2003). https://doi.org/10.1016/S0304-3975(02)00730-2

    Article  MathSciNet  MATH  Google Scholar 

  3. Arora, S., Barak, B.: Computational Complexity: A Modern Approach, 1st edn. Cambridge University Press, New York (2009)

    Book  Google Scholar 

  4. Baader, F., Horrocks, I., Lutz, C., Sattler, U.: An Introduction to Description Logic. Cambridge University Press, Cambridge (2017). http://www.cambridge.org/de/academic/subjects/computer-science/knowledge-management-databases-and-data-mining/introduction-description-logic?format=PB#17zVGeWD2TZUeu6s.97

    Book  Google Scholar 

  5. Barto, L., Krokhin, A., Willard, R.: Polymorphisms, and how to use them. In: Dagstuhl Follow-Ups. vol. 7. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017)

    Google Scholar 

  6. Benedikt, M., ten Cate, B., Colcombet, T., Vanden Boom, M.: The complexity of boundedness for guarded logics. In: 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, 6–10 July 2015, pp. 293–304. IEEE Computer Society (2015). https://doi.org/10.1109/LICS.2015.36

  7. Benedikt, M., Grau, B.C., Kostylev, E.V.: Logical foundations of information disclosure in ontology-based data integration. Artif. Intell. 262, 52–95 (2018). https://doi.org/10.1016/j.artint.2018.06.002

    Article  MathSciNet  MATH  Google Scholar 

  8. Bienvenu, M., ten Cate, B., Lutz, C., Wolter, F.: Ontology-based data access: a study through disjunctive datalog, CSP, and MMSNP. ACM Trans. Database Syst. 39(4), 33:1–33:44 (2014)

    Article  MathSciNet  Google Scholar 

  9. Bulatov, A.A.: A dichotomy theorem for nonuniform CSPs. In: Umans, C. (ed.) 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, 15–17 October 2017, pp. 319–330. IEEE Computer Society (2017). https://doi.org/10.1109/FOCS.2017.37

  10. Calvanese, D., et al.: The MASTRO system for ontology-based data access. Semant. Web 2(1), 43–53 (2011)

    Google Scholar 

  11. Calvanese, D., et al.: Ontop: answering SPARQL queries over relational databases. Semant. Web 8(3), 471–487 (2017)

    Article  Google Scholar 

  12. Cosmadakis, S.S., Gaifman, H., Kanellakis, P.C., Vardi, M.Y.: Decidable optimization problems for database logic programs (preliminary report). In: STOC, pp. 477–490 (1988)

    Google Scholar 

  13. Gault, R., Jeavons, P.: Implementing a test for tractability. Constraints 9(2), 139–160 (2004)

    Article  MathSciNet  Google Scholar 

  14. Gerasimova, O., Kikot, S., Podolskii, V., Zakharyaschev, M.: More on the data complexity of answering ontology-mediated queries with a covering axiom. In: Różewski, P., Lange, C. (eds.) KESW 2017. CCIS, vol. 786, pp. 143–158. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-69548-8_11

    Chapter  Google Scholar 

  15. Gerasimova, O., Kikot, S., Podolskii, V.V., Zakharyaschev, M.: On the data complexity of ontology-mediated queries with a covering axiom. In: Artale, A., Glimm, B., Kontchakov, R. (eds.) Proceedings of the 30th International Workshop on Description Logics. CEUR Workshop Proceedings, Montpellier, France, 18–21 July 2017, vol. 1879. CEUR-WS.org (2017). http://ceur-ws.org/Vol-1879/paper39.pdf

  16. Gerasimova, O., Kikot, S., Zakharyaschev, M.: Towards a data complexity classification of ontology-mediated queries with covering. In: Ortiz, M., Schneider, T. (eds.) Proceedings of the 31st International Workshop on Description Logics co-located with 16th International Conference on Principles of Knowledge Representation and Reasoning (KR 2018), Tempe, Arizona, US. CEUR Workshop Proceedings, 27–29 October 2018, vol. 2211. CEUR-WS.org (2018). http://ceur-ws.org/Vol-2211/paper-36.pdf

  17. Hernich, A., Lutz, C., Ozaki, A., Wolter, F.: Schema.org as a description logic. In: Calvanese, D., Konev, B. (eds.) Proceedings of the 28th International Workshop on Description Logics. CEUR Workshop Proceedings, Athens, Greece, 7–10 June 2015, vol. 1350. CEUR-WS.org (2015). http://ceur-ws.org/Vol-1350/paper-24.pdf

  18. Jeavons, P., Cohen, D., Gyssens, M.: A test for tractability. In: Freuder, E.C. (ed.) CP 1996. LNCS, vol. 1118, pp. 267–281. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-61551-2_80

    Chapter  Google Scholar 

  19. Kaminski, M., Nenov, Y., Grau, B.C.: Datalog rewritability of disjunctive datalog programs and non-Horn ontologies. Artif. Intell. 236, 90–118 (2016). https://doi.org/10.1016/j.artint.2016.03.006

    Article  MathSciNet  MATH  Google Scholar 

  20. Kharlamov, E., et al.: Ontology based data access in Statoil. J. Web Semant. 44, 3–36 (2017). https://doi.org/10.1016/j.websem.2017.05.005

    Article  Google Scholar 

  21. Kozik, M.: Weak consistency notions for all the CSPs of bounded width. In: Grohe, M., Koskinen, E., Shankar, N. (eds.) Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2016, New York, NY, USA, 5–8 July 2016, pp. 633–641. ACM (2016). https://doi.org/10.1145/2933575.2934510

  22. Lanti, D., Rezk, M., Xiao, G., Calvanese, D.: The NPD benchmark: reality check for OBDA systems. In: Alonso, G., et al. (eds.) Proceedings of the 18th International Conference on Extending Database Technology, EDBT 2015, Brussels, Belgium, 23–27 March 2015, pp. 617–628. OpenProceedings.org (2015). https://doi.org/10.5441/002/edbt.2015.62

  23. Lutz, C., Sabellek, L.: Ontology-mediated querying with the description logic EL: trichotomy and linear datalog rewritability. In: Sierra, C. (ed.) Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, 19–25 August 2017, pp. 1181–1187. ijcai.org (2017). https://doi.org/10.24963/ijcai.2017/164

  24. Lutz, C., Wolter, F.: Non-uniform data complexity of query answering in description logics. In: Brewka, G., Eiter, T., McIlraith, S.A. (eds.) Principles of Knowledge Representation and Reasoning: Proceedings of the Thirteenth International Conference, KR 2012, Rome, Italy, 10–14 June 2012. AAAI Press (2012). http://www.aaai.org/ocs/index.php/KR/KR12/paper/view/4533

  25. Lutz, C., Wolter, F.: The data complexity of description logic ontologies. Log. Methods Comput. Sci. 13(4) (2017). https://doi.org/10.23638/LMCS-13(4:7)2017

  26. Marcinkowski, J.: DATALOG SIRUPs uniform boundedness is undecidable. In: Proceedings, 11th Annual IEEE Symposium on Logic in Computer Science, New Brunswick, New Jersey, USA, 27–30 July 1996, pp. 13–24. IEEE Computer Society (1996). https://doi.org/10.1109/LICS.1996.561299

  27. Papadimitriou, C.: Computational Complexity. Addison-Wesley, Boston (1994)

    MATH  Google Scholar 

  28. Poggi, A., Lembo, D., Calvanese, D., De Giacomo, G., Lenzerini, M., Rosati, R.: Linking data to ontologies. In: Spaccapietra, S. (ed.) Journal on Data Semantics X. LNCS, vol. 4900, pp. 133–173. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-77688-8_5

    Chapter  MATH  Google Scholar 

  29. Ramakrishnan, R., Sagiv, Y., Ullman, J.D., Vardi, M.Y.: Proof-tree transformation theorems and their applications. In: Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 172–181. ACM (1989)

    Google Scholar 

  30. Rodríguez-Muro, M., Kontchakov, R., Zakharyaschev, M.: Ontology-based data access: Ontop of databases. In: Alani, H., et al. (eds.) ISWC 2013. LNCS, vol. 8218, pp. 558–573. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-41335-3_35

    Chapter  Google Scholar 

  31. Saraiya, Y.P.: Linearizing nonlinear recursions in polynomial time. In: Silberschatz, A. (ed.) Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Philadelphia, Pennsylvania, USA, 29–31 March 1989, pp. 182–189. ACM Press (1989). https://doi.org/10.1145/73721.73740

  32. Schaerf, A.: On the complexity of the instance checking problem in concept languages with existential quantification. J. Intell. Inf. Syst. 2, 265–278 (1993)

    Article  Google Scholar 

  33. Ullman, J.D., Gelder, A.V.: Parallel complexity of logical query programs. Algorithmica 3, 5–42 (1988). https://doi.org/10.1007/BF01762108

    Article  MathSciNet  MATH  Google Scholar 

  34. Vardi, M.Y.: Decidability and undecidability results for boundedness of linear recursive queries. In: Edmondson-Yurkanan, C., Yannakakis, M. (eds.) Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Austin, Texas, USA, 21–23 March 1988, pp. 341–351. ACM (1988). http://doi.acm.org/10.1145/308386.308470

  35. Xiao, G., et al.: Ontology-based data access: a survey. In: Lang, J. (ed.) Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, Stockholm, Sweden, 13–19 July 2018, pp. 5511–5519. ijcai.org (2018). https://doi.org/10.24963/ijcai.2018/777

  36. Zhang, W., Yu, C.T., Troy, D.: Necessary and sufficient conditions to linearize double recursive programs in logic databases. ACM Trans. Database Syst. 15(3), 459–482 (1990). https://doi.org/10.1145/88636.89237

    Article  Google Scholar 

  37. Zhuk, D.: A proof of CSP dichotomy conjecture. In: Umans, C. (ed.) 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, 15–17 October 2017, pp. 331–342. IEEE Computer Society (2017). https://doi.org/10.1109/FOCS.2017.38

Download references

Acknowledgements

The work of O. Gerasimova and M. Zakharyaschev was carried out at the National Research University Higher School of Economics and supported by the Russian Science Foundation under grant 17-11-01294. We are grateful to Peter Jeavons and Standa Živný for helpful discussions of Polyanna and arc consistency.

Author information

Authors and Affiliations

  1. National Research University Higher School of Economics, Moscow, Russia

    Olga Gerasimova

  2. University of Oxford, Oxford, UK

    Stanislav Kikot

  3. Birkbeck, University of London, London, UK

    Michael Zakharyaschev

Authors
  1. Olga Gerasimova
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Stanislav Kikot
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Michael Zakharyaschev
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Olga Gerasimova .

Editor information

Editors and Affiliations

  1. University of Bremen, Bremen, Germany

    Carsten Lutz

  2. University of Manchester, Manchester, UK

    Uli Sattler

  3. University of Iowa, Iowa City, IA, USA

    Cesare Tinelli

  4. TU Dresden, Dresden, Germany

    Anni-Yasmin Turhan

  5. University of Liverpool, Liverpool, UK

    Frank Wolter

Rights and permissions

Reprints and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this chapter

Check for updates. Verify currency and authenticity via CrossMark

Cite this chapter

Gerasimova, O., Kikot, S., Zakharyaschev, M. (2019). Checking the Data Complexity of Ontology-Mediated Queries: A Case Study with Non-uniform CSPs and Polyanna. In: Lutz, C., Sattler, U., Tinelli, C., Turhan, AY., Wolter, F. (eds) Description Logic, Theory Combination, and All That. Lecture Notes in Computer Science(), vol 11560. Springer, Cham. https://doi.org/10.1007/978-3-030-22102-7_15

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-22102-7_15

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-22101-0

  • Online ISBN: 978-3-030-22102-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation