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: 10872
Venue: VLDB
Year: 2013
Pagerank: 0.00013560445
Overall Rank: 860 | 94.11%
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 36 of 36 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
358	FAQ: Questions Asked Frequently	2016	PODS	0.00020243592
536	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.0001693369
715	Learning Generalized Linear Models Over Normalized Data	2015	SIGMOD	0.00014655327
816	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00013827772
1,109	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00012142685
1,549	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	0.00010390168
2,745	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	8.1747954e-05
2,769	A Layered Aggregate Engine for Analytics Workloads	2019	SIGMOD	8.1465406e-05
2,927	In-Database Learning with Sparse Tensors	2018	PODS	7.9531195e-05
3,206	Incremental View Maintenance with Triple Lock Factorization Benefits	2018	SIGMOD	7.6367549e-05
3,284	SPOOF: Sum-Product Optimization and Operator Fusion for Large-Scale Machine Learning	2017	CIDR	7.5663058e-05
3,334	F: Regression Models over Factorized Views	2016	VLDB	7.5110164e-05
3,357	Columnar Storage and List-based Processing for Graph Database Management Systems	2021	VLDB	7.4904874e-05
4,128	The Relational Data Borg is Learning	2020	VLDB	6.8850804e-05
5,066	Conjunctive Queries with Inequalities Under Updates	2018	VLDB	6.3771079e-05
5,383	Compressed Representations of Conjunctive Query Results	2018	PODS	6.2374576e-05
5,418	Representing Paths in Graph Database Pattern Matching	2023	VLDB	6.2255373e-05
5,461	HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings	2019	PODS	6.2090515e-05
5,593	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	6.1552328e-05
5,601	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	6.1540123e-05
5,923	Topology Dependent Bounds For FAQs	2019	PODS	6.0411129e-05
6,159	General and Fractional Hypertree Decompositions: Hard and Easy Cases	2018	PODS	5.9542729e-05
6,412	Ranked Enumeration of Join Queries with Projections	2022	VLDB	5.8836116e-05
6,885	Fast Matrix Multiplication for Query Processing	2024	PODS	5.7464502e-05
6,999	DuckPGQ: Efficient Property Graph Queries in an analytical RDBMS	2023	CIDR	5.7291934e-05
7,143	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS	5.6915726e-05
7,978	ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Join Algorithms via Reinforcement Learning	2023	VLDB	5.514996e-05
9,235	Output-Sensitive Evaluation of Regular Path Queries	2025	PODS	5.3016261e-05
9,720	Avoiding Materialisation for Guarded Aggregate Queries	2025	VLDB	5.2319816e-05
9,961	Threshold Queries in Theory and in the Wild	2022	VLDB	5.1879626e-05
10,154	Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum	2026	PODS	5.093636e-05
10,237	Factorized and Vectorized Execution: Optimizing Analytical and Semantic Queries over Relations	2026	SIGMOD	5.093636e-05
10,342	Approximate Query Processing under Updates	2026	SIGMOD	5.093636e-05
10,636	A Lower Bound on Unambiguous Context Free Grammars via Communication Complexity	2025	PODS	5.093636e-05
10,639	Circuit Bounds for Conjunctive Queries with Self-joins	2025	PODS	5.093636e-05
11,677	Vertex-centric Parallel Computation of SQL Queries	2021	SIGMOD	5.093636e-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.00069513174
29	Database Architecture Optimized for the New Bottleneck: Memory Access	1999	VLDB	0.00052093615
140	Remarks on the Algebra of Non First Normal Form Relations	1982	PODS	0.00029686538
144	Megastore: Providing Scalable, Highly Available Storage for Interactive Services	2011	CIDR	0.00029554682
199	Integrating Vertical and Horizontal Partitioning into Automated Physical Database Design	2004	SIGMOD	0.00025612088
206	Eager Aggregation and Lazy Aggregation	1995	VLDB	0.00025092273
428	HYRISE—A Main Memory Hybrid Storage Engine	2011	VLDB	0.00018633493
607	F1: A Distributed SQL Database That Scales	2013	VLDB	0.00015800238
835	Scaling Factorization Machines to Relational Data	2013	VLDB	0.00013721583
1,222	Data Compression in Oracle	2003	VLDB	0.00011602327
1,690	Incomplete Objects - A Data Model for Design and Planning Applications	1991	SIGMOD	0.00010001011
1,976	On Line Processing of Compacted Relations	1982	VLDB	9.3644331e-05
2,392	FDB: A Query Engine for Factorised Relational Databases	2012	VLDB	8.6404947e-05
3,009	The Case for RodentStore, an Adaptive, Declarative Storage System	2009	CIDR	7.8541296e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,593	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB
2	12,386	Efficient Rank Join with Aggregation Constraints	2011	VLDB
3	2,745	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB
4	6,412	Ranked Enumeration of Join Queries with Projections	2022	VLDB
5	8,528	Aggregate Queries on Sparse Databases	2020	PODS
6	1,860	Querying Multiple Features of Groups in Relational Databases	1996	VLDB
7	2,511	Aggregation and Relevance in Deductive Databases	1991	VLDB
8	8,688	Advancing Fact Attribution for Query Answering: Aggregate Queries and Novel Algorithms	2025	VLDB
9	12,338	Demonstration of the FDB Query Engine for Factorised Databases	2012	VLDB
10	2,392	FDB: A Query Engine for Factorised Relational Databases	2012	VLDB