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: 6542
Venue: SIGMOD
Year: 2023
Pagerank: 4.1905499e-05
Overall Rank: 11,181 | 22.30%
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,903	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS	4.1905499e-05
10,931	Computing Range Consistent Answers to Aggregation Queries via Rewriting	2024	PODS	4.1905499e-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.00067607389
192	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00035692958
677	ConQuer: Efficient Management of Inconsistent Databases	2005	SIGMOD	0.00018250681
788	ActiveClean: Interactive Data Cleaning For Statistical Modeling	2016	VLDB	0.00016618698
1,197	The LLUNATIC Data-Cleaning Framework	2013	VLDB	0.00013373177
1,544	KATARA: A Data Cleaning System Powered by Knowledge Bases and Crowdsourcing	2015	SIGMOD	0.00011438274
1,629	Data Cleaning: Overview and Emerging Challenges	2016	SIGMOD	0.00011073148
2,246	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.2039096e-05
2,308	Nearest Neighbor Classifiers over Incomplete Information: From Certain Answers to Certain Predictions	2021	VLDB	9.0634287e-05
2,417	Combining Quantitative and Logical Data Cleaning	2016	VLDB	8.8502556e-05
2,574	Database Repairs and Consistent Query Answering: Origins and Further Developments	2019	PODS	8.5126812e-05
2,642	Messing Up with BART: Error Generation for Evaluating Data-Cleaning Algorithms	2016	VLDB	8.3925184e-05
2,805	Query-Oriented Data Cleaning with Oracles	2015	SIGMOD	8.103731e-05
3,000	BigDansing: A System for Big Data Cleansing	2015	SIGMOD	7.7447724e-05
3,483	Transform-Data-by-Example (TDE): An Extensible Search Engine for Data Transformations	2018	VLDB	7.0493668e-05
3,531	Efficient Querying of Inconsistent Databases with Binary Integer Programming	2013	VLDB	6.9982256e-05
5,150	Horizon: Scalable Dependency-driven Data Cleaning	2021	VLDB	5.6553571e-05
5,545	Cleaning Uncertain Data with Quality Guarantees	2008	VLDB	5.447418e-05
6,348	NADEEF: A Generalized Data Cleaning System	2013	VLDB	5.0969173e-05
6,740	Benchmarking Approximate Consistent Query Answering	2021	PODS	4.9401646e-05
7,058	On the First-order Expressibility of Computing Certain Answers to Conjunctive Queries over Uncertain Databases	2010	PODS	4.8412176e-05
7,064	Consistent Query Answering for Primary Keys on Path Queries	2021	PODS	4.8391823e-05
8,002	A Grammar-based Entity Representation Framework for Data Cleaning	2009	SIGMOD	4.60503e-05
8,976	First-Order Rewritability in Consistent Query Answering with Respect to Multiple Keys	2020	PODS	4.4146601e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,465	INCA: Inconsistency-Aware Data Profiling and Querying	2021	SIGMOD	4.1905499e-05
8,972	Output-sensitive Conjunctive Query Evaluation	2024	PODS	4.4150824e-05
9,747	Combined Approximations for Uniform Operational Consistent Query Answering	2024	PODS	4.2856385e-05
6,707	Consistent Query Answers in Inconsistent Probabilistic Databases	2010	SIGMOD	4.9500448e-05
10,903	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS	4.1905499e-05
7,700	Uniform Operational Consistent Query Answering	2022	PODS	4.6691622e-05
7,064	Consistent Query Answering for Primary Keys on Path Queries	2021	PODS	4.8391823e-05
9,257	CAvSAT: Answering Aggregation Queries over Inconsistent Databases via SAT Solving	2021	SIGMOD	4.3648789e-05
6,740	Benchmarking Approximate Consistent Query Answering	2021	PODS	4.9401646e-05
8,176	CAvSAT: A System for Query Answering over Inconsistent Databases	2019	SIGMOD	4.5634257e-05