LinCQA: Faster Consistent Query Answering with Linear Time Guarantees

Summary: Identifies a class of acyclic SPJ queries where CQA has SQL rewritings with linear-time guarantees. Extends Yannakakis' acyclic-join approach to inconsistent data; LinCQA outputs SQL and non-recursive Datalog with negation, speedups over prior CQA systems. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6541
Venue: SIGMOD
Year: 2023
Pagerank: 4.1945683e-05
Overall Rank: 11,178 | 22.24%
DOI: 10.1145/3588718

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,899	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS	4.1945683e-05
10,928	Computing Range Consistent Answers to Aggregation Queries via Rewriting	2024	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 24 of 24 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
49	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00067660624
192	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00035728858
678	ConQuer: Efficient Management of Inconsistent Databases	2005	SIGMOD	0.00018253213
791	ActiveClean: Interactive Data Cleaning For Statistical Modeling	2016	VLDB	0.00016629664
1,197	The LLUNATIC Data-Cleaning Framework	2013	VLDB	0.00013390321
1,546	KATARA: A Data Cleaning System Powered by Knowledge Bases and Crowdsourcing	2015	SIGMOD	0.00011446851
1,627	Data Cleaning: Overview and Emerging Challenges	2016	SIGMOD	0.00011086905
2,243	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.2166927e-05
2,302	Nearest Neighbor Classifiers over Incomplete Information: From Certain Answers to Certain Predictions	2021	VLDB	9.0668832e-05
2,460	Combining Quantitative and Logical Data Cleaning	2016	VLDB	8.7617484e-05
2,566	Database Repairs and Consistent Query Answering: Origins and Further Developments	2019	PODS	8.5243847e-05
2,638	Messing Up with BART: Error Generation for Evaluating Data-Cleaning Algorithms	2016	VLDB	8.399764e-05
2,797	Query-Oriented Data Cleaning with Oracles	2015	SIGMOD	8.1108589e-05
2,946	BigDansing: A System for Big Data Cleansing	2015	SIGMOD	7.8372441e-05
3,478	Transform-Data-by-Example (TDE): An Extensible Search Engine for Data Transformations	2018	VLDB	7.054159e-05
3,524	Efficient Querying of Inconsistent Databases with Binary Integer Programming	2013	VLDB	7.0087032e-05
5,153	Horizon: Scalable Dependency-driven Data Cleaning	2021	VLDB	5.6607963e-05
5,537	Cleaning Uncertain Data with Quality Guarantees	2008	VLDB	5.4522327e-05
6,350	NADEEF: A Generalized Data Cleaning System	2013	VLDB	5.101815e-05
6,739	Benchmarking Approximate Consistent Query Answering	2021	PODS	4.9449088e-05
7,063	On the First-order Expressibility of Computing Certain Answers to Conjunctive Queries over Uncertain Databases	2010	PODS	4.8461152e-05
7,069	Consistent Query Answering for Primary Keys on Path Queries	2021	PODS	4.8438319e-05
8,007	A Grammar-based Entity Representation Framework for Data Cleaning	2009	SIGMOD	4.6068018e-05
8,970	First-Order Rewritability in Consistent Query Answering with Respect to Multiple Keys	2020	PODS	4.4188963e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,462	INCA: Inconsistency-Aware Data Profiling and Querying	2021	SIGMOD	4.1945683e-05
8,966	Output-sensitive Conjunctive Query Evaluation	2024	PODS	4.4193184e-05
9,748	Combined Approximations for Uniform Operational Consistent Query Answering	2024	PODS	4.2897489e-05
6,705	Consistent Query Answers in Inconsistent Probabilistic Databases	2010	SIGMOD	4.9549359e-05
10,899	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS	4.1945683e-05
7,703	Uniform Operational Consistent Query Answering	2022	PODS	4.673644e-05
7,069	Consistent Query Answering for Primary Keys on Path Queries	2021	PODS	4.8438319e-05
9,250	CAvSAT: Answering Aggregation Queries over Inconsistent Databases via SAT Solving	2021	SIGMOD	4.3690661e-05
6,739	Benchmarking Approximate Consistent Query Answering	2021	PODS	4.9449088e-05
8,166	CAvSAT: A System for Query Answering over Inconsistent Databases	2019	SIGMOD	4.5712945e-05