Learning and verifying quantified boolean queries by example

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

doi:10.1145/2463664.2465220

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 proceeding › Conference 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 language	English (US)
Title of host publication	PODS 2013 - Proceedings of the 32nd Symposium on Principles of Database Systems
Pages	49-60
Number of pages	12
DOIs	https://doi.org/10.1145/2463664.2465220
State	Published - 2013
Event	32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013 - New York, NY, United States Duration: Jun 22 2013 → Jun 27 2013

Publication series

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

Other

Other	32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013
Country/Territory	United States
City	New York, NY
Period	6/22/13 → 6/27/13

Keywords

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

ASJC Scopus subject areas

Software
Information Systems
Hardware and Architecture

Access to Document

10.1145/2463664.2465220

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

Learning and verifying quantified boolean queries by example. / Abouzied, Azza; Angluin, Dana; Papadimitriou, Christos et al.
PODS 2013 - Proceedings of the 32nd Symposium on Principles of Database Systems. 2013. p. 49-60 (Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abouzied, A, Angluin, D, Papadimitriou, C, Hellerstein, JM & Silberschatz, A 2013, Learning and verifying quantified boolean queries by example. in PODS 2013 - Proceedings of the 32nd Symposium on Principles of Database Systems. Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 49-60, 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013, New York, NY, United States, 6/22/13. https://doi.org/10.1145/2463664.2465220

@inproceedings{2a9c9b15479748fe83dd83d562c93272,

title = "Learning and verifying quantified boolean queries by example",

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.",

keywords = "Example-driven synthesis, Qhorn, Quantified boolean queries, Query learning, Query verification",

author = "Azza Abouzied and Dana Angluin and Christos Papadimitriou and Hellerstein, {Joseph M.} and Avi Silberschatz",

year = "2013",

doi = "10.1145/2463664.2465220",

language = "English (US)",

isbn = "9781450320665",

series = "Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems",

pages = "49--60",

booktitle = "PODS 2013 - Proceedings of the 32nd Symposium on Principles of Database Systems",

note = "32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013 ; Conference date: 22-06-2013 Through 27-06-2013",

}

TY - GEN

T1 - Learning and verifying quantified boolean queries by example

AU - Abouzied, Azza

AU - Angluin, Dana

AU - Papadimitriou, Christos

AU - Hellerstein, Joseph M.

AU - Silberschatz, Avi

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - Example-driven synthesis

KW - Qhorn

KW - Quantified boolean queries

KW - Query learning

KW - Query verification

UR - http://www.scopus.com/inward/record.url?scp=84880534299&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84880534299&partnerID=8YFLogxK

U2 - 10.1145/2463664.2465220

DO - 10.1145/2463664.2465220

M3 - Conference contribution

AN - SCOPUS:84880534299

SN - 9781450320665

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

SP - 49

EP - 60

BT - PODS 2013 - Proceedings of the 32nd Symposium on Principles of Database Systems

T2 - 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013

Y2 - 22 June 2013 through 27 June 2013

ER -

Learning and verifying quantified boolean queries by example

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this