Givens QR Decomposition over Relational Databases

Summary: FiGaRo computes the QR upper-triangular factor of the matrix defined by a relational join, pushing QR into the join. For acyclic joins, runtime is linear in database size; uses Givens rotations with small rounding error, beating LAPACK-based baselines. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6518
Venue: SIGMOD
Year: 2022
Pagerank: 5.093636e-05
Overall Rank: 11,561 | 20.69%
DOI: 10.1145/3514221.3526144

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Dan Olteanu (University of Zurich)
2. Nils Vortmeier (University of Zurich)
3. Đorđe Živanović (University of Oxford)

BibTeX Citation

@inproceedings{olteanu_sigmod22,
        title = {{Givens QR Decomposition over Relational Databases}},
        author = {Olteanu, Dan and Vortmeier, Nils and Živanović, Đorđe},
        series = {{SIGMOD} '22},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3514221.3526144},
        url = {https://dl.acm.org/doi/10.1145/3514221.3526144},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
206	Eager Aggregation and Lazy Aggregation	1995	VLDB	0.00025092273
358	FAQ: Questions Asked Frequently	2016	PODS	0.00020243592
536	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.0001693369
1,235	Towards Linear Algebra over Normalized Data	2017	VLDB	0.00011548457
2,179	Enabling and Optimizing Non-linear Feature Interactions in Factorized Linear Algebra	2019	SIGMOD	9.0146333e-05
2,273	SliceLine: Fast, Linear-Algebra-based Slice Finding for ML Model Debugging	2021	SIGMOD	8.8230899e-05
2,769	A Layered Aggregate Engine for Analytics Workloads	2019	SIGMOD	8.1465406e-05
4,128	The Relational Data Borg is Learning	2020	VLDB	6.8850804e-05
4,409	MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions	2019	SIGMOD	6.7178579e-05
5,195	Tensor Relational Algebra for Distributed Machine Learning System Design	2021	VLDB	6.3232105e-05
6,046	Automatic Optimization of Matrix Implementations for Distributed Machine Learning and Linear Algebra	2021	SIGMOD	5.9956597e-05
6,514	A Relational Matrix Algebra and its Implementation in a Column Store	2020	SIGMOD	5.8559163e-05
6,814	Expressive Power of Linear Algebra Query Languages	2021	PODS	5.7657129e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,128	The Relational Data Borg is Learning	2020	VLDB
2	9,675	BlockJoin: Efficient Matrix Partitioning Through Joins	2017	VLDB
3	2,991	FactorJoin: A New Cardinality Estimation Framework for Join Queries	2023	SIGMOD
4	3,228	Correlation Sketches for Approximate Join-Correlation Queries	2021	SIGMOD
5	2,631	FastQRE: Fast Query Reverse Engineering	2018	SIGMOD
6	5,364	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD
7	715	Learning Generalized Linear Models Over Normalized Data	2015	SIGMOD
8	2,179	Enabling and Optimizing Non-linear Feature Interactions in Factorized Linear Algebra	2019	SIGMOD
9	8,630	Extending Relational Query Optimization to Dynamic Schemas for Information Integration in Multidatabases	2007	SIGMOD
10	536	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD