Expressive Power of Linear Algebra Query Languages

Summary: Extend MATLANG with dimension-bounded recursion (loops up to matrix size) to express classical linear-algebra algorithms such as Gaussian elimination and matrix inversion. Characterize expressiveness as arithmetic-circuit families; subfragments correspond to logics on semiring-annotated relations. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h2d64a3d07f135284
Venue: PODS
Year: 2021
Pagerank: 5.6383218e-05
Overall Rank: 6,942 | 53.33%
DOI: 10.1145/3452021.3458314

Incoming Non-self Citations Over Time

Authors

1. Floris Geerts (University of Antwerp)
2. Thomas Muñoz (Millennium Institute for Foundational Research on Data (Chile); Pontifical Catholic University of Chile)
3. Cristian Riveros (Millennium Institute for Foundational Research on Data (Chile); Pontifical Catholic University of Chile)
4. Domagoj Vrgoč (Millennium Institute for Foundational Research on Data (Chile); Pontifical Catholic University of Chile)

BibTeX Citation

@inproceedings{geerts_pods21,
        address = {New York, NY, USA},
        series = {{PODS} '21},
        title = {{Expressive Power of Linear Algebra Query Languages}},
        url = {https://dl.acm.org/doi/10.1145/3452021.3458314},
        doi = {10.1145/3452021.3458314},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Geerts, Floris and Muñoz, Thomas and Riveros, Cristian and Vrgoč, Domagoj},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,018	A Query Language Perspective on Graph Learning	2023	PODS	5.9129763e-05
10,262	Automating Vectorized Distributed Graph Computation	2024	SIGMOD	5.050482e-05
10,383	Recursive Querying of Neural Networks via Weighted Structures	2026	PODS	4.9793485e-05
11,870	Givens QR Decomposition over Relational Databases	2022	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
17	Provenance Semirings	2007	PODS	0.00059752575

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,330	Investigation of Algebraic Query Optimisation for Database Programming Languages	1994	VLDB
2	4,559	A Query Language for List-Based Complex Objects	1994	PODS
3	8,005	New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions	1994	PODS
4	1,950	Relational Expressive Power of Constraint Query Languages	1996	PODS
5	1,919	The Expressiveness of a Family of Finite Set Languages	1991	PODS
6	2,109	A Study of Transitive Closure As a Recursion Mechanism	1987	SIGMOD
7	6,689	Functional Database Query Languages as Typed Lambda Calculi of Fixed Order (Extended Abstract)	1994	PODS
8	305	A Graphical Query Language Supporting Recursion	1987	SIGMOD
9	2,152	Querying Constraints	1990	PODS
10	7,411	On the Power of Algebras with Recursion	1993	SIGMOD