Learning and Verifying Quantified Boolean Queries by Example

Summary: Analyzes membership-query complexity for learning and verifying qhorn — conjunctions of quantified Horn expressions — via answer/non-answer questions. Presents optimal polynomial-time and polynomial-question algorithms for two qhorn subclasses under constant-bounded causal density. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1603
Venue: PODS
Year: 2013
Pagerank: 8.1725194e-05
Overall Rank: 2,751 | 80.89%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,507	Overview of Data Exploration Techniques	2015	SIGMOD	0.00011594294
2,100	Predictive Interaction for Data Transformation	2015	CIDR	9.5410186e-05
3,076	Explore-by-Example: An Automatic Query Steering Framework for Interactive Data Exploration	2014	SIGMOD	7.6063803e-05
3,662	Example-Driven Query Intent Discovery: Abductive Reasoning using Semantic Similarity	2019	VLDB	6.8647421e-05
4,636	Reverse Engineering SPJ-Queries from Examples	2017	PODS	6.0270157e-05
4,755	Optimization for Active Learning-based Interactive Database Exploration	2019	VLDB	5.9375171e-05
5,209	Interactive Mapping Specification with Exemplar Tuples	2017	SIGMOD	5.6245587e-05
7,663	Schema Independent Relational Learning	2017	SIGMOD	4.6812239e-05
7,868	Learning Over Dirty Data Without Cleaning	2020	SIGMOD	4.6276013e-05
9,072	DataDiff: User-Interpretable Data Transformation Summaries for Collaborative Data Analysis	2018	SIGMOD	4.3975844e-05
9,695	The Data Interaction Game	2018	SIGMOD	4.298211e-05
9,885	Scalable and Usable Relational Learning With Automatic Language Bias	2021	SIGMOD	4.2580321e-05
11,325	On the Parameterized Complexity of Learning First-Order Logic	2022	PODS	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
491	Query by Output	2009	SIGMOD	0.00021960753

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,005	Counting Answers to Existential Positive Queries: A Complexity Classification	2016	PODS	7.7315492e-05
3,678	Providing Better Support for a Class of Decision Support Queries	1996	SIGMOD	6.8482668e-05
6,273	Determinacy of Real Conjunctive Queries. The Boolean Case	2022	PODS	5.1270241e-05
401	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00024281448
12,364	Query Evaluation with Soft-Key Constraints	2008	PODS	4.1905499e-05
14,275	On Analogical Query Processing in Logic Database	1986	VLDB	-
10,903	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS	4.1905499e-05
12,892	Learning Efficient Query Processing Strategies	1992	PODS	4.1905499e-05
6,094	Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited	1989	SIGMOD	5.2099705e-05
4,722	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	5.9646931e-05