{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T10:48:49Z","timestamp":1775213329813,"version":"3.50.1"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032088864","type":"print"},{"value":"9783032088871","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,10,25]],"date-time":"2025-10-25T00:00:00Z","timestamp":1761350400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,10,25]],"date-time":"2025-10-25T00:00:00Z","timestamp":1761350400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-08887-1_5","type":"book-chapter","created":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T11:28:27Z","timestamp":1761305307000},"page":"72-89","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["When Does Na\u00efve Evaluation Work for\u00a0Datalog?"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-3113-0571","authenticated-orcid":false,"given":"Heng","family":"Liu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0751-4031","authenticated-orcid":false,"given":"Eugenia","family":"Ternovska","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,10,25]]},"reference":[{"key":"5_CR1","doi-asserted-by":"publisher","unstructured":"Abiteboul, S., Duschka, O.M.: Complexity of answering queries using materialized views. In: Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 254\u2013263. PODS \u201998, Association for Computing Machinery, New York, NY, USA (1998). https:\/\/doi.org\/10.1145\/275487.275516","DOI":"10.1145\/275487.275516"},{"key":"5_CR2","unstructured":"Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases (1995)"},{"issue":"1","key":"5_CR3","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/0304-3975(51)90007-2","volume":"78","author":"S Abiteboul","year":"1991","unstructured":"Abiteboul, S., Kanellakis, P., Grahne, G.: On the representation and querying of sets of possible worlds. Theor. Comput. Sci. 78(1), 159\u2013187 (1991). https:\/\/doi.org\/10.1016\/0304-3975(51)90007-2","journal-title":"Theor. Comput. Sci."},{"key":"5_CR4","unstructured":"Angles, R., et al.: The LDBC social network benchmark. CoRR abs\/2001.02299 (2020)"},{"key":"5_CR5","doi-asserted-by":"publisher","unstructured":"Arenas, M., Barcel\u00f3, P., Reutter, J.: Query languages for data exchange: beyond unions of conjunctive queries. In: Proceedings of the 12th International Conference on Database Theory, pp. 73\u201383. ICDT \u201909, ACM, New York, NY, USA (2009). https:\/\/doi.org\/10.1145\/1514894.1514904","DOI":"10.1145\/1514894.1514904"},{"key":"5_CR6","doi-asserted-by":"publisher","unstructured":"Bruijn, J., Heymans, S.: Complexity of the stable model semantics for queries on incomplete databases. In: Proceedings of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning, pp. 101\u2013114. LPNMR \u201909, Springer-Verlag, Berlin, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-04238-6_11","DOI":"10.1007\/978-3-642-04238-6_11"},{"issue":"1","key":"5_CR7","first-page":"115","volume":"48","author":"A Cal\u00ec","year":"2013","unstructured":"Cal\u00ec, A., Gottlob, G., Kifer, M.: Taming the infinite chase: query answering under expressive relational constraints. J. Artif. Int. Res. 48(1), 115\u2013174 (2013)","journal-title":"J. Artif. Int. Res."},{"key":"5_CR8","doi-asserted-by":"publisher","unstructured":"Cal\u00ec, A., Gottlob, G., Lukasiewicz, T.: A general datalog-based framework for tractable query answering over ontologies. J. Web Semant. 14, 57\u201383 (2012). https:\/\/doi.org\/10.1016\/j.websem.2012.03.001, special Issue on Dealing with the Messiness of the Web of Data","DOI":"10.1016\/j.websem.2012.03.001"},{"issue":"4","key":"5_CR9","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1145\/320107.320109","volume":"4","author":"EF Codd","year":"1979","unstructured":"Codd, E.F.: Extending the database relational model to capture more meaning. ACM Trans. Database Syst. 4(4), 397\u2013434 (1979). https:\/\/doi.org\/10.1145\/320107.320109","journal-title":"ACM Trans. Database Syst."},{"key":"5_CR10","doi-asserted-by":"publisher","unstructured":"Console, M., Guagliardo, P., Libkin, L., Toussaint, E.: Coping with incomplete data: recent advances. In: Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pp. 33\u201347. PODS\u201920, Association for Computing Machinery, New York, NY, USA (2020). https:\/\/doi.org\/10.1145\/3375395.3387970","DOI":"10.1145\/3375395.3387970"},{"key":"5_CR11","doi-asserted-by":"publisher","unstructured":"Fagin, R., Kolaitis, P.G., Miller, R.J., Popa, L.: Data exchange: semantics and query answering. Theoret. Comput. Sci. 336(1), 89\u2013124 (2005). https:\/\/doi.org\/10.1016\/j.tcs.2004.10.033, database Theory","DOI":"10.1016\/j.tcs.2004.10.033"},{"key":"5_CR12","doi-asserted-by":"publisher","unstructured":"Feder, T., Vardi, M.: Homomorphism closed vs. existential positive. In: 18th Annual IEEE Symposium of Logic in Computer Science, 2003. Proceedings, pp. 311\u2013320 (2003). https:\/\/doi.org\/10.1109\/LICS.2003.1210071","DOI":"10.1109\/LICS.2003.1210071"},{"key":"5_CR13","doi-asserted-by":"publisher","unstructured":"Gheerbrant, A., Libkin, L., Sirangelo, C.: When is naive evaluation possible? In: Proceedings of the 32Nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pp. 75\u201386. PODS \u201913, ACM, New York, NY, USA (2013). https:\/\/doi.org\/10.1145\/2463664.2463674","DOI":"10.1145\/2463664.2463674"},{"key":"5_CR14","doi-asserted-by":"publisher","unstructured":"Gheerbrant, A., Libkin, L., Sirangelo, C.: Na\u00efve evaluation of queries over incomplete databases. ACM Trans. Database Syst. 39(4) (2015). https:\/\/doi.org\/10.1145\/2691190.2691194","DOI":"10.1145\/2691190.2691194"},{"key":"5_CR15","unstructured":"Gottlob, G., Lukasiewicz, T., Pieris, A.: Datalog+\/-: questions and answers. In: Proceedings of the Fourteenth International Conference on Principles of Knowledge Representation and Reasoning, pp. 682\u2013685. KR\u201914, AAAI Press (2014)"},{"issue":"5","key":"5_CR16","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/0020-0190(77)90013-8","volume":"6","author":"J Grant","year":"1977","unstructured":"Grant, J.: Null values in a relational data base. Inf. Process. Lett. 6(5), 156\u2013157 (1977). https:\/\/doi.org\/10.1016\/0020-0190(77)90013-8","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"5_CR17","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1145\/1634.1886","volume":"31","author":"T Imieli\u0144ski","year":"1984","unstructured":"Imieli\u0144ski, T., Lipski, W.: Incomplete information in relational databases. J. ACM 31(4), 761\u2013791 (1984). https:\/\/doi.org\/10.1145\/1634.1886","journal-title":"J. ACM"},{"key":"5_CR18","doi-asserted-by":"publisher","unstructured":"Ketsman, B., Koch, C.: Datalog with negation and monotonicity. International Conference on Database Theory (ICDT) (2020). https:\/\/doi.org\/10.5446\/46837","DOI":"10.5446\/46837"},{"key":"5_CR19","doi-asserted-by":"publisher","unstructured":"Kolaitis, P.G.: On the Expressive Power of Logics on Finite Models, pp. 27\u2013123. Springer Berlin Heidelberg, Berlin, Heidelberg (2007). https:\/\/doi.org\/10.1007\/3-540-68804-8_2","DOI":"10.1007\/3-540-68804-8_2"},{"key":"5_CR20","unstructured":"Libkin, L.: How to define certain answers. In: Proceedings of the 24th International Conference on Artificial Intelligence, pp. 4282\u20134288. IJCAI\u201915, AAAI Press (2015)"},{"issue":"3","key":"5_CR21","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1145\/320083.320088","volume":"4","author":"W Lipski","year":"1979","unstructured":"Lipski, W.: On semantic issues connected with incomplete information databases. ACM Trans. Database Syst. 4(3), 262\u2013296 (1979). https:\/\/doi.org\/10.1145\/320083.320088","journal-title":"ACM Trans. Database Syst."},{"issue":"4","key":"5_CR22","doi-asserted-by":"publisher","first-page":"1987","DOI":"10.1109\/TETC.2019.2952765","volume":"9","author":"F Mercorio","year":"2021","unstructured":"Mercorio, F., Mezzanzanica, M., Moscato, V., Picariello, A., Sperl\u00ed, G.: DICO: a graph-DB framework for community detection on big scholarly data. IEEE Trans. Emerg. Top. Comput. 9(4), 1987\u20132003 (2021). https:\/\/doi.org\/10.1109\/TETC.2019.2952765","journal-title":"IEEE Trans. Emerg. Top. Comput."},{"key":"5_CR23","doi-asserted-by":"publisher","unstructured":"Reiter, R.: On closed world databases. In: Webber, B.L., Nilsson, N.J. (eds.) Readings in Artificial Intelligence, pp. 119\u2013140. Morgan Kaufmann (1981). https:\/\/doi.org\/10.1016\/B978-0-934613-03-3.50014-3","DOI":"10.1016\/B978-0-934613-03-3.50014-3"},{"issue":"3","key":"5_CR24","doi-asserted-by":"publisher","first-page":"380","DOI":"10.2178\/bsl\/1182353894","volume":"8","author":"E Rosen","year":"2002","unstructured":"Rosen, E.: Some aspects of model theory and finite structures. Bull. Symbolic Logic 8(3), 380\u2013403 (2002). https:\/\/doi.org\/10.2178\/bsl\/1182353894","journal-title":"Bull. Symbolic Logic"},{"key":"5_CR25","doi-asserted-by":"publisher","unstructured":"Rosen, E., Weinstein, S.: Preservation theorems in finite model theory. In: Leivant, D. (ed.) Logic and Computational Complexity, pp. 480\u2013502. Springer Berlin Heidelberg, Berlin, Heidelberg (1995). https:\/\/doi.org\/10.1007\/3-540-60178-3_99","DOI":"10.1007\/3-540-60178-3_99"},{"key":"5_CR26","doi-asserted-by":"publisher","unstructured":"Rossman, B.: Homomorphism preservation theorems. J. ACM 55(3) (2008). https:\/\/doi.org\/10.1145\/1379759.1379763","DOI":"10.1145\/1379759.1379763"},{"key":"5_CR27","unstructured":"Rudolph, S., Thomazo, M.: Expressivity of datalog variants \u2013 completing the picture. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence. New-York, United States (2016)"},{"issue":"9","key":"5_CR28","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1145\/3434642","volume":"64","author":"S Sakr","year":"2021","unstructured":"Sakr, S., et al.: The future is big graphs: a community view on graph processing systems. Commun. ACM 64(9), 62\u201371 (2021). https:\/\/doi.org\/10.1145\/3434642","journal-title":"Commun. ACM"},{"key":"5_CR29","doi-asserted-by":"publisher","unstructured":"Srivastava, S., Singh, A.K.: Fraud detection in the distributed graph database. Cluster Comput. 26(1), 515\u2013537 (2022). https:\/\/doi.org\/10.1007\/s10586-022-03540-3","DOI":"10.1007\/s10586-022-03540-3"},{"key":"5_CR30","doi-asserted-by":"publisher","unstructured":"Vardi, M.Y.: The complexity of relational query languages (extended abstract). In: Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pp. 137\u2013146. STOC \u201982, Association for Computing Machinery, New York, NY, USA (1982). https:\/\/doi.org\/10.1145\/800070.802186","DOI":"10.1145\/800070.802186"}],"container-title":["Lecture Notes in Computer Science","Rules and Reasoning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-08887-1_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T09:56:41Z","timestamp":1775210201000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-08887-1_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,25]]},"ISBN":["9783032088864","9783032088871"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-08887-1_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,25]]},"assertion":[{"value":"25 October 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"RuleML+RR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Joint Conference on Rules and Reasoning","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Istanbul","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"T\u00fcrkiye","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 September 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 September 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"rulemlrr2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/2025.declarativeai.net\/events\/ruleml-rr","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}