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



When is Ontology-Mediated Querying Efficient?
Indexado
WoS WOS:000502349000053
Scopus SCOPUS_ID:85067180723
DOI 10.1109/LICS.2019.8785823
Año 2019
Tipo proceedings paper

Citas Totales

Autores Afiliación Chile

Instituciones Chile

% Participación
Internacional

Autores
Afiliación Extranjera

Instituciones
Extranjeras


Abstract



In ontology-mediated querying, description logic (DL) ontologies are used to enrich incomplete data with domain knowledge which results in more complete answers to queries. However, the evaluation of ontology-mediated queries (OMQs) over relational databases is computationally hard. This raises the question when OMQ evaluation is efficient, in the sense of being tractable in combined complexity or fixed-parameter tractable. We study this question for a range of ontology-mediated query languages based on several important and widely-used DLs, using unions of conjunctive queries as the actual queries. For the DL fl-t1, we provide a characterization of the classes of OMQs that are fixed-parameter tractable. For its fragment fl-C1', which restricts the use of inverse roles, we provide a characterization of the classes of OMQs that are tractable in combined complexity. Both results are in terms of equivalence to OMQs of bounded tree width and rest on a reasonable assumption from parameterized complexity theory. They are similar in spirit to Grohe's seminal characterization of the tractable classes of conjunctive queries over relational databases. We further study the complexity of the meta problem of deciding whether a given OMQ is equivalent to an OMQ of bounded tree width, providing several completeness results that range from NP to 2ExPTimE, depending on the DL used. We also consider the DL-Lite family of DLs, including members that, unlike E, admit functional roles.

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
Mathematics (All)
Software
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 BARCELO-BAEZA, PABLO Hombre Chile - Chile
Instituto Milenio Fundamentos de los Datos - Chile
Universidad de Chile - Chile
2 Feier, Cristina Mujer Univ Bremen - Alemania
University of Bremen - Alemania
Universität Bremen - Alemania
3 Lutz, Carsten Hombre Univ Bremen - Alemania
University of Bremen - Alemania
Universität Bremen - Alemania
4 Pieris, Andreas Hombre UNIV EDINBURGH - Reino Unido
University of Edinburgh - Reino Unido
The University of Edinburgh - Reino Unido
5 IEEE Corporación

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
European Research Council
EPSRC
ERC
Fondo Nacional de Desarrollo Científico y Tecnológico
Engineering and Physical Sciences Research Council
Millennium Institute for Foundational Research on Data
Horizon 2020 Framework Programme
Westmead Millennium Institute for Medical Research
ERC consolidator

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

Agradecimientos



Agradecimiento
We thank the anonymous reviewers for their helpful comments. This research was supported by ERC consolidator grant 647289 CODA, by EPSRC grant EP/S003800/1 EQUID, by the Millennium Institute for Foundational Research on Data, and Fondecyt grant 1170109.
Being a bit more adventurous, one could be interested in classifying PTIME combined complexity within (ELI,CQ) and related languages, and in classifying PTIME combined complexity and FPT for DLs with functional roles, existential rule languages such as (frontier-)guarded rules, and DLs that include negation and disjunction such as ALC and SHIQ. Acknowledgments. We thank the anonymous reviewers for their helpful comments. This research was supported by ERC consolidator grant 647289 CODA, by EPSRC grant EP/S003800/1 EQUID, by the Millennium Institute for Foundational Research on Data, and Fondecyt grant 1170109.

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