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.00020002796
Overall Rank
564 | 96.09%
DOI
10.1145/2902251.2902280

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 65 citing papers.

Rank Citing Paper Year Venue Pagerank
341 EmptyHeaded: A Relational Engine for Graph Processing 2016 SIGMOD 0.00026850764
832 Learning Linear Regression Models over Factorized Joins 2016 SIGMOD 0.00016089705
1,054 The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates 2017 SIGMOD 0.00014397587
1,322 Hypertree Decompositions: Questions and Answers 2016 PODS 0.00012595941
1,452 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00011922523
1,534 Data Management in Machine Learning: Challenges, Techniques, and Systems 2017 SIGMOD 0.00011462072
1,948 Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows 2018 VLDB 9.9938634e-05
2,173 AJAR: Aggregations and Joins over Annotated Relations 2016 PODS 9.3767985e-05
2,281 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 9.122455e-05
2,912 Convergence of Datalog over (Pre-) Semirings 2022 PODS 7.9261665e-05
3,009 On Functional Aggregate Queries with Additive Inequalities 2019 PODS 7.7230513e-05
3,280 A Layered Aggregate Engine for Analytics Workloads 2019 SIGMOD 7.2813732e-05
3,311 Attacking Diophantus: Solving a Special Case of Bag Containment 2019 PODS 7.2361776e-05
3,702 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 6.8251643e-05
3,785 Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries 2020 PODS 6.7658346e-05
4,200 Incremental View Maintenance with Triple Lock Factorization Benefits 2018 SIGMOD 6.3618329e-05
4,508 SPOOF: Sum-Product Optimization and Operator Fusion for Large-Scale Machine Learning 2017 CIDR 6.1261819e-05
4,787 The Relational Data Borg is Learning 2020 VLDB 5.9168117e-05
4,835 MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions 2019 SIGMOD 5.8861112e-05
5,076 HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings 2019 PODS 5.709895e-05
5,085 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 5.7040225e-05
5,497 SPORES: Sum-Product Optimization via Relational Equality Saturation for Large Scale Linear Algebra 2020 VLDB 5.4741034e-05
5,650 Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins 2021 PODS 5.3887172e-05
5,836 Tensor Relational Algebra for Distributed Machine Learning System Design 2021 VLDB 5.3079723e-05
5,840 Topology Dependent Bounds For FAQs 2019 PODS 5.3062554e-05
5,845 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 5.3057391e-05
5,996 Evaluating Datalog over Semirings: A Grounding-based Approach 2024 PODS 5.2365238e-05
5,998 A Query Language Perspective on Graph Learning 2023 PODS 5.2365238e-05
6,081 The Fast and the Private: Task-based Dataset Search 2024 CIDR 5.2179192e-05
7,017 Query Evaluation by Circuits 2022 PODS 4.8556471e-05
7,073 Mining Approximate Acyclic Schemes from Relations 2020 SIGMOD 4.8378353e-05
7,161 Computing the Difference of Conjunctive Queries Efficiently 2023 SIGMOD 4.8086254e-05
7,165 Ranked Enumeration of Join Queries with Projections 2022 VLDB 4.807833e-05
7,465 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 4.7186055e-05
7,490 Saibot: A Differentially Private Data Search Platform 2023 VLDB 4.7135369e-05
7,584 A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries 2022 PODS 4.7015411e-05
7,762 Space-Time Tradeoffs for Conjunctive Queries with Access Patterns 2023 PODS 4.6542406e-05
7,920 JoinBoost: Grow Trees Over Normalized Data Using Only SQL 2023 VLDB 4.6120304e-05
8,035 Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores 2025 VLDB 4.5967078e-05
8,065 Efficient Computation of Quantiles over Joins 2023 PODS 4.5899218e-05
8,274 Galley: Modern Query Optimization for Sparse Tensor Programs 2025 SIGMOD 4.5392079e-05
8,428 Insert-Only versus Insert-Delete in Dynamic Query Evaluation 2024 PODS 4.5095504e-05
8,587 Output-Optimal Algorithms for Join-Aggregate Queries 2025 PODS 4.4853975e-05
8,972 Output-sensitive Conjunctive Query Evaluation 2024 PODS 4.4150824e-05
9,086 Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs 2024 SIGMOD 4.3947639e-05
9,743 Output-Sensitive Evaluation of Regular Path Queries 2025 PODS 4.2856385e-05
9,801 Threshold Queries in Theory and in the Wild 2022 VLDB 4.2777144e-05
9,876 Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation 2025 VLDB 4.2615675e-05
9,985 Database Research needs an Abstract Relational Query Language 2026 CIDR 4.1905499e-05
10,007 Query Answering Under Volume-Based Diversity Functions 2026 PODS 4.1905499e-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
503 Worst-case Optimal Join Algorithms 2012 PODS 0.00021517145
610 Design and Implementation of the LogicBlox System 2015 SIGMOD 0.00019204048
1,231 Incremental Query Evaluation in a Ring of Databases 2010 PODS 0.00013141213
1,255 Aggregation and Ordering in Factorised Databases 2013 VLDB 0.00013011216
1,556 Beyond Worst-case Analysis for Joins with Minesweeper 2014 PODS 0.00011383141
2,007 Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width 2001 PODS 9.8123766e-05
2,057 Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability 2014 PODS 9.665853e-05
2,298 Joins via Geometric Resolutions: Worst-case and Beyond 2015 PODS 9.0746479e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,325 On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information 2006 PODS 7.2149375e-05
8,134 Counting Database Repairs Entailing a Query: The Case of Functional Dependencies 2022 PODS 4.5740737e-05
7,561 Complete Approximations of Incomplete Queries 2013 VLDB 4.7057229e-05
9,740 Containment of Conjunctive Object Meta-Queries 2006 VLDB 4.2895392e-05
976 Answering Queries Using Limited External Query Processors 1996 PODS 0.00014877501
6,822 Computing Join Queries with Functional Dependencies 2016 PODS 4.9101655e-05
1,489 On the Decidability of Query Containment under Constraints 1998 PODS 0.00011687823
8,972 Output-sensitive Conjunctive Query Evaluation 2024 PODS 4.4150824e-05
401 Conjunctive-Query Containment and Constraint Satisfaction 1998 PODS 0.00024281448
3,009 On Functional Aggregate Queries with Additive Inequalities 2019 PODS 7.7230513e-05