STypeS: Nonrecursive Datalog Rewriter for Linear TGDs and Conjunctive Queries | SpringerLink
Skip to main content
Springer Nature Link
Log in

STypeS: Nonrecursive Datalog Rewriter for Linear TGDs and Conjunctive Queries

  • Conference paper
  • First Online:
On the Move to Meaningful Internet Systems. OTM 2018 Conferences (OTM 2018)

Part of the book series: Lecture Notes in Computer Science ((LNPSE,volume 11230))

  • 2576 Accesses

Abstract

We present STypeS, a system that rewrites ontology-mediated queries with linear tuple-generating dependencies and conjunctive queries to equivalent nonrecursive datalog (NDL) queries. The main feature of STypeS is that it produces polynomial-size rewritings whenever the treewidth of the input conjunctive queries and the size of the chases for the ontology atoms as well as their arity are bounded; moreover, the rewritings can be constructed and executed in LogCFL, indicating high parallelisability in theory. We show experimentally that Apache Flink on a cluster of machines with 20 virtual CPUs is indeed able to parallelise execution of a series of NDL-rewritings constructed by STypeS, with the time decreasing proportionally to the number of CPUs available.

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://github.com/mabseher/htd.

  2. 2.

    http://graphik-team.github.io/graal.

References

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

    MATH  Google Scholar 

  2. Abseher, M., Musliu, N., Woltran, S.: htd – a free, open-source framework for (customized) tree decompositions and beyond. In: Salvagnin, D., Lombardi, M. (eds.) CPAIOR 2017. LNCS, vol. 10335, pp. 376–386. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59776-8_30

    Chapter  MATH  Google Scholar 

  3. Artale, A., Calvanese, D., Kontchakov, R., Zakharyaschev, M.: The DL-Lite family and relations. J. Artif. Intell. Res. (JAIR) 36, 1–69 (2009). https://doi.org/10.1613/jair.2820

    Article  MathSciNet  MATH  Google Scholar 

  4. Baget, J.-F., Leclère, M., Mugnier, M.-L., Rocher, S., Sipieter, C.: Graal: a toolkit for query answering with existential rules. In: Bassiliades, N., Gottlob, G., Sadri, F., Paschke, A., Roman, D. (eds.) RuleML 2015. LNCS, vol. 9202, pp. 328–344. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21542-6_21

    Chapter  Google Scholar 

  5. Baget, J.F., Leclère, M., Mugnier, M.L., Salvat, E.: Extending decidable cases for rules with existential variables. In: Proceedings of the 21th International Joint Conference on Artificial Intelligence (IJCAI 2009), pp. 677–682. IJCAI (2009)

    Google Scholar 

  6. Baget, J.F., Leclère, M., Mugnier, M.L., Salvat, E.: On rules with existential variables: walking the decidability line. Artif. Intell. 175(9–10), 1620–1654 (2011). https://doi.org/10.1016/j.artint.2011.03.002

    Article  MathSciNet  MATH  Google Scholar 

  7. Bienvenu, M., Kikot, S., Kontchakov, R., Podolskii, V., Zakharyaschev, M.: Ontology-mediated queries: combined complexity and succinctness of rewritings via circuit complexity. J. ACM 65(5), 28:1–28:51 (2018). https://doi.org/10.1145/3191832

    Article  MathSciNet  Google Scholar 

  8. Bienvenu, M., Kikot, S., Kontchakov, R., Podolskii, V.V., Ryzhikov, V., Zakharyaschev, M.: The complexity of ontology-based data access with OWL 2 QL and bounded treewidth queries. In: Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017, pp. 201–216. ACM (2017). https://doi.org/10.1145/3034786.3034791

  9. Bienvenu, M., Kikot, S., Kontchakov, R., Ryzhikov, V., Zakharyaschev, M.: Optimal nonrecursive datalog rewritings of linear TGDs and bounded (hyper)tree-width queries. In: Proceedings of the 30th International Workshop on Description Logics, DL 2017. CEUR Workshop Proceedings, vol. 1879. CEUR-WS.org (2017)

    Google Scholar 

  10. Boguslavsky, I., Dikonov, V., Iomdin, L., Lazursky, A., Sizov, V., Timoshenko, S.: Semantic analysis and question answering: a system under development. In: Computational Linguistics and Intellectual Technologies (Papers from the Annual International Conference Dialogue 2015), vol. 1, pp. 62–79. RSUH (2015)

    Google Scholar 

  11. Calì, A., Gottlob, G., Lukasiewicz, T.: A general datalog-based framework for tractable query answering over ontologies. J. Web Semant. 14, 57–83 (2012). https://doi.org/10.1016/j.websem.2012.03.001

    Article  Google Scholar 

  12. Calì, A., Gottlob, G., Pieris, A.: Advanced processing for ontological queries. PVLDB 3(1), 554–565 (2010). https://doi.org/10.14778/1920841.1920912

    Article  Google Scholar 

  13. Calì, A., Gottlob, G., Pieris, A.: Towards more expressive ontology languages: the query answering problem. Artif. Intell. 193, 87–128 (2012). https://doi.org/10.1016/j.artint.2012.08.002

    Article  MathSciNet  MATH  Google Scholar 

  14. Carbone, P., Katsifodimos, A., Ewen, S., Markl, V., Haridi, S., Tzoumas, K.: Apache flink™: stream and batch processing in a single engine. IEEE Data Eng. Bull. 38(4), 28–38 (2015)

    Google Scholar 

  15. Chekuri, C., Rajaraman, A.: Conjunctive query containment revisited. Theor. Comput. Sci. 239(2), 211–229 (2000). https://doi.org/10.1016/S0304-3975(99)00220-0

    Article  MathSciNet  MATH  Google Scholar 

  16. Chortaras, A., Trivela, D., Stamou, G.: Optimized query rewriting for OWL 2 QL. In: Bjørner, N., Sofronie-Stokkermans, V. (eds.) CADE 2011. LNCS (LNAI), vol. 6803, pp. 192–206. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22438-6_16

    Chapter  Google Scholar 

  17. Eiter, T., Ortiz, M., Šimkus, M., Tran, T.K., Xiao, G.: Query rewriting for Horn-SHIQ plus rules. In: Proceedings of the 26th AAAI Conference on Artificial Intelligence, AAAI 2012, pp. 726–733. AAAI Press (2012)

    Google Scholar 

  18. Fagin, R., Kolaitis, P.G., Miller, R.J., Popa, L.: Data exchange: semantics and query answering. Theor. Comput. Sci. 336(1), 89–124 (2005). https://doi.org/10.1016/j.tcs.2004.10.033

    Article  MathSciNet  MATH  Google Scholar 

  19. Gottlob, G., Kikot, S., Kontchakov, R., Podolskii, V.V., Schwentick, T., Zakharyaschev, M.: The price of query rewriting in ontology-based data access. Artif. Intell. 213, 42–59 (2014). https://doi.org/10.1016/j.artint.2014.04.004

    Article  MathSciNet  MATH  Google Scholar 

  20. Gottlob, G., Leone, N., Scarcello, F.: Computing LOGCFL certificates. In: Wiedermann, J., van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, pp. 361–371. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48523-6_33

    Chapter  Google Scholar 

  21. Kikot, S., Kontchakov, R., Podolskii, V., Zakharyaschev, M.: Exponential lower bounds and separation for query rewriting. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012 Part II. LNCS, vol. 7392, pp. 263–274. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31585-5_26

    Chapter  MATH  Google Scholar 

  22. Lenzerini, M.: Data integration: a theoretical perspective. In: Proceedings of the 21st ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS 2002, pp. 233–246. ACM (2002). https://doi.org/10.1145/543613.543644

  23. Motik, B., Cuenca Grau, B., Horrocks, I., Wu, Z., Fokoue, A., Lutz, C.: OWL 2 Web Ontology Language Profiles. W3C Recommendation (2012). http://www.w3.org/TR/owl2-profiles

  24. Poggi, A., Lembo, D., Calvanese, D., De Giacomo, G., Lenzerini, M., Rosati, R.: Linking data to ontologies. J. Data Semant. 10, 133–173 (2008). https://doi.org/10.1007/978-3-540-77688-8_5

    Article  MATH  Google Scholar 

  25. Rosati, R., Almatelli, A.: Improving query answering over DL-Lite ontologies. In: Proceedings of the 12th International Conference on Principles of Knowledge Representation and Reasoning, KR 2010, pp. 290–300. AAAI Press (2010)

    Google Scholar 

  26. Ruzzo, W.L.: Tree-size bounded alternation. J. Comput. Syst. Sci. 21(2), 218–235 (1980). https://doi.org/10.1016/0022-0000(80)90036-7

    Article  MathSciNet  MATH  Google Scholar 

  27. Rygaev, I.: Rule-based reasoning in semantic text analysis. In: Proceedings of the Doctoral Consortium, Challenge, Industry Track, Tutorials and Posters @ RuleML+RR 2017. CEUR Workshop Proceedings, vol. 1875. CEUR-WS.org (2017)

    Google Scholar 

  28. Xiao, G., Calvanese, D., Kontchakov, R., Lembo, D., Poggi, A., Rosati, R., Zakharyaschev, M.: Ontology-based data access: a survey. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI-ECAI 2018, pp. 5511–5519. IJCAI/AAAI (2018). https://doi.org/10.24963/ijcai.2018/777

  29. Yannakakis, M.: Algorithms for acyclic database schemes. In: Proceedings of the 7th International Conference on Very Large Data Bases, VLDB81, pp. 82–94. IEEE Computer Society (1981)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Oxford, Oxford, UK

    Stanislav Kikot

  2. Birkbeck, University of London, London, UK

    Roman Kontchakov, Salvatore Rapisarda & Michael Zakharyaschev

Authors
  1. Stanislav Kikot
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Roman Kontchakov
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Salvatore Rapisarda
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Michael Zakharyaschev
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Roman Kontchakov .

Editor information

Editors and Affiliations

  1. CNRS, University of Lorraine, Vandoeuvre-les-Nancy, France

    Hervé Panetto

  2. Trinity College Dublin, Dublin, Ireland

    Christophe Debruyne

  3. Luxembourg Institute of Science and Technology, Esch-sur-Alzette, Luxembourg

    Henderik A. Proper

  4. Università degli Studi di Milano, Crema, Italy

    Claudio Agostino Ardagna

  5. SINTEF and University of Oslo, Oslo, Norway

    Dumitru Roman

  6. TU Graz, Graz, Austria

    Robert Meersman

Rights and permissions

Reprints and permissions

Copyright information

© 2018 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Kikot, S., Kontchakov, R., Rapisarda, S., Zakharyaschev, M. (2018). STypeS: Nonrecursive Datalog Rewriter for Linear TGDs and Conjunctive Queries. In: Panetto, H., Debruyne, C., Proper, H., Ardagna, C., Roman, D., Meersman, R. (eds) On the Move to Meaningful Internet Systems. OTM 2018 Conferences. OTM 2018. Lecture Notes in Computer Science(), vol 11230. Springer, Cham. https://doi.org/10.1007/978-3-030-02671-4_27

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-02671-4_27

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-02670-7

  • Online ISBN: 978-3-030-02671-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation