Database Paper Browser

Back to papers

FAQ: Questions Asked Frequently

Summary: Defines FAQ, a unifying formalism for CSPs, PGMs, matrix ops, joins and logic, and presents InsideOut, a variable-elimination algorithm that leverages fractional edge covers and worst-case optimal join techniques. Characterizes semantically equivalent variable orderings and gives a polytime approximation to minimize fractional FAQ-width. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1675
Venue
PODS
Year
2016
Pagerank
0.00019717214
Overall Rank
583 | 95.95%
DOI
10.1145/2902251.2902280

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 64 citing papers.

Rank Citing Paper Year Venue Pagerank
342 EmptyHeaded: A Relational Engine for Graph Processing 2016 SIGMOD 0.00026795977
834 Learning Linear Regression Models over Factorized Joins 2016 SIGMOD 0.00016135159
1,056 The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates 2017 SIGMOD 0.0001441128
1,328 Hypertree Decompositions: Questions and Answers 2016 PODS 0.00012565612
1,442 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00011956109
1,532 Data Management in Machine Learning: Challenges, Techniques, and Systems 2017 SIGMOD 0.00011472681
1,953 Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows 2018 VLDB 9.9665955e-05
2,169 AJAR: Aggregations and Joins over Annotated Relations 2016 PODS 9.3845975e-05
2,275 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 9.1262202e-05
2,907 Convergence of Datalog over (Pre-) Semirings 2022 PODS 7.933806e-05
3,006 On Functional Aggregate Queries with Additive Inequalities 2019 PODS 7.7299363e-05
3,277 A Layered Aggregate Engine for Analytics Workloads 2019 SIGMOD 7.2871625e-05
3,307 Attacking Diophantus: Solving a Special Case of Bag Containment 2019 PODS 7.2431594e-05
3,715 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 6.8220943e-05
3,781 Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries 2020 PODS 6.7723513e-05
4,197 Incremental View Maintenance with Triple Lock Factorization Benefits 2018 SIGMOD 6.367895e-05
4,505 SPOOF: Sum-Product Optimization and Operator Fusion for Large-Scale Machine Learning 2017 CIDR 6.1327108e-05
4,787 The Relational Data Borg is Learning 2020 VLDB 5.9224501e-05
4,833 MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions 2019 SIGMOD 5.8916346e-05
5,077 HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings 2019 PODS 5.7153846e-05
5,104 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 5.6946113e-05
5,487 SPORES: Sum-Product Optimization via Relational Equality Saturation for Large Scale Linear Algebra 2020 VLDB 5.4791501e-05
5,639 Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins 2021 PODS 5.393897e-05
5,821 Tensor Relational Algebra for Distributed Machine Learning System Design 2021 VLDB 5.3134851e-05
5,828 Topology Dependent Bounds For FAQs 2019 PODS 5.3113542e-05
5,855 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 5.3006096e-05
5,992 Evaluating Datalog over Semirings: A Grounding-based Approach 2024 PODS 5.2415551e-05
5,994 A Query Language Perspective on Graph Learning 2023 PODS 5.2415551e-05
6,077 The Fast and the Private: Task-based Dataset Search 2024 CIDR 5.2229324e-05
7,017 Query Evaluation by Circuits 2022 PODS 4.8603097e-05
7,076 Mining Approximate Acyclic Schemes from Relations 2020 SIGMOD 4.8426354e-05
7,162 Computing the Difference of Conjunctive Queries Efficiently 2023 SIGMOD 4.8132423e-05
7,166 Ranked Enumeration of Join Queries with Projections 2022 VLDB 4.8124491e-05
7,467 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 4.7218691e-05
7,491 Saibot: A Differentially Private Data Search Platform 2023 VLDB 4.7180617e-05
7,579 A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries 2022 PODS 4.706055e-05
7,761 Space-Time Tradeoffs for Conjunctive Queries with Access Patterns 2023 PODS 4.658708e-05
7,920 JoinBoost: Grow Trees Over Normalized Data Using Only SQL 2023 VLDB 4.6163888e-05
8,034 Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores 2025 VLDB 4.6010599e-05
8,061 Efficient Computation of Quantiles over Joins 2023 PODS 4.5943269e-05
8,279 Galley: Modern Query Optimization for Sparse Tensor Programs 2025 SIGMOD 4.5435639e-05
8,437 Insert-Only versus Insert-Delete in Dynamic Query Evaluation 2024 PODS 4.5138778e-05
8,589 Output-Optimal Algorithms for Join-Aggregate Queries 2025 PODS 4.4897014e-05
8,966 Output-sensitive Conjunctive Query Evaluation 2024 PODS 4.4193184e-05
9,089 Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs 2024 SIGMOD 4.39898e-05
9,744 Output-Sensitive Evaluation of Regular Path Queries 2025 PODS 4.2897489e-05
9,798 Threshold Queries in Theory and in the Wild 2022 VLDB 4.2818172e-05
9,877 Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation 2025 VLDB 4.2656547e-05
9,986 Database Research needs an Abstract Relational Query Language 2026 CIDR 4.1945683e-05
10,009 The Space-Time Complexity of Sum-Product Queries 2026 PODS 4.1945683e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank Cited Paper Year Venue Pagerank
502 Worst-case Optimal Join Algorithms 2012 PODS 0.00021526612
613 Design and Implementation of the LogicBlox System 2015 SIGMOD 0.00019181325
1,238 Incremental Query Evaluation in a Ring of Databases 2010 PODS 0.00013114581
1,259 Aggregation and Ordering in Factorised Databases 2013 VLDB 0.00012995821
1,557 Beyond Worst-case Analysis for Joins with Minesweeper 2014 PODS 0.00011392493
2,015 Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width 2001 PODS 9.7901938e-05
2,063 Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability 2014 PODS 9.6447857e-05
2,296 Joins via Geometric Resolutions: Worst-case and Beyond 2015 PODS 9.0776226e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
8,132 Counting Database Repairs Entailing a Query: The Case of Functional Dependencies 2022 PODS 4.5784634e-05
3,324 On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information 2006 PODS 7.2213002e-05
7,560 Complete Approximations of Incomplete Queries 2013 VLDB 4.7102455e-05
9,741 Containment of Conjunctive Object Meta-Queries 2006 VLDB 4.2936538e-05
976 Answering Queries Using Limited External Query Processors 1996 PODS 0.0001489085
6,824 Computing Join Queries with Functional Dependencies 2016 PODS 4.9144789e-05
1,490 On the Decidability of Query Containment under Constraints 1998 PODS 0.00011699154
8,966 Output-sensitive Conjunctive Query Evaluation 2024 PODS 4.4193184e-05
407 Conjunctive-Query Containment and Constraint Satisfaction 1998 PODS 0.00024004562
3,006 On Functional Aggregate Queries with Additive Inequalities 2019 PODS 7.7299363e-05