Complexity of answering counting aggregate queries over DL - LiteReportar como inadecuado




Complexity of answering counting aggregate queries over DL - Lite - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Reference: Kostylev, EV and Reutter, JL, (2015). Complexity of answering counting aggregate queries over DL - Lite. Journal of Web Semantics, 33, 94-111.Citable link to this page:

 

Complexity of answering counting aggregate queries over DL - Lite

Abstract: The ontology based data access model assumes that users access data by means of an ontology, which is often described in terms of description logics. As a consequence, languages for managing ontologies now need algorithms not only to decide standard reasoning problems, but also to answer database-like queries. However, fundamental database aggregate queries, such as the ones using functions COUNT and COUNT DISTINCT, have received very little attention in this context, and even defining appropriate semantics for their answers over ontologies appears to be a non-trivial task. Our goal is to study the problem of answering database queries with aggregation in the context of ontologies. This paper presents an intuitive semantics for answering counting queries, followed by a comparison with similar approaches that have been taken in different database contexts. Afterwards, it exhibits a thorough study of the computational complexity of evaluating counting queries conforming to this semantics. Our results show that answering such queries over ontologies is decidable, but generally intractable. However, our semantics promotes awareness on the information that can be obtained by querying ontologies and raises the need to look for suitable approximations or heuristics in order to allow efficient evaluation of this widely used class of queries.

Peer Review status:Peer reviewedPublication status:PublishedVersion:Author's Original Funder: Engineering and Physical Sciences Research Council   Funder: Chilean Millennium Nucleus Center for Semantic Web Research   Notes:Copyright © 2015 Elsevier B.V. All rights reserved.Notes:This is the Author's Original version of the article. The final version is available online from Elsevier at: [10.1016/j.websem.2015.05.003]

Bibliographic Details

Publisher: Elsevier

Publisher Website: http://www.elsevier.com

Journal: Journal of Web Semanticssee more from them

Publication Website: http://www.journals.elsevier.com/journal-of-web-semantics

Issue Date: 2015-05-29

pages:94-111Identifiers

Urn: uuid:1407507b-7a5d-46de-9237-f0b79cf11cf8

Source identifier: 550198

Eissn: 1873-7749

Doi: https://doi.org/10.1016/j.websem.2015.05.003

Issn: 1570-8268 Item Description

Type: Journal article;

Version: Author's OriginalKeywords: Description logics OBDA DL-Lite Aggregate queries Count queries Complexity Tiny URL: pubs:550198

Relationships





Autor: Kostylev, EV - institutionUniversity of Oxford Oxford, MPLS, Computer Science - - - Reutter, JL - - - - Bibliographic Details Pub

Fuente: https://ora.ox.ac.uk/objects/uuid:1407507b-7a5d-46de-9237-f0b79cf11cf8



DESCARGAR PDF




Documentos relacionados