Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/36213
Title: | Expressiveness within Sequence Datalog | Authors: | AAMER, Heba Hidders, Jan Paredaens, Jan VAN DEN BUSSCHE, Jan |
Issue Date: | 2021 | Publisher: | ACM | Source: | 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 | 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. | Keywords: | path variables;solving word equations;stratified negation | Document URI: | http://hdl.handle.net/1942/36213 | ISBN: | 9781450383813 | DOI: | 10.1145/3452021.3458327 | ISI #: | 000842374900007 | Rights: | 2021 Association for Computing Machinery. | Category: | C1 | Type: | Proceedings Paper | Validations: | ecoom 2023 |
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.