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.176296e-05
Overall Rank: 2,750 | 80.88%
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,552	Overview of Data Exploration Techniques	2015	SIGMOD	0.00011408814
2,097	Predictive Interaction for Data Transformation	2015	CIDR	9.5489822e-05
3,070	Explore-by-Example: An Automatic Query Steering Framework for Interactive Data Exploration	2014	SIGMOD	7.6137064e-05
3,661	Example-Driven Query Intent Discovery: Abductive Reasoning using Semantic Similarity	2019	VLDB	6.8689912e-05
4,636	Reverse Engineering SPJ-Queries from Examples	2017	PODS	6.0303761e-05
4,758	Optimization for Active Learning-based Interactive Database Exploration	2019	VLDB	5.9422515e-05
5,208	Interactive Mapping Specification with Exemplar Tuples	2017	SIGMOD	5.6296265e-05
7,664	Schema Independent Relational Learning	2017	SIGMOD	4.6857329e-05
7,867	Learning Over Dirty Data Without Cleaning	2020	SIGMOD	4.6320452e-05
9,076	DataDiff: User-Interpretable Data Transformation Summaries for Collaborative Data Analysis	2018	SIGMOD	4.401804e-05
9,696	The Data Interaction Game	2018	SIGMOD	4.3023337e-05
9,886	Scalable and Usable Relational Learning With Automatic Language Bias	2021	SIGMOD	4.2621158e-05
11,323	On the Parameterized Complexity of Learning First-Order Logic	2022	PODS	4.1945683e-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
492	Query by Output	2009	SIGMOD	0.00021974699

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,003	Counting Answers to Existential Positive Queries: A Complexity Classification	2016	PODS	7.7388586e-05
3,676	Providing Better Support for a Class of Decision Support Queries	1996	SIGMOD	6.8547125e-05
6,275	Determinacy of Real Conjunctive Queries. The Boolean Case	2022	PODS	5.1319495e-05
407	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00024004562
12,356	Query Evaluation with Soft-Key Constraints	2008	PODS	4.1945683e-05
14,261	On Analogical Query Processing in Logic Database	1986	VLDB	-
10,899	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS	4.1945683e-05
12,882	Learning Efficient Query Processing Strategies	1992	PODS	4.1945683e-05
6,090	Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited	1989	SIGMOD	5.2148332e-05
4,720	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	5.973811e-05