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.00013682594
Overall Rank
815 | 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,526 On the Enumeration Complexity of Unions of Conjunctive Queries 2019 PODS 8.3274934e-05
2,766 Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration 2020 PODS 8.0221503e-05
3,122 Incremental View Maintenance with Triple Lock Factorization Benefits 2018 SIGMOD 7.6091671e-05
3,165 Robust Join Processing with Diamond Hardened Joins 2024 VLDB 7.5598778e-05
3,199 Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries 2020 PODS 7.5261206e-05
3,684 DBSP: Automatic Incremental View Maintenance for Rich Query Languages 2023 VLDB 7.0834345e-05
5,080 Change Propagation Without Joins 2023 VLDB 6.2689958e-05
5,170 Conjunctive Queries with Inequalities Under Updates 2018 VLDB 6.2330027e-05
5,574 Representing Paths in Graph Database Pattern Matching 2023 VLDB 6.0628579e-05
5,911 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 5.9338021e-05
5,995 An In-Depth Study of Continuous Subgraph Matching 2022 VLDB 5.903845e-05
6,397 Maintaining Acyclic Foreign-Key Joins under Updates 2020 SIGMOD 5.7822506e-05
6,579 Fast Matrix Multiplication for Query Processing 2024 PODS 5.7252637e-05
6,585 Output-Optimal Algorithms for Join-Aggregate Queries 2025 PODS 5.7238683e-05
6,807 Intermittent Query Processing 2019 VLDB 5.661199e-05
6,826 Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores 2025 VLDB 5.6566963e-05
6,882 Computing Complex Temporal Join Queries Efficiently 2022 SIGMOD 5.6412354e-05
6,900 Insert-Only versus Insert-Delete in Dynamic Query Evaluation 2024 PODS 5.6372471e-05
7,361 Space-Time Tradeoffs for Conjunctive Queries with Access Patterns 2023 PODS 5.528228e-05
7,490 Reservoir Sampling over Joins 2024 SIGMOD 5.499011e-05
7,550 Foreign Keys Open the Door for Faster Incremental View Maintenance 2023 SIGMOD 5.4809422e-05
7,741 Resource-efficient Shared Query Execution via Exploiting Time Slackness 2021 SIGMOD 5.4469162e-05
7,936 Avoiding Materialisation for Guarded Aggregate Queries 2025 VLDB 5.4070923e-05
8,154 Thrifty Query Execution via Incrementability 2020 SIGMOD 5.3732833e-05
8,585 Efficient Incrementialization of Correlated Nested Aggregate Queries using Relative Partial Aggregate Indexes (RPAI) 2022 SIGMOD 5.2943199e-05
8,855 Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration 2020 PODS 5.2486885e-05
8,859 On Reporting Durable Patterns in Temporal Proximity Graphs 2024 PODS 5.2481795e-05
9,114 Efficient Enumeration for Annotated Grammars 2022 PODS 5.208561e-05
9,398 Complex Event Recognition meets Hierarchical Conjunctive Queries 2024 PODS 5.1672232e-05
9,530 REmatch: a novel regex engine for finding all matches 2023 VLDB 5.151324e-05
10,048 Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration 2021 PODS 5.0786422e-05
10,072 Towards Update-Dependent Analysis of Query Maintenance 2025 PODS 5.0732737e-05
10,101 TC-Match: Fast Time-constrained Continuous Subgraph Matching 2024 VLDB 5.068372e-05
10,175 Cquirrel: Continuous Query Processing over Acyclic Relational Schemas 2021 VLDB 5.0559291e-05
10,192 Threshold Queries in Theory and in the Wild 2022 VLDB 5.052396e-05
10,333 MAVIS: Materialized View for Subgraph Matching 2026 SIGMOD 5.0225409e-05
10,455 Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations 2026 PODS 4.9605343e-05
10,465 Towards Parameterized Hardness on Maintaining Conjunctive Queries 2026 PODS 4.9605343e-05
10,477 Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries 2026 PODS 4.9605343e-05
10,620 Approximate Query Processing under Updates 2026 SIGMOD 4.9605343e-05
10,630 Continuous Subgraph Matching via Cost-Model-based Dynamic Vertex Dominance Embeddings 2026 SIGMOD 4.9605343e-05
10,689 An Extensive Experimental Study of Indexes in Continuous Subgraph Matching:[Experiments & Analysis] 2026 SIGMOD 4.9605343e-05
10,955 Storing and Indexing Multiple Tables by Interesting Orderings: For Efficient Joins, Groupings, and Updates in Relational Databases 2026 VLDB 4.9605343e-05
11,097 Instance-Optimal Acyclic Joins: From Theory to Systems 2026 VLDB 4.9605343e-05
11,253 Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized 2025 SIGMOD 4.9605343e-05
11,581 Relational Algorithms for Top-k Query Evaluation 2024 SIGMOD 4.9605343e-05
11,785 Lightweight Materialization for Fast Dashboards Over Joins 2023 SIGMOD 4.9605343e-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