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.00013504405
Overall Rank: 849 | 94.30%
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.00020020639
521	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.00016929744
730	Learning Generalized Linear Models Over Normalized Data	2015	SIGMOD	0.00014406936
812	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00013729015
1,091	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00012074152
1,570	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	0.0001020855
2,591	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	8.2468757e-05
2,663	A Layered Aggregate Engine for Analytics Workloads	2019	SIGMOD	8.1581558e-05
2,975	In-Database Learning with Sparse Tensors	2018	PODS	7.7907759e-05
3,112	Incremental View Maintenance with Triple Lock Factorization Benefits	2018	SIGMOD	7.6357579e-05
3,204	Columnar Storage and List-based Processing for Graph Database Management Systems	2021	VLDB	7.5400217e-05
3,330	SPOOF: Sum-Product Optimization and Operator Fusion for Large-Scale Machine Learning	2017	CIDR	7.4173693e-05
3,373	F: Regression Models over Factorized Views	2016	VLDB	7.3661025e-05
4,161	The Relational Data Borg is Learning	2020	VLDB	6.7700593e-05
4,752	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	6.434561e-05
5,145	Conjunctive Queries with Inequalities Under Updates	2018	VLDB	6.2566119e-05
5,482	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	6.111411e-05
5,489	Compressed Representations of Conjunctive Query Results	2018	PODS	6.1095111e-05
5,557	Representing Paths in Graph Database Pattern Matching	2023	VLDB	6.085853e-05
5,601	HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings	2019	PODS	6.0706976e-05
6,044	Topology Dependent Bounds For FAQs	2019	PODS	5.9055665e-05
6,264	General and Fractional Hypertree Decompositions: Hard and Easy Cases	2018	PODS	5.8308708e-05
6,545	Ranked Enumeration of Join Queries with Projections	2022	VLDB	5.7515992e-05
6,567	Fast Matrix Multiplication for Query Processing	2024	PODS	5.7469783e-05
7,078	DuckPGQ: Efficient Property Graph Queries in an analytical RDBMS	2023	CIDR	5.6053079e-05
7,293	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS	5.5638766e-05
7,367	ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Join Algorithms via Reinforcement Learning	2023	VLDB	5.5411636e-05
7,917	Avoiding Materialisation for Guarded Aggregate Queries	2025	VLDB	5.4276002e-05
9,410	Output-Sensitive Evaluation of Regular Path Queries	2025	PODS	5.1826718e-05
10,153	Threshold Queries in Theory and in the Wild	2022	VLDB	5.0715586e-05
10,371	Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum	2026	PODS	4.9793485e-05
10,452	Factorized and Vectorized Execution: Optimizing Analytical and Semantic Queries over Relations	2026	SIGMOD	4.9793485e-05
10,544	Approximate Query Processing under Updates	2026	SIGMOD	4.9793485e-05
10,802	BaCon: Efficient Batch Processing of Counting Queries	2026	VLDB	4.9793485e-05
10,842	The Data World Is Not Flat: Efficient Factorized Execution for Relational Systems	2026	VLDB	4.9793485e-05
11,080	A Lower Bound on Unambiguous Context Free Grammars via Communication Complexity	2025	PODS	4.9793485e-05
11,082	Circuit Bounds for Conjunctive Queries with Self-joins	2025	PODS	4.9793485e-05
11,984	Vertex-centric Parallel Computation of SQL Queries	2021	SIGMOD	4.9793485e-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.00068998927
27	Database Architecture Optimized for the New Bottleneck: Memory Access	1999	VLDB	0.0005158963
139	Megastore: Providing Scalable, Highly Available Storage for Interactive Services	2011	CIDR	0.00029480065
140	Remarks on the Algebra of Non First Normal Form Relations	1982	PODS	0.00029346895
195	Integrating Vertical and Horizontal Partitioning into Automated Physical Database Design	2004	SIGMOD	0.00025628849
213	Eager Aggregation and Lazy Aggregation	1995	VLDB	0.00024759805
431	HYRISE—A Main Memory Hybrid Storage Engine	2011	VLDB	0.00018403783
617	F1: A Distributed SQL Database That Scales	2013	VLDB	0.00015555815
851	Scaling Factorization Machines to Relational Data	2013	VLDB	0.00013457975
1,192	Data Compression in Oracle	2003	VLDB	0.00011590015
1,718	Incomplete Objects - A Data Model for Design and Planning Applications	1991	SIGMOD	9.7987023e-05
2,012	On Line Processing of Compacted Relations	1982	VLDB	9.1867589e-05
2,290	FDB: A Query Engine for Factorised Relational Databases	2012	VLDB	8.6889284e-05
3,056	The Case for RodentStore, an Adaptive, Declarative Storage System	2009	CIDR	7.6972474e-05

Semantically Similar Papers

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