Aggregation and Ordering in Factorised Databases

Summary: Extends factorised databases/FDB beyond select-project-join queries with aggregates and ordering. Novel partial aggregation and order-aware enumeration exploit factorisation, achieving orders-of-magnitude speedups over conventional relational engines. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: hf0bb61a3e7858b21
Venue: VLDB
Year: 2013
Pagerank: 0.00013463236
Overall Rank: 848 | 94.32%
DOI: 10.14778/2733004.2733006

Incoming Non-self Citations Over Time

Authors

1. Nurzhan Bakibayev (University of Oxford)
2. Tomáš Kociský (University of Oxford)
3. Dan Olteanu (University of Oxford)
4. Jakub Závodný (University of Oxford)

BibTeX Citation

@article{bakibayev_vldb13,
        title = {{Aggregation and Ordering in Factorised Databases}},
        author = {Bakibayev, Nurzhan and Kociský, Tomáš and Olteanu, Dan and Závodný, Jakub},
        journal = {PVLDB},
        series = {{VLDB} '13},
        volume = {6},
        number = {14},
        pages = {1610--1621},
        doi = {10.14778/2733004.2733006},
        url = {https://doi.org/10.14778/2733004.2733006},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 38 of 38 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
357	FAQ: Questions Asked Frequently	2016	PODS	0.00020048899
522	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.00016893112
731	Learning Generalized Linear Models Over Normalized Data	2015	SIGMOD	0.00014363943
815	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00013682594
1,096	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00012035761
1,568	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	0.00010178045
2,602	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	8.2157154e-05
2,673	A Layered Aggregate Engine for Analytics Workloads	2019	SIGMOD	8.1276375e-05
2,974	In-Database Learning with Sparse Tensors	2018	PODS	7.7812156e-05
3,122	Incremental View Maintenance with Triple Lock Factorization Benefits	2018	SIGMOD	7.6091671e-05
3,215	Columnar Storage and List-based Processing for Graph Database Management Systems	2021	VLDB	7.5117201e-05
3,331	SPOOF: Sum-Product Optimization and Operator Fusion for Large-Scale Machine Learning	2017	CIDR	7.4065701e-05
3,369	F: Regression Models over Factorized Views	2016	VLDB	7.3507965e-05
4,174	The Relational Data Borg is Learning	2020	VLDB	6.750725e-05
4,730	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	6.4313418e-05
5,170	Conjunctive Queries with Inequalities Under Updates	2018	VLDB	6.2330027e-05
5,506	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	6.0883761e-05
5,512	Compressed Representations of Conjunctive Query Results	2018	PODS	6.0867282e-05
5,574	Representing Paths in Graph Database Pattern Matching	2023	VLDB	6.0628579e-05
5,613	HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings	2019	PODS	6.048773e-05
6,059	Topology Dependent Bounds For FAQs	2019	PODS	5.8832527e-05
6,278	General and Fractional Hypertree Decompositions: Hard and Easy Cases	2018	PODS	5.8092008e-05
6,557	Ranked Enumeration of Join Queries with Projections	2022	VLDB	5.7298671e-05
6,579	Fast Matrix Multiplication for Query Processing	2024	PODS	5.7252637e-05
7,100	DuckPGQ: Efficient Property Graph Queries in an analytical RDBMS	2023	CIDR	5.5841286e-05
7,313	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS	5.5428538e-05
7,394	ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Join Algorithms via Reinforcement Learning	2023	VLDB	5.5202266e-05
7,936	Avoiding Materialisation for Guarded Aggregate Queries	2025	VLDB	5.4070923e-05
9,445	Output-Sensitive Evaluation of Regular Path Queries	2025	PODS	5.1630894e-05
10,192	Threshold Queries in Theory and in the Wild	2022	VLDB	5.052396e-05
10,449	Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum	2026	PODS	4.9605343e-05
10,529	Factorized and Vectorized Execution: Optimizing Analytical and Semantic Queries over Relations	2026	SIGMOD	4.9605343e-05
10,620	Approximate Query Processing under Updates	2026	SIGMOD	4.9605343e-05
10,873	BaCon: Efficient Batch Processing of Counting Queries	2026	VLDB	4.9605343e-05
10,913	The Data World Is Not Flat: Efficient Factorized Execution for Relational Systems	2026	VLDB	4.9605343e-05
11,150	A Lower Bound on Unambiguous Context Free Grammars via Communication Complexity	2025	PODS	4.9605343e-05
11,152	Circuit Bounds for Conjunctive Queries with Self-joins	2025	PODS	4.9605343e-05
12,034	Vertex-centric Parallel Computation of SQL Queries	2021	SIGMOD	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
12	C-Store: A Column-oriented DBMS	2005	VLDB	0.00068985264
27	Database Architecture Optimized for the New Bottleneck: Memory Access	1999	VLDB	0.0005146739
139	Megastore: Providing Scalable, Highly Available Storage for Interactive Services	2011	CIDR	0.00029386971
140	Remarks on the Algebra of Non First Normal Form Relations	1982	PODS	0.00029239337
196	Integrating Vertical and Horizontal Partitioning into Automated Physical Database Design	2004	SIGMOD	0.00025581936
213	Eager Aggregation and Lazy Aggregation	1995	VLDB	0.00024695393
431	HYRISE—A Main Memory Hybrid Storage Engine	2011	VLDB	0.00018411252
617	F1: A Distributed SQL Database That Scales	2013	VLDB	0.00015511217
851	Scaling Factorization Machines to Relational Data	2013	VLDB	0.00013448823
1,191	Data Compression in Oracle	2003	VLDB	0.00011557261
1,728	Incomplete Objects - A Data Model for Design and Planning Applications	1991	SIGMOD	9.7626331e-05
2,024	On Line Processing of Compacted Relations	1982	VLDB	9.1532448e-05
2,298	FDB: A Query Engine for Factorised Relational Databases	2012	VLDB	8.6645337e-05
3,068	The Case for RodentStore, an Adaptive, Declarative Storage System	2009	CIDR	7.6696594e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,726	Efficient Rank Join with Aggregation Constraints	2011	VLDB
2	2,602	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB
3	6,557	Ranked Enumeration of Join Queries with Projections	2022	VLDB
4	8,725	Aggregate Queries on Sparse Databases	2020	PODS
5	1,909	Querying Multiple Features of Groups in Relational Databases	1996	VLDB
6	2,556	Aggregation and Relevance in Deductive Databases	1991	VLDB
7	8,882	Advancing Fact Attribution for Query Answering: Aggregate Queries and Novel Algorithms	2025	VLDB
8	12,678	Demonstration of the FDB Query Engine for Factorised Databases	2012	VLDB
9	10,913	The Data World Is Not Flat: Efficient Factorized Execution for Relational Systems	2026	VLDB
10	2,298	FDB: A Query Engine for Factorised Relational Databases	2012	VLDB