Expressiveness within Sequence Datalog

Summary: Characterizes expressiveness of Sequence Datalog over sequences across six features (negation, recursion, intermediate predicates, higher arity, path-equations, packing). Proves redundancy/primitivity theorems classifying which features encode others versus which are primitive, yielding a complete taxonomy of Sequence Datalog fragments. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1854
Venue: PODS
Year: 2021
Pagerank: 5.2302568e-05
Overall Rank: 9,725 | 33.28%
DOI: 10.1145/3452021.3458327

Incoming Non-self Citations Over Time

Authors

1. Heba Aamer (Hasselt University)
2. Jan Hidders (Birkbeck, University of London)
3. Jan Paredaens (University of Antwerp)
4. Jan Van den Bussche (Hasselt University)

BibTeX Citation

@inproceedings{aamer_pods21,
        address = {New York, NY, USA},
        series = {{PODS} '21},
        title = {{Expressiveness within Sequence Datalog}},
        url = {https://dl.acm.org/doi/10.1145/3452021.3458327},
        doi = {10.1145/3452021.3458327},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Aamer, Heba and Hidders, Jan and Paredaens, Jan and Van den Bussche, Jan},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,947	Optimizing Time Series Queries with Versions	2024	SIGMOD	5.1915905e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
319	Declarative Information Extraction Using Datalog with Embedded Extraction Predicates	2007	VLDB	0.00021377065
669	The TileDB Array Data Storage Manager	2017	VLDB	0.00015163245
900	G-CORE: A Core for Future Graph Query Languages	2018	SIGMOD	0.00013337186
1,434	A Query Language for Multidimensional Arrays: Design, Implementation, and Optimization Techniques	1996	SIGMOD	0.00010800479
9,851	J-Logic: Logical Foundations for JSON Querying	2017	PODS	5.2094004e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,600	Convergence of Datalog over (Pre-) Semirings	2022	PODS
2	6,785	Expressiveness of Guarded Existential Rule Languages	2014	PODS
3	3,712	Non-Deterministic Languages to Express Deterministic Transformations	1990	PODS
4	7,536	Database Updates in Logic Programming	1988	PODS
5	6,301	Evaluating Datalog over Semirings: A Grounding-based Approach	2024	PODS
6	6,613	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS
7	9,430	A Theory of Regular Queries	2016	PODS
8	7,972	On the First-Order Expressibility of Recursive Queries	1989	PODS
9	13,078	Datalog Expressiveness of Chain Queries: Grammar Tools and Characterizations	1992	PODS
10	6,802	Sequences, Datalog and Transducers	1995	PODS