DBScholar

Back to papers

The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates

Summary: Dyn, a dynamic Yannakakis variant, yields DCLR for free-connex acyclic CQs, avoiding materialization. Optimal for its class: linear-space, linear-time updates, constant-delay output, constant-time lookups; experiments on TPC-H/DS favor Dyn vs HIVM. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
5465
Venue
SIGMOD
Year
2017
Pagerank
0.00013827772
Overall Rank
816 | 94.41%
DOI
10.1145/3035918.3064027

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{idris_sigmod17,
        title = {{The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates}},
        author = {Idris, Muhammad and Ugarte, Martín and Vansummeren, Stijn},
        series = {{SIGMOD} '17},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3035918.3064027},
        url = {https://dl.acm.org/doi/10.1145/3035918.3064027},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 45 of 45 citing papers.

Rank Citing Paper Year Venue Pagerank
2,468 On the Enumeration Complexity of Unions of Conjunctive Queries 2019 PODS 8.5358494e-05
2,777 Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration 2020 PODS 8.1352657e-05
3,136 Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries 2020 PODS 7.7210541e-05
3,206 Incremental View Maintenance with Triple Lock Factorization Benefits 2018 SIGMOD 7.6367549e-05
3,622 Robust Join Processing with Diamond Hardened Joins 2024 VLDB 7.2465862e-05
4,865 DBSP: Automatic Incremental View Maintenance for Rich Query Languages 2023 VLDB 6.4731692e-05
4,985 Change Propagation Without Joins 2023 VLDB 6.412102e-05
5,066 Conjunctive Queries with Inequalities Under Updates 2018 VLDB 6.3771079e-05
5,418 Representing Paths in Graph Database Pattern Matching 2023 VLDB 6.2255373e-05
5,870 An In-Depth Study of Continuous Subgraph Matching 2022 VLDB 6.061038e-05
6,332 Maintaining Acyclic Foreign-Key Joins under Updates 2020 SIGMOD 5.9107433e-05
6,434 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 5.8799421e-05
6,444 Output-Optimal Algorithms for Join-Aggregate Queries 2025 PODS 5.8774519e-05
6,732 Insert-Only versus Insert-Delete in Dynamic Query Evaluation 2024 PODS 5.7885064e-05
6,885 Fast Matrix Multiplication for Query Processing 2024 PODS 5.7464502e-05
7,195 Space-Time Tradeoffs for Conjunctive Queries with Access Patterns 2023 PODS 5.6765621e-05
7,200 Intermittent Query Processing 2019 VLDB 5.6756294e-05
7,335 Reservoir Sampling over Joins 2024 SIGMOD 5.64193e-05
7,386 Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores 2025 VLDB 5.6273882e-05
7,579 Resource-efficient Shared Query Execution via Exploiting Time Slackness 2021 SIGMOD 5.592546e-05
7,967 Thrifty Query Execution via Incrementability 2020 SIGMOD 5.5169373e-05
8,181 Foreign Keys Open the Door for Faster Incremental View Maintenance 2023 SIGMOD 5.4721346e-05
8,235 Computing Complex Temporal Join Queries Efficiently 2022 SIGMOD 5.4608734e-05
8,571 Efficient Incrementialization of Correlated Nested Aggregate Queries using Relative Partial Aggregate Indexes (RPAI) 2022 SIGMOD 5.4102496e-05
8,673 Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration 2020 PODS 5.3872753e-05
8,691 On Reporting Durable Patterns in Temporal Proximity Graphs 2024 PODS 5.3839057e-05
8,924 Efficient Enumeration for Annotated Grammars 2022 PODS 5.3483178e-05
9,184 Complex Event Recognition meets Hierarchical Conjunctive Queries 2024 PODS 5.3058708e-05
9,312 REmatch: a novel regex engine for finding all matches 2023 VLDB 5.289545e-05
9,720 Avoiding Materialisation for Guarded Aggregate Queries 2025 VLDB 5.2319816e-05
9,819 Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration 2021 PODS 5.214913e-05
9,845 Towards Update-Dependent Analysis of Query Maintenance 2025 PODS 5.2094004e-05
9,872 TC-Match: Fast Time-constrained Continuous Subgraph Matching 2024 VLDB 5.2043672e-05
9,951 Cquirrel: Continuous Query Processing over Acyclic Relational Schemas 2021 VLDB 5.1915905e-05
9,961 Threshold Queries in Theory and in the Wild 2022 VLDB 5.1879626e-05
10,084 MAVIS: Materialized View for Subgraph Matching 2026 SIGMOD 5.1573064e-05
10,160 Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations 2026 PODS 5.093636e-05
10,170 Towards Parameterized Hardness on Maintaining Conjunctive Queries 2026 PODS 5.093636e-05
10,183 Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries 2026 PODS 5.093636e-05
10,342 Approximate Query Processing under Updates 2026 SIGMOD 5.093636e-05
10,354 Continuous Subgraph Matching via Cost-Model-based Dynamic Vertex Dominance Embeddings 2026 SIGMOD 5.093636e-05
10,428 An Extensive Experimental Study of Indexes in Continuous Subgraph Matching:[Experiments & Analysis] 2026 SIGMOD 5.093636e-05
10,762 Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized 2025 SIGMOD 5.093636e-05
11,183 Relational Algorithms for Top-k Query Evaluation 2024 SIGMOD 5.093636e-05
11,421 Lightweight Materialization for Fast Dashboards Over Joins 2023 SIGMOD 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

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

Previous Page 1 / 1 Next

Semantically Similar Papers