Characterizing XML Twig Queries with Examples

Staworko, Slawomir; Wieczorek, Piotr

Type de document :

Communication dans un congrès avec actes

Titre :

Characterizing XML Twig Queries with Examples

Auteur(s) :

Staworko, Slawomir [Auteur]
Linking Dynamic Data [LINKS]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Wieczorek, Piotr [Auteur]
University of Wrocław [Poland] [UWr]

Titre de la manifestation scientifique :

International Conference on Database Theory

Ville :

Brussels

Pays :

Belgique

Date de début de la manifestation scientifique :

2015-03

Titre de l’ouvrage :

International Conference on Database Theory

Titre de la revue :

International Conference on Database Theory

Date de publication :

2015-03

Mot(s)-clé(s) en anglais :

Query characterization
Query examples
Query fitting
Twig queries

Discipline(s) HAL :

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

Résumé en anglais : [en]

Typically, a (Boolean) query is a finite formula that defines a possibly infinite set of database instances that satisfy it (positive examples), and implicitly, the set of instances that do not satisfy the query (negative ...
Lire la suite >Typically, a (Boolean) query is a finite formula that defines a possibly infinite set of database instances that satisfy it (positive examples), and implicitly, the set of instances that do not satisfy the query (negative examples). We investigate the following natural question: for a given class of queries, is it possible to characterize every query with a finite set of positive and negative examples that no other query is consistent with.We study this question for twig queries and XML databases. We show that while twig queries are characterizable, they generally require exponential sets of examples. Consequently, we focus on a practical subclass of anchored twig queries and show that not only are they characterizable but also with polynomially-sized sets of examples. This result is obtained with the use of generalization operations on twig queries, whose application to an anchored twig query yields a properly contained and minimally different query. Our results illustrate further interesting and strong connections between the structure and the semantics of anchored twig queries that the class of arbitrary twig queries does not enjoy. Finally, we show that the class of unions of twig queries is not characterizable.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Fichiers

https://hal.inria.fr/hal-01205417/document
Accès libre
Accéder au document

https://hal.inria.fr/hal-01205417/document
Accès libre
Accéder au document

https://hal.inria.fr/hal-01205417/document
Accès libre
Accéder au document

document
Accès libre
Accéder au document

staworko-icdt15b.pdf
Accès libre
Accéder au document

Characterizing XML Twig Queries with Examples BibTeX CSV Excel RIS

Fichiers

Characterizing XML Twig Queries with Examples

BibTeX

CSV

Excel

RIS