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: 1602
Venue: PODS
Year: 2013
Pagerank: 8.3078378e-05
Overall Rank: 2,639 | 81.90%
DOI: 10.1145/2463664.2465220

Incoming Non-self Citations Over Time

Authors

1. Azza Abouzied (Yale University)
2. Dana Angluin (Yale University)
3. Christos Papadimitriou (University of California Berkeley)
4. Joseph M. Hellerstein (University of California Berkeley)
5. Avi Silberschatz (Yale University)

BibTeX Citation

@inproceedings{abouzied_pods13,
        address = {New York, NY, USA},
        series = {{PODS} '13},
        title = {{Learning and Verifying Quantified Boolean Queries by Example}},
        url = {https://dl.acm.org/doi/10.1145/2463664.2465220},
        doi = {10.1145/2463664.2465220},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Abouzied, Azza and Angluin, Dana and Papadimitriou, Christos and Hellerstein, Joseph M. and Silberschatz, Avi},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,198	Overview of Data Exploration Techniques	2015	SIGMOD	0.00011706307
1,866	Predictive Interaction for Data Transformation	2015	CIDR	9.5914583e-05
2,677	Explore-by-Example: An Automatic Query Steering Framework for Interactive Data Exploration	2014	SIGMOD	8.2682753e-05
3,677	Example-Driven Query Intent Discovery: Abductive Reasoning using Semantic Similarity	2019	VLDB	7.2076465e-05
4,140	Interactive Mapping Specification with Exemplar Tuples	2017	SIGMOD	6.8765495e-05
4,420	Optimization for Active Learning-based Interactive Database Exploration	2019	VLDB	6.7132724e-05
4,644	Reverse Engineering SPJ-Queries from Examples	2017	PODS	6.5901073e-05
7,880	Learning Over Dirty Data Without Cleaning	2020	SIGMOD	5.5244204e-05
7,985	Schema Independent Relational Learning	2017	SIGMOD	5.5125969e-05
9,129	DataDiff: User-Interpretable Data Transformation Summaries for Collaborative Data Analysis	2018	SIGMOD	5.318789e-05
9,832	The Data Interaction Game	2018	SIGMOD	5.2124469e-05
10,042	Scalable and Usable Relational Learning With Automatic Language Bias	2021	SIGMOD	5.1708123e-05
11,522	On the Parameterized Complexity of Learning First-Order Logic	2022	PODS	5.093636e-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
517	Query by Output	2009	SIGMOD	0.00017169735

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,266	Counting Answers to Existential Positive Queries: A Complexity Classification	2016	PODS
2	3,708	Providing Better Support for a Class of Decision Support Queries	1996	SIGMOD
3	6,542	Determinacy of Real Conjunctive Queries. The Boolean Case	2022	PODS
4	382	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS
5	12,549	Query Evaluation with Soft-Key Constraints	2008	PODS
6	14,462	On Analogical Query Processing in Logic Database	1986	VLDB
7	11,121	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS
8	13,076	Learning Efficient Query Processing Strategies	1992	PODS
9	6,072	Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited	1989	SIGMOD
10	4,301	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB