Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/36213Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | AAMER, Heba | - |
| dc.contributor.author | Hidders, Jan | - |
| dc.contributor.author | Paredaens, Jan | - |
| dc.contributor.author | VAN DEN BUSSCHE, Jan | - |
| dc.date.accessioned | 2021-12-15T12:58:53Z | - |
| dc.date.available | 2021-12-15T12:58:53Z | - |
| dc.date.issued | 2021 | - |
| dc.date.submitted | 2021-12-10T13:16:54Z | - |
| dc.identifier.citation | Libkin, Leonid; Pichler, Reinhard; Guagliardo, Paolo (Ed.). Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 2021), ACM, p. 70 -81 | - |
| dc.identifier.isbn | 9781450383813 | - |
| dc.identifier.uri | http://hdl.handle.net/1942/36213 | - |
| dc.description.abstract | 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 "packing". 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. | - |
| dc.language.iso | en | - |
| dc.publisher | ACM | - |
| dc.subject.other | path variables | - |
| dc.subject.other | solving word equations | - |
| dc.subject.other | stratified negation | - |
| dc.title | Expressiveness within Sequence Datalog | - |
| dc.type | Proceedings Paper | - |
| local.bibliographicCitation.authors | Libkin, Leonid | - |
| local.bibliographicCitation.authors | Pichler, Reinhard | - |
| local.bibliographicCitation.authors | Guagliardo, Paolo | - |
| local.bibliographicCitation.conferencedate | June 20 - 25, 2021 | - |
| local.bibliographicCitation.conferenceplace | Virtual Event Xi'an, Shaanxi, China | - |
| dc.identifier.epage | 81 | - |
| dc.identifier.spage | 70 | - |
| local.format.pages | 12 | - |
| local.bibliographicCitation.jcat | C1 | - |
| local.publisher.place | 1601 Broadway, 10th Floor, NEW YORK, NY, UNITED STATES | - |
| dc.relation.references | [1] H. Abdulrab and J.-P. Pécuchet. 1989. Solving word equations. Journal of Symbolic Computation 8, 5 (1989), 499–521. [2] S. Abiteboul, R. Hull, and V. Vianu. 1995. Foundations of Databases. Addison-Wesley. [3] 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. [4] M. Atkinson, F. Bancilhon, D. DeWitt, K. Dittrich, D. Maier, and S. Zdonik. 1989. The Object-Oriented Database System Manifesto. In Proceedings 1st International Conference on Deductive and Object-Oriented Databases, W. Kim, J.-M. Nicolas, and S. Nishio (Eds.). Elsevier Science Publishers, 40–57. [5] P. Barceló, N. Higeura, J. Pérez, and B. Suercaseaux. 2020. On the expressiveness of LARA: A unified language for linear and relational algebra. In Proceedings 23rd International Conference on Database Theory (Leibniz International Proceedings in Informatics, Vol. 155), C. Lutz and J.C. Jung (Eds.). Schloss Dagstuhl–Leibniz- Zentrum für Informatik, 6:1–6:20. [6] P. Barceló and R. Pichler (Eds.). 2012. Datalog in Academia and Industry: Second International Workshop, Datalog 2.0. Lecture Notes in Computer Science, Vol. 7494. Springer. [7] M. Benedikt, L. Libkin, T. Schwentick, and L. Segoufin. 2003. Definable relations and first-order query languages over strings. J. ACM 50, 5 (2003), 694–751. [8] A. Bonner and G. Mecca. 1998. Sequences, Datalog, and transducers. J. Comput. System Sci. 57 (1998), 234–259. [9] A.J. Bonner and G. Mecca. 2000. Querying sequence databases with transducers. Acta Informatica 36 (2000), 511–544. [10] A.K. Chandra and D. Harel. 1982. Structure and complexity of relational queries. J. Comput. System Sci. 25, 1 (1982), 99–128. [11] J. Chomicki. 1994. Temporal query languages: a survey. In Temporal Logic: ICTL’94 (Lecture Notes in Computer Science, Vol. 827), D.M. Gabbay and H.J. Ohlbach (Eds.). Springer-Verlag, 506–534. [12] The Commitee for Advanced DBMS Function. 1990. Third-Generation Database System Manifesto. SIGMOD Record 19, 3 (1990), 31–44. [13] O. de Moor, G. Gottlob, T. Furche, and A. Sellers (Eds.). 2011. Datalog Reloaded: First International Workshop, Datalog 2010. Lecture Notes in Computer Science, Vol. 6702. Springer. [14] F. Durán, S. Eker, S. Escobar, N. Martí-Oliet, J. Meseguer, and C. Talcott. 2018. Associative unification and symbolic reasoning modulo associativity in Maude. In Proceedings 12th International Workshop on Rewriting Logic and Its Applications (Lecture Notes in Computer Science, Vol. 11152), V. Rusu (Ed.). Springer, 98–114. [15] H.-D. Ebbinghaus and J. Flum. 1999. Finite Model Theory (second ed.). Springer. [16] R. Fagin, B. Kimelfeld, F. Reiss, and S. Vansummeren. 2015. Document spanners: A formal approach to information extraction. J. ACM 62, 2 (2015), 12:1–12:51. [17] S. Ginsburg and X.S. Wang. 1998. Regular sequence operations and their use in database queries. J. Comput. System Sci. 56, 1 (1998), 1–26. [18] G. Grahne, M. Nykänen, and E. Ukkonen. 1999. Reasoning about strings in databases. J. Comput. System Sci. 59 (1999), 116–162. [19] G. Grahne and E. Waller. 2000. How to make SQL stand for String Query Language. In Research Issues in Structured and Semistructured Database Programming (Lecture Notes in Computer Science, Vol. 1949), R.C.H. Connor and A.O. Mendelzon (Eds.).Springer, 61–79. [20] M. Grohe. 1996. Arity hierarchies. Annals of Pure and Applied Logic 82, 2 (1996), 103–163. [21] J. Hidders, J. Paredaens, and J. Van den Bussche. 2017. J-Logic: Logical foundations for JSON querying. In Proceedings 36th ACM Symposium on Principles of Databases. ACM, 137–149. [22] J. Hidders, J. Paredaens, and J. Van den Bussche. 2020. J-Logic: a Logic for Querying JSON. arXiv:2006.04277. [23] D. Hutchison, B. Howe, and D. Suciu. 2017. LaraDB: A minimalist kernel for linear and relational algebra computation. In Proceedings 4th ACM SIGMOD Workshop on Algorithms and Systems for MapReduce and Beyond, F.N. Afrati and J. Sroka (Eds.). 2:1–2:10. [24] IEEE Task Force on Process Mining. 2011. Process mining manifesto. https://www.tf-pm.org/resources/manifesto [25] H.V. Jagadish and F. Olken. 2004. Database management for life science research. SIGMOD Record 33, 2 (2004), 15–20. [26] H. Jananthan, Z. Zhou, et al. 2017. Polystore mathematics of relational algebra. In Proceedings IEEE International Conference on Big Data, J.-Y. Nie, Z. Obradovic, T. Suzumura, et al. (Eds.). IEEE, 3180–3189. [27] Y.-N. Law, H. Wang, and C. Zaniolo. 2011. Relational languages and data models for continuous queries on sequences and data streams. ACM Transactions on Database Systems 36, 2 (2011), 8:1–8:32. [28] LDBC Graph Query Language Task Force. 2018. G-CORE: A core for future graph query languages. In Proceedings 2018 International Conference on Management of Data. ACM, 1421–1432. [29] L. Libkin, R. Machlin, and L. Wong. 1996. A query language for multidimensional arrays: design, implementations, and optimization techniques. In Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data (SIGMOD Record, Vol. 25:2). ACM Press, 228–239. [30] S. Luo, Z.J. Gao, M.N. Gubanov, L.L. Perez, D. Jankov, and C.M. Jermaine. 2020. Scalable linear algebra on a relational database system. Commun. ACM 63, 8 (2020), 93–101. [31] G. Mecca and A.J. Bonner. 2001. Query languages for sequence databases: Termination and Complexity. IEEE Transactions on Knowledge and Data Engineering 13, 3 (2001), 519–525. [32] Y. Nahshon, L. Peterfreund, and S. Vansummeren. 2019. Incorporating information extraction in the relational database model. In Proceedings 19th International Conference on Web and Databases. ACM, 6:1–6:7. [33] S. Papadopoulos et al. 2016. The TileDB array data storage manager. Proceedings of the VLDB Endowment 10, 4 (2016), 349–360. [34] L. Peterfreund et al. 2019. Recursive programs for document spanners. In Proceedings 22nd International Conference on Database Theory (LIPIcs, Vol. 127), P. Barcelo and M. Calautti (Eds.). Schloss Dagstuhl–Leibniz Center for Informatics, 13:1– 13:18. [35] F. Pezoa, J.L. Reutter, F. Suarez, M. Ugarte, and D. Vrgoč. 2016. Foundations of JSON Schema. In Proceedings 25th International Conference on World Wide Web. 263–273. [36] W. Plandowski. 2019. On PSPACE generation of a solution set of a word equation and its applications. Theoretical Computer Science 792 (2019), 20–61. [37] G. Plotkin. 1972. Building-in equational theories. In Machine Intelligence 7, B. Meltzer and D. Michie (Eds.). Edinburgh University Press, 73–90. [38] R. Ramakrishnan et al. 1998. SRQL: Sorted relational query language. In Proceedings 10th International Conference on Scientific and Statistical Database Management, M. Rafanelli and M. Jarke (Eds.). IEEE Computer Society, 84–95. [39] E.L. Robertson, L.V. Saxton, D. Van Gucht, and S. Vansummeren. 2009. Structural recursion as a query language on lists and ordered trees. Theory of Computing Systems 44 (2009), 590–619. [40] F. Rusu and Y. Cheng. 2013. A survey on array storage, query languages, and systems. arXiv:1302.0103. [41] R. Sadri, C. Zaniolo, A. Zarkesh, et al. 2004. Expressing and optimizing sequence queries in database systems. ACM Transactions on Database Systems 29, 2 (2004), 282–318. [42] P. Seshadri, M. Livny, and R. Ramakrishnan. 1995. SEQ: A model for sequence databases. In Proceedings 11th International Conference on Data Engineering, P.S. Yu and A.L.P. Chen (Eds.). IEEE Computer Society, 232–239. [43] W. Shen et al. 2007. Declarative information extraction using Datalog with embedded extraction. In Proceedings 33th International Conference on Very Large Data Bases, Ch. Koch et al. (Eds.). ACM, 1033–1044. [44] J.D. Ullman. 1988. Principles of Database and Knowledge-Base Systems. Vol. I. Computer Science Press. | - |
| local.type.refereed | Refereed | - |
| local.type.specified | Proceedings Paper | - |
| dc.identifier.doi | 10.1145/3452021.3458327 | - |
| dc.identifier.isi | 000842374900007 | - |
| local.provider.type | CrossRef | - |
| local.bibliographicCitation.btitle | Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 2021) | - |
| local.uhasselt.uhpub | yes | - |
| local.uhasselt.international | yes | - |
| item.validation | ecoom 2023 | - |
| item.fulltext | With Fulltext | - |
| item.accessRights | Open Access | - |
| item.fullcitation | AAMER, Heba; Hidders, Jan; Paredaens, Jan & VAN DEN BUSSCHE, Jan (2021) Expressiveness within Sequence Datalog. In: Libkin, Leonid; Pichler, Reinhard; Guagliardo, Paolo (Ed.). Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 2021), ACM, p. 70 -81. | - |
| item.contributor | AAMER, Heba | - |
| item.contributor | Hidders, Jan | - |
| item.contributor | Paredaens, Jan | - |
| item.contributor | VAN DEN BUSSCHE, Jan | - |
| Appears in Collections: | Research publications | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| xian.pdf Restricted Access | Published version | 4.26 MB | Adobe PDF | View/Open Request a copy |
| 2206.06754.pdf | Non Peer-reviewed author version | 4.69 MB | Adobe PDF | View/Open |
Page view(s)
44
checked on Sep 7, 2022
Download(s)
16
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.