Colección SciELO Chile

Departamento Gestión de Conocimiento, Monitoreo y Prospección
Consultas o comentarios: productividad@anid.cl
Búsqueda Publicación
Búsqueda por Tema Título, Abstract y Keywords



Canonicalisation of Monotone SPARQL Queries
Indexado
WoS WOS:000476939700035
Scopus SCOPUS_ID:85054798084
DOI 10.1007/978-3-030-00671-6_35
Año 2018
Tipo proceedings paper

Citas Totales

Autores Afiliación Chile

Instituciones Chile

% Participación
Internacional

Autores
Afiliación Extranjera

Instituciones
Extranjeras


Abstract



Caching in the context of expressive query languages such as SPARQL is complicated by the difficulty of detecting equivalent queries: deciding if two conjunctive queries are equivalent is NP-complete, where adding further query features makes the problem undecidable. Despite this complexity, in this paper we propose an algorithm that performs syntactic canonicalisation of SPARQL queries such that the answers for the canonicalised query will not change versus the original. We can guarantee that the canonicalisation of two queries within a core fragment of SPARQL (monotone queries with select, project, join and union) is equal if and only if the two queries are equivalent; we also support other SPARQL features but with a weaker soundness guarantee: that the (partially) canonicalised query is equivalent to the input query. Despite the fact that canonicalisation must be harder than the equivalence problem, we show the algorithm to be practical for real-world queries taken from SPARQL endpoint logs, and further show that it detects more equivalent queries than when compared with purely syntactic methods. We also present the results of experiments over synthetic queries designed to stress-test the canonicalisation method, highlighting difficult cases.

Métricas Externas



PlumX Altmetric Dimensions

Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:

Disciplinas de Investigación



WOS
Sin Disciplinas
Scopus
Computer Science (All)
Theoretical Computer Science
SciELO
Sin Disciplinas

Muestra la distribución de disciplinas para esta publicación.

Publicaciones WoS (Ediciones: ISSHP, ISTP, AHCI, SSCI, SCI), Scopus, SciELO Chile.

Colaboración Institucional



Muestra la distribución de colaboración, tanto nacional como extranjera, generada en esta publicación.


Autores - Afiliación



Ord. Autor Género Institución - País
1 Salas, Jaime Hombre Universidad de Chile - Chile
2 Hogan, Aidan Hombre Universidad de Chile - Chile
3 Vrandecic, D -
4 Bontcheva, K -
5 SuarezFigueroa, MC -
6 Presutti, V -
7 Celino, I -
8 Sabou, M -
9 Kaffee, LA -
10 Simperl, E -

Muestra la afiliación y género (detectado) para los co-autores de la publicación.

Financiamiento



Fuente
FONDECYT
Fondo Nacional de Desarrollo Científico y Tecnológico
Fondo Nacional de Desarrollo Científico y Tecnológico
Millennium Institute for Foundational Research on Data (IMFD)

Muestra la fuente de financiamiento declarada en la publicación.

Agradecimientos



Agradecimiento
The work was supported by the Millennium Institute for Foundational Research on Data (IMFD) and by Fondecyt Grant No. 1181896.
Acknowledgements. The work was supported by the Millennium Institute for Foundational Research on Data (IMFD) and by Fondecyt Grant No. 1181896.

Muestra la fuente de financiamiento declarada en la publicación.