Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:
| Indexado |
|
||||
| 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
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.
| 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 |
| 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 |
| 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. |