NDLI: Learning Join Queries from User Examples

Content Provider	ACM Digital Library
Author	Ciucanu, Radu Staworko, Sławek Bonifati, Angela
Copyright Year	2016
Abstract	We investigate the problem of learning join queries from user examples. The user is presented with a set of candidate tuples and is asked to label them as $\textit{positive}$ or $\textit{negative}$ examples, depending on whether or not she would like the tuples as part of the join result. The goal is to quickly infer an arbitrary $\textit{n}-ary$ join predicate across an arbitrary number $\textit{m}$ of relations while keeping the number of user interactions as minimal as possible. We assume no prior knowledge of the integrity constraints across the involved relations. Inferring the join predicate across multiple relations when the referential constraints are unknown may occur in several applications, such as data integration, reverse engineering of database queries, and schema inference. In such scenarios, the number of tuples involved in the join is typically large. We introduce a set of strategies that let us inspect the search space and aggressively prune what we call $\textit{uninformative}$ tuples, and we directly present to the user the $\textit{informative}$ ones—that is, those that allow the user to quickly find the goal query she has in mind. In this article, we focus on the inference of joins with equality predicates and also allow disjunctive join predicates and projection in the queries. We precisely characterize the frontier between tractability and intractability for the following problems of interest in these settings: consistency checking, learnability, and deciding the informativeness of a tuple. Next, we propose several strategies for presenting tuples to the user in a given order that allows minimization of the number of interactions. We show the efficiency of our approach through an experimental study on both benchmark and synthetic datasets.
Starting Page	1
Ending Page	38
Page Count	38
File Format	PDF
ISSN	03625915
e-ISSN	15574644
DOI	10.1145/2818637
Volume Number	40
Issue Number	4
Journal	ACM Transactions on Database Systems (TODS)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-01-04
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	SQL query discovery Incomplete schema Reverse engineering
Content Type	Text
Resource Type	Article
Subject	Information Systems

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Reverse engineering complex join queries

Formal semantics of SQL queries

Observing SQL queries in their natural habitat

SQL query optimization:reordering for a general class of queries

Reverse Engineering SPJ-Queries from Examples

SQL/SE:a query language extension for databases supporting schema evolution

On optimizing an SQL-like nested query

SQL query optimization through nested relational algebra

A Paradigm for Learning Queries on Big Data

Learning Join Queries from User Examples

Similar Documents

Reverse engineering complex join queries

Formal semantics of SQL queries

Observing SQL queries in their natural habitat

SQL query optimization:reordering for a general class of queries

Reverse Engineering SPJ-Queries from Examples

SQL/SE:a query language extension for databases supporting schema evolution

On optimizing an SQL-like nested query

SQL query optimization through nested relational algebra

A Paradigm for Learning Queries on Big Data

Learning Join Queries from User Examples