Conjunctive Queries with Inequalities Under Updates

Summary: IEDyn dynamically maintains conjunctive queries with theta-joins under updates, avoiding materialization and recomputation. It generalizes Dynamic Yannakakis to theta-joins and extends acyclicity/free-connexity, achieving two orders of magnitude gains. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h774b8654734ad51c
Venue: VLDB
Year: 2018
Pagerank: 6.2330027e-05
Overall Rank: 5,170 | 65.35%
DOI: 10.14778/3192965.3192966

Incoming Non-self Citations Over Time

Authors

1. Muhammad Idris (Technical University of Dresden; Université Libre de Bruxelles)
2. Martín Ugarte (Université Libre de Bruxelles)
3. Stijn Vansummeren (Université Libre de Bruxelles)
4. Hannes Voigt (Technical University of Dresden)
5. Wolfgang Lehner (Technical University of Dresden)

BibTeX Citation

@article{idris_vldb18,
        title = {{Conjunctive Queries with Inequalities Under Updates}},
        author = {Idris, Muhammad and Ugarte, Martín and Vansummeren, Stijn and Voigt, Hannes and Lehner, Wolfgang},
        journal = {PVLDB},
        series = {{VLDB} '18},
        volume = {11},
        number = {7},
        pages = {733--745},
        doi = {10.14778/3192965.3192966},
        url = {https://doi.org/10.14778/3192965.3192966},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
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
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
10,048	Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration	2021	PODS	5.0786422e-05
10,465	Towards Parameterized Hardness on Maintaining Conjunctive Queries	2026	PODS	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
210	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00024910589
220	An Evaluation of Non-Equijoin Algorithms	1991	VLDB	0.00024275691
241	High-Performance Complex Event Processing over Streams	2006	SIGMOD	0.00023332645
408	DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views	2012	VLDB	0.00018836656
522	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.00016893112
582	Efficient Pattern Matching over Event Streams	2008	SIGMOD	0.00016025959
639	Answering Conjunctive Queries under Updates	2017	PODS	0.00015289346
815	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00013682594
848	Aggregation and Ordering in Factorised Databases	2013	VLDB	0.00013463236
979	Incremental Query Evaluation in a Ring of Databases	2010	PODS	0.00012697012
1,034	ZStream: A Cost-based Query Processor for Adaptively Detecting Composite Events	2009	SIGMOD	0.00012370157
1,586	On Complexity and Optimization of Expensive Queries in Complex Event Processing	2014	SIGMOD	0.0001012531
2,949	Cayuga: A High-Performance Event Processing Engine	2007	SIGMOD	7.8084129e-05
3,122	Incremental View Maintenance with Triple Lock Factorization Benefits	2018	SIGMOD	7.6091671e-05
3,138	How to Win a Hot Dog Eating Contest: Distributed Incremental View Maintenance with Batch Updates	2016	SIGMOD	7.5866991e-05
4,350	Joining Interval Data in Relational Databases	2004	SIGMOD	6.6363233e-05
9,643	Processing Inequality Queries Based on Generalized Semi-Joins	1984	VLDB	5.1336732e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,826	Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores	2025	VLDB
2	6,211	Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited	1989	SIGMOD
3	10,072	Towards Update-Dependent Analysis of Query Maintenance	2025	PODS
4	10,620	Approximate Query Processing under Updates	2026	SIGMOD
5	5,506	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB
6	5,911	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD
7	6,900	Insert-Only versus Insert-Delete in Dynamic Query Evaluation	2024	PODS
8	6,585	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS
9	6,482	Output-sensitive Conjunctive Query Evaluation	2024	PODS
10	815	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD