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
hf04fd6f13d93775c
Venue
SIGMOD
Year
2017
Pagerank
0.00013722638
Overall Rank
813 | 94.54%
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 47 of 47 citing papers.

Rank Citing Paper Year Venue Pagerank
2,517 On the Enumeration Complexity of Unions of Conjunctive Queries 2019 PODS 8.3550625e-05
2,757 Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration 2020 PODS 8.0487636e-05
3,114 Incremental View Maintenance with Triple Lock Factorization Benefits 2018 SIGMOD 7.6321464e-05
3,154 Robust Join Processing with Diamond Hardened Joins 2024 VLDB 7.5849549e-05
3,188 Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries 2020 PODS 7.5510881e-05
3,675 DBSP: Automatic Incremental View Maintenance for Rich Query Languages 2023 VLDB 7.1058941e-05
5,061 Change Propagation Without Joins 2023 VLDB 6.2897936e-05
5,147 Conjunctive Queries with Inequalities Under Updates 2018 VLDB 6.2536517e-05
5,559 Representing Paths in Graph Database Pattern Matching 2023 VLDB 6.082972e-05
5,895 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 5.9534254e-05
5,984 An In-Depth Study of Continuous Subgraph Matching 2022 VLDB 5.9234316e-05
6,389 Maintaining Acyclic Foreign-Key Joins under Updates 2020 SIGMOD 5.8014043e-05
6,569 Fast Matrix Multiplication for Query Processing 2024 PODS 5.7442578e-05
6,576 Output-Optimal Algorithms for Join-Aggregate Queries 2025 PODS 5.7428578e-05
6,801 Intermittent Query Processing 2019 VLDB 5.6776677e-05
6,811 Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores 2025 VLDB 5.6754603e-05
6,881 Insert-Only versus Insert-Delete in Dynamic Query Evaluation 2024 PODS 5.6559492e-05
7,341 Space-Time Tradeoffs for Conjunctive Queries with Access Patterns 2023 PODS 5.5465684e-05
7,471 Reservoir Sampling over Joins 2024 SIGMOD 5.5172544e-05
7,533 Foreign Keys Open the Door for Faster Incremental View Maintenance 2023 SIGMOD 5.4991257e-05
7,616 Computing Complex Temporal Join Queries Efficiently 2022 SIGMOD 5.4822011e-05
7,728 Resource-efficient Shared Query Execution via Exploiting Time Slackness 2021 SIGMOD 5.4649863e-05
7,922 Avoiding Materialisation for Guarded Aggregate Queries 2025 VLDB 5.4250308e-05
8,137 Thrifty Query Execution via Incrementability 2020 SIGMOD 5.391109e-05
8,567 Efficient Incrementialization of Correlated Nested Aggregate Queries using Relative Partial Aggregate Indexes (RPAI) 2022 SIGMOD 5.3118554e-05
8,837 Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration 2020 PODS 5.2661006e-05
8,841 On Reporting Durable Patterns in Temporal Proximity Graphs 2024 PODS 5.2655908e-05
9,095 Efficient Enumeration for Annotated Grammars 2022 PODS 5.2258409e-05
9,372 Complex Event Recognition meets Hierarchical Conjunctive Queries 2024 PODS 5.1843659e-05
9,501 REmatch: a novel regex engine for finding all matches 2023 VLDB 5.168414e-05
10,012 Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration 2021 PODS 5.0954911e-05
10,033 Towards Update-Dependent Analysis of Query Maintenance 2025 PODS 5.0901047e-05
10,067 TC-Match: Fast Time-constrained Continuous Subgraph Matching 2024 VLDB 5.0851868e-05
10,138 Cquirrel: Continuous Query Processing over Acyclic Relational Schemas 2021 VLDB 5.0727027e-05
10,157 Threshold Queries in Theory and in the Wild 2022 VLDB 5.0691578e-05
10,305 MAVIS: Materialized View for Subgraph Matching 2026 SIGMOD 5.0392037e-05
10,389 Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations 2026 PODS 4.9769913e-05
10,399 Towards Parameterized Hardness on Maintaining Conjunctive Queries 2026 PODS 4.9769913e-05
10,411 Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries 2026 PODS 4.9769913e-05
10,555 Approximate Query Processing under Updates 2026 SIGMOD 4.9769913e-05
10,566 Continuous Subgraph Matching via Cost-Model-based Dynamic Vertex Dominance Embeddings 2026 SIGMOD 4.9769913e-05
10,628 An Extensive Experimental Study of Indexes in Continuous Subgraph Matching:[Experiments & Analysis] 2026 SIGMOD 4.9769913e-05
10,894 Storing and Indexing Multiple Tables by Interesting Orderings: For Efficient Joins, Groupings, and Updates in Relational Databases 2026 VLDB 4.9769913e-05
11,036 Instance-Optimal Acyclic Joins: From Theory to Systems 2026 VLDB 4.9769913e-05
11,194 Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized 2025 SIGMOD 4.9769913e-05
11,532 Relational Algorithms for Top-k Query Evaluation 2024 SIGMOD 4.9769913e-05
11,741 Lightweight Materialization for Fast Dashboards Over Joins 2023 SIGMOD 4.9769913e-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