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.00013729015
Overall Rank
812 | 94.55%
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.3589894e-05
2,757 Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration 2020 PODS 8.0525756e-05
3,112 Incremental View Maintenance with Triple Lock Factorization Benefits 2018 SIGMOD 7.6357579e-05
3,153 Robust Join Processing with Diamond Hardened Joins 2024 VLDB 7.5883271e-05
3,187 Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries 2020 PODS 7.5546613e-05
3,673 DBSP: Automatic Incremental View Maintenance for Rich Query Languages 2023 VLDB 7.1092596e-05
5,057 Change Propagation Without Joins 2023 VLDB 6.2927647e-05
5,145 Conjunctive Queries with Inequalities Under Updates 2018 VLDB 6.2566119e-05
5,557 Representing Paths in Graph Database Pattern Matching 2023 VLDB 6.085853e-05
5,902 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 5.9536872e-05
5,984 An In-Depth Study of Continuous Subgraph Matching 2022 VLDB 5.926237e-05
6,386 Maintaining Acyclic Foreign-Key Joins under Updates 2020 SIGMOD 5.8040725e-05
6,567 Fast Matrix Multiplication for Query Processing 2024 PODS 5.7469783e-05
6,573 Output-Optimal Algorithms for Join-Aggregate Queries 2025 PODS 5.7455776e-05
6,796 Intermittent Query Processing 2019 VLDB 5.6803529e-05
6,805 Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores 2025 VLDB 5.6780394e-05
6,876 Insert-Only versus Insert-Delete in Dynamic Query Evaluation 2024 PODS 5.6586279e-05
7,338 Space-Time Tradeoffs for Conjunctive Queries with Access Patterns 2023 PODS 5.5491953e-05
7,467 Reservoir Sampling over Joins 2024 SIGMOD 5.5198675e-05
7,542 Foreign Keys Open the Door for Faster Incremental View Maintenance 2023 SIGMOD 5.4986181e-05
7,609 Computing Complex Temporal Join Queries Efficiently 2022 SIGMOD 5.4847975e-05
7,722 Resource-efficient Shared Query Execution via Exploiting Time Slackness 2021 SIGMOD 5.467573e-05
7,917 Avoiding Materialisation for Guarded Aggregate Queries 2025 VLDB 5.4276002e-05
8,131 Thrifty Query Execution via Incrementability 2020 SIGMOD 5.3936608e-05
8,560 Efficient Incrementialization of Correlated Nested Aggregate Queries using Relative Partial Aggregate Indexes (RPAI) 2022 SIGMOD 5.3142933e-05
8,828 Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration 2020 PODS 5.2685945e-05
8,832 On Reporting Durable Patterns in Temporal Proximity Graphs 2024 PODS 5.2680847e-05
9,085 Efficient Enumeration for Annotated Grammars 2022 PODS 5.2283159e-05
9,363 Complex Event Recognition meets Hierarchical Conjunctive Queries 2024 PODS 5.1868213e-05
9,490 REmatch: a novel regex engine for finding all matches 2023 VLDB 5.1708619e-05
10,007 Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration 2021 PODS 5.0979044e-05
10,028 Towards Update-Dependent Analysis of Query Maintenance 2025 PODS 5.0925155e-05
10,062 TC-Match: Fast Time-constrained Continuous Subgraph Matching 2024 VLDB 5.0875952e-05
10,134 Cquirrel: Continuous Query Processing over Acyclic Relational Schemas 2021 VLDB 5.0751052e-05
10,153 Threshold Queries in Theory and in the Wild 2022 VLDB 5.0715586e-05
10,300 MAVIS: Materialized View for Subgraph Matching 2026 SIGMOD 5.0415903e-05
10,377 Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations 2026 PODS 4.9793485e-05
10,387 Towards Parameterized Hardness on Maintaining Conjunctive Queries 2026 PODS 4.9793485e-05
10,399 Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries 2026 PODS 4.9793485e-05
10,544 Approximate Query Processing under Updates 2026 SIGMOD 4.9793485e-05
10,555 Continuous Subgraph Matching via Cost-Model-based Dynamic Vertex Dominance Embeddings 2026 SIGMOD 4.9793485e-05
10,617 An Extensive Experimental Study of Indexes in Continuous Subgraph Matching:[Experiments & Analysis] 2026 SIGMOD 4.9793485e-05
10,885 Storing and Indexing Multiple Tables by Interesting Orderings: For Efficient Joins, Groupings, and Updates in Relational Databases 2026 VLDB 4.9793485e-05
11,027 Instance-Optimal Acyclic Joins: From Theory to Systems 2026 VLDB 4.9793485e-05
11,185 Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized 2025 SIGMOD 4.9793485e-05
11,526 Relational Algorithms for Top-k Query Evaluation 2024 SIGMOD 4.9793485e-05
11,735 Lightweight Materialization for Fast Dashboards Over Joins 2023 SIGMOD 4.9793485e-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