{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T04:07:54Z","timestamp":1751342874623,"version":"3.41.0"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"name":"Special Research Fund (BOF) bof","award":["BOF19OWB16 bof"],"award-info":[{"award-number":["BOF19OWB16 bof"]}]},{"DOI":"10.13039\/501100003130","name":"Fonds Wetenschappelijk Onderzoek Vlaanderen","doi-asserted-by":"crossref","award":["(1210525N fwo) or (G062721N fwo)"],"award-info":[{"award-number":["(1210525N fwo) or (G062721N fwo)"]}],"id":[{"id":"10.13039\/501100003130","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Flanders AI Research Programme"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2025,9,30]]},"abstract":"<jats:p>Motivated by old and new applications, we investigate Datalog as a language for sequence databases. We reconsider classical features of Datalog programs, such as negation, recursion, intermediate predicates, and relations of higher arities. We also consider new features that are useful for sequences, notably, equations between path expressions, and \u201cpacking\u201d. Our goal is to clarify the relative expressiveness of all these different features, in the context of sequences. Towards our goal, we establish a number of redundancy and primitivity results, showing that certain features can, or cannot, be expressed in terms of other features. These results paint a complete picture of the expressiveness relationships among all possible Sequence Datalog fragments that can be formed using the six features that we consider.<\/jats:p>","DOI":"10.1145\/3732283","type":"journal-article","created":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T11:17:49Z","timestamp":1746098269000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Expressiveness within Sequence Datalog"],"prefix":"10.1145","volume":"50","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0460-8534","authenticated-orcid":false,"given":"Heba","family":"Aamer","sequence":"first","affiliation":[{"name":"SOFT Lab, Vrije Universiteit Brussel","place":["Brussel, Belgium"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8865-4329","authenticated-orcid":false,"given":"Jan","family":"Hidders","sequence":"additional","affiliation":[{"name":"Birkbeck University of London","place":["London, United Kingdom"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-0629-2756","authenticated-orcid":false,"given":"Jan","family":"Paredaens","sequence":"additional","affiliation":[{"name":"University of Antwerp","place":["Antwerpen, Belgium"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0072-3252","authenticated-orcid":false,"given":"Jan","family":"Van den Bussche","sequence":"additional","affiliation":[{"name":"Data Science Institute, Hasselt University","place":["Hasselt, Belgium"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,30]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3452021.3458327"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-25383-6_11"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(89)80056-2"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.5555\/551350"},{"key":"e_1_3_2_6_2","series-title":"CEUR Workshop Proceedings","volume-title":"Datalog 2.0 2019: Third International Workshop on the Resurgence of Datalog in Academia and Industry","volume":"2368","author":"Alviano M.","year":"2019","unstructured":"M. Alviano and A. Pieris (Eds.). 2019. Datalog 2.0 2019: Third International Workshop on the Resurgence of Datalog in Academia and Industry. CEUR Workshop Proceedings, Vol. 2368. CEUR-WS.org."},{"key":"e_1_3_2_7_2","first-page":"40","volume-title":"Proceedings of the 1st International Conference on Deductive and Object-Oriented Databases","author":"Atkinson M.","year":"1989","unstructured":"M. Atkinson, F. Bancilhon, D. DeWitt, K. Dittrich, D. Maier, and S. Zdonik. 1989. The object-oriented database system manifesto. In Proceedings of the 1st International Conference on Deductive and Object-Oriented Databases. W. Kim, J.-M. Nicolas, and S. Nishio (Eds.), Elsevier Science Publishers, 40\u201357."},{"key":"e_1_3_2_8_2","first-page":"6:1\u20136:20","volume-title":"Proceedings of the 23rd International Conference on Database Theory.","volume":"155","author":"Barcel\u00f3 P.","year":"2020","unstructured":"P. Barcel\u00f3, N. Higeura, J. P\u00e9rez, and B. Suercaseaux. 2020. On the expressiveness of LARA: A unified language for linear and relational algebra. In Proceedings of the 23rd International Conference on Database Theory.C. Lutz and J.C. Jung (Eds.), Leibniz International Proceedings in Informatics, Vol. 155, Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 6:1\u20136:20."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.5555\/2415092"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/876638.876642"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1562"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.5555\/342769.342771"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90012-5"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0014006"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/101077.390001"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24206-9"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-99840-4_6"},{"key":"e_1_3_2_18_2","volume-title":"Finite Model Theory (2nd. ed.)","author":"Ebbinghaus H. -D.","year":"1999","unstructured":"H. -D. Ebbinghaus and J. Flum. 1999. Finite Model Theory (2nd. ed.). Springer."},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2699442"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1514"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1633"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44543-9_5"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(95)00072-0"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056106"},{"key":"e_1_3_2_25_2","unstructured":"J. Hidders J. Paredaens and J. Van den Bussche. 2020. J-Logic: a Logic for Querying JSON. arXiv:2006.04277. Retrieved from https:\/\/arxiv.org\/abs\/2006.04277"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3070607.3070608"},{"key":"e_1_3_2_27_2","unstructured":"IEEE Task Force on Process Mining. 2011. Process mining manifesto. Retrieved 10 May 2025 from https:\/\/www.tf-pm.org\/resources\/manifesto"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/1024694.1024697"},{"key":"e_1_3_2_29_2","first-page":"3180","volume-title":"Proceedings of the IEEE International Conference on Big Data","author":"Nie J.-Y.","year":"2017","unstructured":"H. Jananthan, Z. Zhou, V. Gadepally, D. Hutchison, S. Kim, and J. Kepner. 2017. Polystore mathematics of relational algebra. In Proceedings of the IEEE International Conference on Big Data. J.-Y. Nie, Z. Obradovic, T. Suzumura, et\u00a0al. (Eds.), IEEE, 3180\u20133189."},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/1966385.1966386"},{"key":"e_1_3_2_31_2","first-page":"1421","volume-title":"Proceedings of the 2018 International Conference on Management of Data","author":"Force LDBC Graph Query Language Task","year":"2018","unstructured":"LDBC Graph Query Language Task Force. 2018. G-CORE: A core for future graph query languages. In Proceedings of the 2018 International Conference on Management of Data. ACM, 1421\u20131432."},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233335"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3405470"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/69.929906"},{"key":"e_1_3_2_35_2","first-page":"6:1\u20136:7","volume-title":"Proceedings of the 19th International Conference on Web and Databases","author":"Nahshon Y.","year":"2019","unstructured":"Y. Nahshon, L. Peterfreund, and S. Vansummeren. 2019. Incorporating information extraction in the relational database model. In Proceedings of the 19th International Conference on Web and Databases. ACM, 6:1\u20136:7."},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.14778\/3025111.3025117"},{"key":"e_1_3_2_37_2","series-title":"LIPIcs","first-page":"13:1\u201313:18","volume-title":"Proceedings of the 22nd International Conference on Database Theory.","volume":"127","author":"Barcelo P.","year":"2019","unstructured":"L. Peterfreund, B. ten Cate, R. Fagin, and B. Kimelfeld. 2019. Recursive programs for document spanners. In Proceedings of the 22nd International Conference on Database Theory.P. Barcelo and M. Calautti (Eds.), LIPIcs, Vol. 127, Schloss Dagstuhl\u2013Leibniz Center for Informatics, 13:1\u201313:18."},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/2872427.2883029"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.10.023"},{"key":"e_1_3_2_40_2","first-page":"73","volume-title":"Proceedings of the Machine Intelligence 7","author":"Plotkin G.","year":"1972","unstructured":"G. Plotkin. 1972. Building-in equational theories. In Proceedings of the Machine Intelligence 7. B. Meltzer and D. Michie (Eds.), Edinburgh University Press, 73\u201390."},{"key":"e_1_3_2_41_2","first-page":"84","volume-title":"Proceedings of the 10th International Conference on Scientific and Statistical Database Management","author":"Rafanelli M.","year":"1998","unstructured":"R. Ramakrsihnan, D. Donjerkovic, A. Ranganathan, K. S. Beyer, and M. Krishnaprasad. 1998. SRQL: Sorted relational query language. In Proceedings of the 10th International Conference on Scientific and Statistical Database Management. M. Rafanelli and M. Jarke (Eds.), IEEE Computer Society, 84\u201395."},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-008-9110-5"},{"key":"e_1_3_2_43_2","unstructured":"F. Rusu and Y. Cheng. 2013. A survey on array storage query languages and systems. arXiv:1302.0103. Retrieved from https:\/\/arxiv.org\/abs\/1302.0103"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/1005566.1005568"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1995.380388"},{"key":"e_1_3_2_46_2","first-page":"1033","volume-title":"Proceedings of the 33th International Conference on Very Large Data Bases","author":"Koch Ch.","year":"2007","unstructured":"W. Shen, A. Doan, J. F. Naughton, and R. Ramakrishnan. 2007. Declarative information extraction using datalog with embedded extraction. In Proceedings of the 33th International Conference on Very Large Data Bases. Ch. Koch et\u00a0al. (Eds.), ACM, 1033\u20131044."},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.5555\/42790"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3732283","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T11:45:08Z","timestamp":1751283908000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3732283"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,30]]},"references-count":46,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9,30]]}},"alternative-id":["10.1145\/3732283"],"URL":"https:\/\/doi.org\/10.1145\/3732283","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2025,6,30]]},"assertion":[{"value":"2024-01-19","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-31","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-30","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}