Muestra la distribución de disciplinas para esta publicación.
Publicaciones WoS (Ediciones: ISSHP, ISTP, AHCI, SSCI, SCI), Scopus, SciELO Chile.
| Indexado |
|
||
| DOI | |||
| Año | 2012 | ||
| Tipo |
Citas Totales
Autores Afiliación Chile
Instituciones Chile
% Participación
Internacional
Autores
Afiliación Extranjera
Instituciones
Extranjeras
We recently initiated the study of approximations of conjunctive queries within classes that admit tractable query evaluation (with respect to combined complexity). Those include classes of acyclic, bounded treewidth, or bounded hypertreewidth queries. Such approximations are always guaranteed to exist. However, while for acyclic and bounded hypertreewidth queries we have shown a number of examples of interesting approximations, for queries of bounded treewidth the study had been restricted to queries over graphs, where such approximations usually trivialize. In this note we show that for relations of arity greater than two, the notion of low treewidth approximations is a rich one, as many queries possess them. In fact we look at approximations of queries of maximum possible treewidth by queries of minimum possible treewidth (i.e., one), and show that even in this case the structure of approximations remain rather rich as long as input relations are not binary.
| Ord. | Autor | Género | Institución - País |
|---|---|---|---|
| 1 | BARCELO-BAEZA, PABLO | Hombre |
Universidad de Chile - Chile
|
| 2 | Libkin, Leonid | Hombre |
University of Edinburgh - Reino Unido
The University of Edinburgh - Reino Unido |
| 3 | ROMERO-VASQUEZ, MIGUEL ESTEBAN | Hombre |
Universidad de Chile - Chile
|