# Learning and Verifying Quantified Boolean Queries by Example

arXiv: https://arxiv.org/abs/1304.4303 · HTML: https://mlsanity.com/paper/1304.4303/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Apr 2013.

## Built on by (most cited first, 2 of 2)

- [The Horn Non-Clausal Class and its Polynomiality](https://mlsanity.com/paper/2108.13744/) (2021)
- [Learn to Explore: on Bootstrapping Interactive Data Exploration with Meta-learning](https://mlsanity.com/paper/2212.03423/) (2022)

## Abstract (arXiv)

To help a user specify and verify quantified queries --- a class of database queries known to be very challenging for all but the most expert users --- one can question the user on whether certain data objects are answers or non-answers to her intended query. In this paper, we analyze the number of questions needed to learn or verify qhorn queries, a special class of Boolean quantified queries whose underlying form is conjunctions of quantified Horn expressions. We provide optimal polynomial-question and polynomial-time learning and verification algorithms for two subclasses of the class qhorn with upper constant limits on a query's causal density.