{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:35Z","timestamp":1740109415946,"version":"3.37.3"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,8,14]],"date-time":"2017-08-14T00:00:00Z","timestamp":1502668800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/J020214\/1","EP\/L012138\/1","EP\/N014359\/1"],"award-info":[{"award-number":["EP\/J020214\/1","EP\/L012138\/1","EP\/N014359\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,5]]},"DOI":"10.1007\/s00224-017-9802-9","type":"journal-article","created":{"date-parts":[[2017,8,14]],"date-time":"2017-08-14T07:02:04Z","timestamp":1502694124000},"page":"772-809","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Complexity and Expressive Power of Weakly Well-Designed SPARQL"],"prefix":"10.1007","volume":"62","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8712-2953","authenticated-orcid":false,"given":"Mark","family":"Kaminski","sequence":"first","affiliation":[]},{"given":"Egor V.","family":"Kostylev","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,8,14]]},"reference":[{"key":"9802_CR1","doi-asserted-by":"crossref","unstructured":"Ahmetaj, S., Fischl, W., Pichler, R., Simkus, M., Skritek, S.: Towards reconciling SPARQL and certain answers. In: Gangemi, A., Leonardi, S., Panconesi, A. (eds.) Proceedings of the 24th International Conference on World Wide Web, WWW 2015, pp. 23\u201333. ACM (2015)","DOI":"10.1145\/2736277.2741636"},{"key":"9802_CR2","doi-asserted-by":"crossref","unstructured":"Angles, R., Gutierrez, C.: The expressive power of SPARQL. In: Sheth, A.P., Staab, S., Dean, M., Paolucci, M., Maynard, D., Finin, T.W., Thirunarayan, K. (eds.) ISWC 2008, LNCS, vol. 5318, pp. 114\u2013129. Springer (2008)","DOI":"10.1007\/978-3-540-88564-1_8"},{"key":"9802_CR3","doi-asserted-by":"crossref","unstructured":"Arenas, M., Conca, S., P\u00e9rez, J.: Counting beyond a Yottabyte, or how SPARQL 1.1 property paths will prevent adoption of the standard. In: Mille, A., Gandon, F.L., Misselis, J., Rabinovich, M., Staab, S. (eds.) Proceedings of the 21st World Wide Web Conference, WWW 2012, pp. 629\u2013638. ACM (2012)","DOI":"10.1145\/2187836.2187922"},{"key":"9802_CR4","doi-asserted-by":"crossref","unstructured":"Arenas, M., Gottlob, G., Pieris, A.: Expressive languages for querying the semantic web. In: Hull, R., Grohe, M. (eds.) Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2014, pp. 14\u201326. ACM (2014)","DOI":"10.1145\/2594538.2594555"},{"key":"9802_CR5","doi-asserted-by":"crossref","unstructured":"Arenas, M., P\u0117rez, J.: Querying Semantic Web Data with SPARQL. In: Lenzerini, M., Schwentick, T. (eds.) Proceedings 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2011, pp. 305\u2013316. ACM (2011)","DOI":"10.1145\/1989284.1989312"},{"key":"9802_CR6","doi-asserted-by":"crossref","unstructured":"Arenas, M., Ugarte, M.: Designing a query language for RDF: marrying open and closed worlds. In: Milo, T., Tan, W. (eds.) Proceedings 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, pp. 225\u2013236. ACM (2016)","DOI":"10.1145\/2902251.2902298"},{"key":"9802_CR7","unstructured":"Arias Gallego, M., Fern\u00e1ndez, J.D., Mart\u00ednez-Prieto, M.A., de la Fuente, P.: An empirical study of real-world SPARQL queries Proceedings of the 1st International Workshop on Usage Analysis and the Web of Data, USEWOD 2011. arXiv: 1103.5043 (2011)"},{"key":"9802_CR8","doi-asserted-by":"crossref","unstructured":"Barcel\u00f3, P., Pichler, R., Skritek, S.: Efficient Evaluation and Approximation of Well-Designed Pattern Trees. In: Milo, T., Calvanese, D. (eds.) Proceedings of the 34th ACM Symposium on Principles of Database Systems, PODS 2015, pp. 131\u2013144. ACM (2015)","DOI":"10.1145\/2745754"},{"key":"9802_CR9","doi-asserted-by":"crossref","unstructured":"Bischof, S., Kr\u00f3tzsch, M., Polleres, A., Rudolph, S.: Schema-agnostic query rewriting in SPARQL 1.1. In: Mika, P., Tudorache, T., Bernstein, A., Welty, C., Knoblock, C.A., Vrandecic, D., Groth, P.T., Noy, N.F., Janowicz, K., Goble, C.A. (eds.) ISWC 2014, Part I, LNCS, vol. 8796, pp. 584\u2013600. Springer (2014)","DOI":"10.1007\/978-3-319-11964-9_37"},{"key":"9802_CR10","doi-asserted-by":"crossref","unstructured":"Buil Aranda, C., Arenas, M., Corcho, \u00d3., Simperl, E.P.B.: Semantics and optimization of the SPARQL 1.1 federation extension. In: Antoniou, G., Grobelnik, M., Parsia, B., Plexousakis, D., Leenheer, P.D., Pan, J.Z. (eds.) ESWC 2011, Part II, LNCS, vol. 6644, pp. 1\u201315. Springer (2011)","DOI":"10.1007\/978-3-642-21064-8_1"},{"key":"9802_CR11","doi-asserted-by":"crossref","unstructured":"Buil Aranda, C., Polleres, A., Umbrich, J., Knoblock, C.A., Vrandecic, D.: Strategies for executing federated queries in SPARQL 1.1. In: Mika, P., Tudorache, T., Bernstein, A., Welty, C., Groth, P.T., Noy, N.F., Janowicz, K., Goble, C.A. (eds.) ISWC 2014, Part II, LNCS, vol. 8797, pp. 390\u2013405. Springer (2014)","DOI":"10.1007\/978-3-319-11915-1_25"},{"key":"9802_CR12","doi-asserted-by":"crossref","unstructured":"Chekol, M.W., Euzenat, J., Genev\u00e8s, P., Laya\u00efda, N.: SPARQL query containment under RDFS entailment regime. In: Gramlich, B., Miller, D., Sattler, U. (eds.) IJCAR 2012, LNCS, vol. 7364, pp. 134\u2013148. Springer (2012)","DOI":"10.1007\/978-3-642-31365-3_13"},{"key":"9802_CR13","doi-asserted-by":"crossref","unstructured":"Chekol, M.W., Euzenat, J., Genev\u00e8s, P., Laya\u00efda, N.: SPARQL query containment under SHI Axioms. In: Hoffmann, J., Selman, B. (eds.) Proceedings of the 26th AAAI Conference on Artificial Intelligence, AAAI 2012, pp. 10\u201316. AAAI Press (2012)","DOI":"10.1609\/aaai.v26i1.8108"},{"key":"9802_CR14","unstructured":"Cyganiak, R., Wood, D., Lanthaler, M.: RDF 1.1 concepts and abstract syntax. W3C recommendation, W3C. http:\/\/www.w3.org\/TR\/rdf11-concepts\/ (2014)"},{"issue":"1","key":"9802_CR15","doi-asserted-by":"crossref","first-page":"7:1","DOI":"10.1145\/2810037","volume":"63","author":"F Geerts","year":"2016","unstructured":"Geerts, F., Unger, T., Karvounarakis, G., Fundulaki, I., Christophides, V.: Algebraic structures for capturing the provenance of SPARQL queries. J. ACM 63(1), 7:1\u20137:63 (2016)","journal-title":"J. ACM"},{"key":"9802_CR16","doi-asserted-by":"crossref","unstructured":"Halpin, H., Cheney, J.: Dynamic Provenance for SPARQL Updates. In: Mika, P., Tudorache, T., Bernstein, A., Welty, C., Knoblock, C.A., Vrandecic, D., Groth, P.T., Noy, N.F., Janowicz, K., Goble, C.A. (eds.) ISWC 2014, Part I, LNCS, vol. 8796, pp. 425\u2013440. Springer (2014)","DOI":"10.1007\/978-3-319-11964-9_27"},{"key":"9802_CR17","unstructured":"Harris, S., Seaborne, A.: SPARQL 1.1 query language. W3C recommendation, W3C. http:\/\/www.w3.org\/TR\/sparql11-query\/ (2013)"},{"key":"9802_CR18","unstructured":"Hayes, P.J., Patel-Schneider, P.F.: RDF 1.1 semantics. W3C recommendation, W3C. http:\/\/www.w3.org\/TR\/rdf11-mt\/ (2014)"},{"key":"9802_CR19","unstructured":"Kaminski, M., Kostylev, E.V.: Beyond well-designed SPARQL. In: Martens, W., Zeume, T. (eds.) Proceedings of the 19th International Conference on Database Theory, ICDT 2016, LIPIcs, vol. 48, pp. 5:1\u20135:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016)"},{"key":"9802_CR20","doi-asserted-by":"crossref","unstructured":"Kaminski, M., Kostylev, E.V., Cuenca Grau, B.: Semantics and expressive power of subqueries and aggregates in SPARQL 1.1. In: Bourdeau, J., Hendler, J., Nkambou, R., Horrocks, I., Zhao, B.Y. (eds.) Proceedings of the 25th International Conference on World Wide Web, WWW 2016, pp. 227\u2013238. ACM (2016)","DOI":"10.1145\/2872427.2883022"},{"key":"9802_CR21","unstructured":"Kontchakov, R., Kostylev, E.V.: On expressibility of non-monotone operators in SPARQL. In: Baral, C., Delgrande, J.P., Wolter, F. (eds.) Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning, KR 2016, pp. 369\u2013379. AAAI Press (2016)"},{"key":"9802_CR22","doi-asserted-by":"crossref","unstructured":"Kontchakov, R., Rezk, M., Rodriguez-muro, M., Xiao, G., Zakharyaschev, M.: Answering SPARQL queries over databases under OWL 2 QL entailment regime. In: Mika, P., Tudorache, T., Bernstein, A., Welty, C., Knoblock, C.A., Vrandecic, D., Groth, P.T., Noy, N.F., Janowicz, K., Goble, C. A. (eds.) ISWC 2014, Part I, LNCS, vol. 8796, pp. 552\u2013567. Springer (2014)","DOI":"10.1007\/978-3-319-11964-9_35"},{"key":"9802_CR23","doi-asserted-by":"crossref","unstructured":"Kostylev, E.V., Cuenca Grau, B.: On the semantics of SPARQL queries with optional matching under entailment regimes. In: Mika, P., Tudorache, T., Bernstein, A., Welty, C., Knoblock, C.A., Vrandecic, D., Groth, P.T., Noy, N.F., Janowicz, K., Goble, C.A. (eds.) ISWC 2014, Part II, LNCS, vol. 8797, pp. 374\u2013389. Springer (2014)","DOI":"10.1007\/978-3-319-11915-1_24"},{"key":"9802_CR24","doi-asserted-by":"crossref","unstructured":"Kostylev, E.V., Reutter, J.L., Romero, M., Vrgoc, D., Staab, S.: SPARQL with property paths. In: Arenas, M., Corcho, O\u0307., Simperl, E., Strohmaier, M., d\u2019Aquin, M., Srinivas, K., Groth, P.T., Dumontier, M., Heflin, J., Thirunarayan, K. (eds.) ISWC 2015, Part I, LNCS, vol. 9366, pp. 3\u201318. Springer (2015)","DOI":"10.1007\/978-3-319-25007-6_1"},{"key":"9802_CR25","unstructured":"Kostylev, E.V., Reutter, J.L., Ugarte, M.: CONSTRUCT Queries in SPARQL. In: Arenas, M., Ugarte, M. (eds.) Proceedings of the 18th International Conference on Database Theory, ICDT 2015, LIPIcs, vol. 31, pp. 212\u2013229. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2015)"},{"issue":"2","key":"9802_CR26","doi-asserted-by":"crossref","first-page":"167","DOI":"10.3233\/SW-140134","volume":"6","author":"J Lehmann","year":"2015","unstructured":"Lehmann, J., Isele, R., Jakob, M., Jentzsch, A., Kontokostas, D., Mendes, P.N., Hellmann, S., Morsey, M., van Kleef, P., Auer, S., Bizer, C.: DBpedia\u2014a large-scale, multilingual knowledge base extracted from Wikipedia. Semantic Web 6(2), 167\u2013195 (2015)","journal-title":"Semantic Web"},{"issue":"4","key":"9802_CR27","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1145\/2500130","volume":"38","author":"A Letelier","year":"2013","unstructured":"Letelier, A., P\u0117rez, J., Pichler, R., Skritek, S.: Static analysis and optimization of semantic web queries. ACM Trans. Database Syst. 38(4), 25 (2013)","journal-title":"ACM Trans. Database Syst."},{"key":"9802_CR28","doi-asserted-by":"crossref","unstructured":"Losemann, K., Martens, W.: The complexity of evaluating path expressions in SPARQL. In: Benedikt, M., Kr\u00f3tzsch, M., Lenzerini, M. (eds.) Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2012, pp. 101\u2013112. ACM (2012)","DOI":"10.1145\/2213556.2213573"},{"key":"9802_CR29","doi-asserted-by":"publisher","unstructured":"Luczak-R\u00f6sch, M., Aljaloud, S., Berendt, B., Hollink, L.: USEWOD 2016 research dataset. doi: 10.5258\/SOTON\/385344 (2016)","DOI":"10.5258\/SOTON\/385344"},{"key":"9802_CR30","doi-asserted-by":"publisher","unstructured":"Luczak-R\u00f6sch, M., Berendt, B., Hollink, L.: USEWOD 2015 research dataset. doi: 10.5258\/SOTON\/379407 (2015)","DOI":"10.5258\/SOTON\/379407"},{"key":"9802_CR31","unstructured":"Manola, F., Miller, E., McBride, B.: RDF 1.1 primer. W3C working group note, W3C. http:\/\/www.w3.org\/TR\/rdf11-primer\/ (2014)"},{"key":"9802_CR32","unstructured":"P\u00e9rez, J., Arenas, M., Gutierrez, C.: Semantics and complexity of SPARQL. In: Cruz, I.F., Decker, S., Allemang, D., Preist, C., Schwabe, D., Mika, P., Uschold, M., Aroyo, L. (eds.) ISWC 2006, LNCS, vol. 4273, pp. 30\u201343. Springer (2006)"},{"issue":"3","key":"9802_CR33","doi-asserted-by":"crossref","first-page":"16:1","DOI":"10.1145\/1567274.1567278","volume":"34","author":"J P\u00e9rez","year":"2009","unstructured":"P\u00e9rez, J., Arenas, M., Gutierrez, C.: Semantics and complexity of SPARQL. ACM Trans. Database Syst. 34(3), 16:1\u201316:45 (2009)","journal-title":"ACM Trans. Database Syst."},{"key":"9802_CR34","doi-asserted-by":"crossref","unstructured":"Picalausa, F., Vansummeren, S.: What are real SPARQL queries like? In: Virgilio, R.D., Giunchiglia, F., Tanca, L. (eds.) Proceedings of the 3rd International Workshop on Semantic Web Information Management, SWIM 2011, pp. 7:1\u20137:6. ACM (2011)","DOI":"10.1145\/1999299.1999306"},{"key":"9802_CR35","doi-asserted-by":"crossref","unstructured":"Pichler, R., Skritek, S.: Containment and equivalence of well-designed SPARQL. In: Hull, R., Grohe, M. (eds.) Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2014, pp. 39\u201350. ACM (2014)","DOI":"10.1145\/2594538.2594542"},{"issue":"1\u20132","key":"9802_CR36","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1080\/11663081.2013.798992","volume":"23","author":"A Polleres","year":"2013","unstructured":"Polleres, A., Wallner, J.P.: On the relation between SPARQL 1.1 and answer set programming. J. Appl. Non-Classical Log. 23(1\u20132), 159\u2013212 (2013)","journal-title":"J. Appl. Non-Classical Log."},{"key":"9802_CR37","unstructured":"Prud\u2019hommeaux, E., Seaborne, A.: SPARQL query language for RDF. W3C recommendation, W3C. http:\/\/www.w3.org\/TR\/rdf-sparql-query\/ (2008)"},{"key":"9802_CR38","doi-asserted-by":"crossref","unstructured":"Schmidt, M., Meier, M., Lausen, G.: Foundations of SPARQL query optimization. In: Segoufin, L. (ed.) Proceedings of the 13Th International Conference on Database Theory, ICDT 2010, pp. 4\u201333. ACM (2010)","DOI":"10.1145\/1804669.1804675"},{"issue":"11","key":"9802_CR39","doi-asserted-by":"crossref","first-page":"2841","DOI":"10.1093\/comjnl\/bxu128","volume":"58","author":"X Zhang","year":"2015","unstructured":"Zhang, X., Van den Bussche, J.: On the power of SPARQL in expressing navigational queries. Comput. J. 58(11), 2841\u20132851 (2015)","journal-title":"Comput. J."},{"issue":"9","key":"9802_CR40","doi-asserted-by":"crossref","first-page":"480","DOI":"10.1016\/j.ipl.2014.03.014","volume":"114","author":"X Zhang","year":"2014","unstructured":"Zhang, X., Van den bussche, J.: On the primitivity of operators in SPARQL. Inf. Process. Lett. 114(9), 480\u2013485 (2014)","journal-title":"Inf. Process. Lett."},{"key":"9802_CR41","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1613\/jair.5028","volume":"56","author":"X Zhang","year":"2016","unstructured":"Zhang, X., Van den bussche, J., Picalausa, F.: On the satisfiability problem for SPARQL patterns. J. Artif. Intell. Res. (JAIR) 56, 403\u2013428 (2016)","journal-title":"J. Artif. Intell. Res. (JAIR)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9802-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9802-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9802-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T04:27:39Z","timestamp":1659328059000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9802-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,14]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,5]]}},"alternative-id":["9802"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9802-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2017,8,14]]}}}