Learning and verifying quantified boolean queries by example

Azza Abouzied, Dana Angluin, Christos Papadimitriou, Joseph M. Hellerstein, Avi Silberschatz

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationPODS 2013 - Proceedings of the 32nd Symposium on Principles of Database Systems
Pages49-60
Number of pages12
DOIs
StatePublished - Jul 29 2013
Event32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013 - New York, NY, United States
Duration: Jun 22 2013Jun 27 2013

Publication series

NameProceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

Other

Other32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013
CountryUnited States
CityNew York, NY
Period6/22/136/27/13

    Fingerprint

Keywords

  • Example-driven synthesis
  • Qhorn
  • Quantified boolean queries
  • Query learning
  • Query verification

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture

Cite this

Abouzied, A., Angluin, D., Papadimitriou, C., Hellerstein, J. M., & Silberschatz, A. (2013). Learning and verifying quantified boolean queries by example. In PODS 2013 - Proceedings of the 32nd Symposium on Principles of Database Systems (pp. 49-60). (Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems). https://doi.org/10.1145/2463664.2465220