{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T23:50:10Z","timestamp":1649116210391},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2019,6,8]],"date-time":"2019-06-08T00:00:00Z","timestamp":1559952000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,6,8]],"date-time":"2019-06-08T00:00:00Z","timestamp":1559952000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2019,10]]},"DOI":"10.1007\/s10472-019-09639-5","type":"journal-article","created":{"date-parts":[[2019,6,8]],"date-time":"2019-06-08T05:05:35Z","timestamp":1559970335000},"page":"157-184","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A framework for comparing query languages in their ability to express boolean queries"],"prefix":"10.1007","volume":"87","author":[{"given":"Dimitri","family":"Surinx","sequence":"first","affiliation":[]},{"given":"Jan","family":"Van den Bussche","sequence":"additional","affiliation":[]},{"given":"Dirk","family":"Van Gucht","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,6,8]]},"reference":[{"key":"9639_CR1","unstructured":"Abiteboul, S., Hull, R., Vianu, V.: Foundations of databases. Addison-Wesley, Reading (1995)"},{"issue":"4","key":"9639_CR2","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1145\/2809784","volume":"40","author":"T Ameloot","year":"2016","unstructured":"Ameloot, T., Ketsman, B., Neven, F., Zinn, D.: Weaker forms of monotonicity for declarative networking: A more fine-grained answer to the CALM-conjecture. ACM Trans. Database Syst. 40(4), 21 (2016)","journal-title":"ACM Trans. Database Syst."},{"key":"9639_CR3","unstructured":"Angles, R., Barcel\u00f3, P., Rios, G.: A practical query language for graph DBs. In: L. Bravo, M. Lenzerini (eds.) Proceedings 7th Alberto Mendelzon International Workshop on Foundations of Data Management, CEUR Workshop Proceedings, vol. 1087 (2013)"},{"issue":"1","key":"9639_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1322432.1322433","volume":"40","author":"R Angles","year":"2008","unstructured":"Angles, R., Gutierrez, C.: Survey of graph database models. ACM Comput. Surv. 40(1), 1 (2008)","journal-title":"ACM Comput. Surv."},{"key":"9639_CR5","doi-asserted-by":"crossref","unstructured":"Badia, A.: Quantifiers in action: Generalized quantification in query, Logical and Natural Languages, Advances in Database Systems, vol. 37 Springer (2009)","DOI":"10.1007\/978-0-387-09564-6_4"},{"key":"9639_CR6","unstructured":"Barcel\u00f3, P.: Querying graph databases. In: Proceedings 32st ACM symposium on principles of databases, pp. 175\u2013188. ACM (2013)"},{"issue":"2","key":"9639_CR7","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/BF00350139","volume":"4","author":"J Barwise","year":"1981","unstructured":"Barwise, J., Cooper, R.: Generalized quantifiers and natural language. Linguistics and Philosophy 4(2), 159\u2013219 (1981)","journal-title":"Linguistics and Philosophy"},{"issue":"4","key":"9639_CR8","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1145\/1634.1636","volume":"31","author":"C Beeri","year":"1984","unstructured":"Beeri, C., Vardi, M.: A proof procedure for data dependencies. J. ACM 31 (4), 718\u2013741 (1984)","journal-title":"J. ACM"},{"key":"9639_CR9","doi-asserted-by":"crossref","unstructured":"Van den Bussche, J.: Applications of Alfred Tarski\u2019s ideas in database theory. In: Fribourg, L. (ed.) Computer science logic, lecture notes in computer science, vol. 2142. Springer (2001)","DOI":"10.1007\/3-540-44802-0_2"},{"issue":"2","key":"9639_CR10","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1145\/1328854.1328858","volume":"36","author":"B ten Cate","year":"2007","unstructured":"ten Cate, B., Marx, M.: Navigational XPath: Calculus and algebra. SIGMOD Rec. 36(2), 19\u201326 (2007)","journal-title":"SIGMOD Rec."},{"key":"9639_CR11","doi-asserted-by":"crossref","unstructured":"Chandra, A., Merlin, P.: Optimal implementation of conjunctive queries in relational data bases. In: Proceedings 9th ACM symposium on the theory of computing, pp. 77\u201390. ACM (1977)","DOI":"10.1145\/800105.803397"},{"key":"9639_CR12","doi-asserted-by":"crossref","unstructured":"Cruz, I., Mendelzon, A., Wood, P.: A graphical query language supporting recursion. In: Dayal, U., Traiger, I. (eds.) Proceedings of the ACM SIGMOD 1987 annual conference, SIGMOD record, vol. 16:3, pp 323\u2013330. ACM Press (1987)","DOI":"10.1145\/38714.38749"},{"key":"9639_CR13","volume-title":"Finite model theory","author":"HD Ebbinghaus","year":"1999","unstructured":"Ebbinghaus, H. D., Flum, J.: Finite model theory, 2nd edn. Springer, Berlin (1999)","edition":"2"},{"key":"9639_CR14","doi-asserted-by":"crossref","unstructured":"Fletcher, G., Gyssens, M., Leinders, D., Van den Bussche, J., Van Gucht, D., Vansummeren, S., Wu, Y.: Relative expressive power of navigational querying on graphs. In: Proceedings 14th international conference on database theory (2011)","DOI":"10.1145\/1938551.1938578"},{"issue":"1\u20132","key":"9639_CR15","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/s10472-013-9346-x","volume":"73","author":"G Fletcher","year":"2015","unstructured":"Fletcher, G., Gyssens, M., Leinders, D., Van den Bussche, J., Van Gucht, D., Vansummeren, S., Wu, Y.: The impact of transitive closure on the expressiveness of navigational query languages on unlabeled graphs. Ann. Math. Artif. Intell. 73(1\u20132), 167\u2013203 (2015)","journal-title":"Ann. Math. Artif. Intell."},{"key":"9639_CR16","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1016\/j.ins.2014.11.031","volume":"298","author":"G Fletcher","year":"2015","unstructured":"Fletcher, G., Gyssens, M., Leinders, D., Surinx, D., Van den Bussche, J., Van Gucht, D., Vansummeren, S., Wu, Y.: Relative expressive power of navigational querying on graphs. Inform. Sci. 298, 390\u2013406 (2015)","journal-title":"Inform. Sci."},{"key":"9639_CR17","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001","volume-title":"Graphs and homomorphisms","author":"P Hell","year":"2004","unstructured":"Hell, P., Nesetril, J.: Graphs and homomorphisms. Oxford Lecture Series in Mathematics and Its Applications, OUP Oxford (2004). \n                    https:\/\/books.google.be\/books?id=bJXWV-qK7kYC"},{"issue":"3","key":"9639_CR18","doi-asserted-by":"publisher","first-page":"802","DOI":"10.2307\/2275786","volume":"61","author":"L Hella","year":"1996","unstructured":"Hella, L., Luosto, K., V\u00e4\u00e4n\u00e4nen, J.: The hierarchy theorem for generalized quantifiers. The Journal of Symbolic Logic 61(3), 802\u2013817 (1996)","journal-title":"The Journal of Symbolic Logic"},{"key":"9639_CR19","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/0022-0000(84)90077-1","volume":"28","author":"T Imielinski","year":"1984","unstructured":"Imielinski, T., Lipski, W.: The relational model of data and cylindric algebras. J. Comput. Syst. Sci. 28, 80\u2013102 (1984)","journal-title":"J. Comput. Syst. Sci."},{"key":"9639_CR20","unstructured":"Kolaitis, P.: On the expressive power of logics on finite models. In: Finite model theory and its applications, chap. 2. Springer (2007)"},{"key":"9639_CR21","doi-asserted-by":"crossref","unstructured":"Libkin, L.: Elements of finite model theory. Springer (2004)","DOI":"10.1007\/978-3-662-07003-1"},{"key":"9639_CR22","doi-asserted-by":"crossref","unstructured":"Libkin, L., Martens, W., Vrgo\u010d, D.: Quering graph databases with XPath. In: Proceedings 16th international conference on database theory. ACM (2013)","DOI":"10.1145\/2448496.2448513"},{"issue":"2","key":"9639_CR23","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/1083784.1083792","volume":"34","author":"M Marx","year":"2005","unstructured":"Marx, M., de Rijke, M.: Semantic characterizations of navigational XPath. SIGMOD Rec. 34(2), 41\u201346 (2005)","journal-title":"SIGMOD Rec."},{"issue":"4","key":"9639_CR24","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1145\/322217.322221","volume":"27","author":"Y Sagiv","year":"1980","unstructured":"Sagiv, Y., Yannakakis, M.: Equivalences among relational expressions with the union and difference operators. J. ACM 27(4), 633\u2013655 (1980)","journal-title":"J. ACM"},{"key":"9639_CR25","volume-title":"A framework for comparing query languages in their ability to express boolean queries","author":"D Surinx","year":"2017","unstructured":"Surinx, D.: A framework for comparing query languages in their ability to express boolean queries. Ph.D. thesis, Hasselt University (2017). \n                    http:\/\/dsurinx.be\/phd.pdf"},{"key":"9639_CR26","doi-asserted-by":"crossref","unstructured":"Surinx, D., Van den Bussche, J.: A monotone preservation result for boolean queries expressed as a containment of conjunctive queries. arXiv:\n                    1808.08822\n                    \n                   (2018)","DOI":"10.1016\/j.ipl.2019.06.001"},{"key":"9639_CR27","doi-asserted-by":"crossref","unstructured":"Surinx, D., Van den Bussche, J., Van Gucht, D.: The primitivity of operators in the algebra of binary relations under conjunctions of containments. In: Proceedings 32nd annual ACM\/IEEE symposium on logic in computer science. IEEE Computer Society Press (2017)","DOI":"10.1109\/LICS.2017.8005122"},{"key":"9639_CR28","doi-asserted-by":"crossref","unstructured":"Surinx, D., Van den Bussche, J., Van Gucht, D.: A framework for comparing query languages in their ability to express boolean queries. In: Ferrarotti, F., Woltran, S. (eds.) Proceedings of the 10th international symposium on foundations of information and knowledge systems, Lecture notes in computer science, vol. 10833, pp 360\u2013378. Springer (2018)","DOI":"10.1007\/978-3-319-90050-6_20"},{"issue":"5","key":"9639_CR29","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1093\/jigpal\/jzv028","volume":"23","author":"D Surinx","year":"2015","unstructured":"Surinx, D., Fletcher, G., Gyssens, M., Leinders, D., Van den Bussche, J., Van Gucht, D., Vansummeren, S., Wu, Y.: Relative expressive power of navigational querying on graphs using transitive closure. Log. J. IGPL 23(5), 759\u2013788 (2015)","journal-title":"Log. J. IGPL"},{"issue":"1","key":"9639_CR30","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1145\/2206869.2206879","volume":"41","author":"P Wood","year":"2012","unstructured":"Wood, P.: Query languages for graph databases. SIGMOD Rec. 41(1), 50\u201360 (2012)","journal-title":"SIGMOD Rec."}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-019-09639-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10472-019-09639-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-019-09639-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T23:19:04Z","timestamp":1591485544000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10472-019-09639-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,8]]},"references-count":30,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2019,10]]}},"alternative-id":["9639"],"URL":"https:\/\/doi.org\/10.1007\/s10472-019-09639-5","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"value":"1012-2443","type":"print"},{"value":"1573-7470","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,8]]},"assertion":[{"value":"8 June 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}