Learning Join Queries from User Examples

Bonifati, Angela; Ciucanu, Radu; Staworko, Slawomir

Type de document :

Article dans une revue scientifique: Article original

DOI :

10.1145/2818637

Titre :

Learning Join Queries from User Examples

Auteur(s) :

Bonifati, Angela [Auteur]
Linking Dynamic Data [LINKS]
Université Claude Bernard Lyon 1 [UCBL]
Base de Données [BD]
Ciucanu, Radu [Auteur correspondant]
Linking Dynamic Data [LINKS]
University of Oxford
Staworko, Slawomir [Auteur]
Linking Dynamic Data [LINKS]
University of Edinburgh [Edin.]

Titre de la revue :

ACM Transactions on Database Systems

Pagination :

24:1--24:38

Éditeur :

Association for Computing Machinery

Date de publication :

2016-01

ISSN :

0362-5915

Discipline(s) HAL :

Informatique [cs]/Base de données [cs.DB]

Résumé en anglais : [en]

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 positive or negative examples, depending on whether or not she would ...
Lire la suite >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 positive or 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 n-ary join predicate across an arbitrary number 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 uninformative tuples, and we directly present to the user the 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.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :