License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2016.2
URN: urn:nbn:de:0030-drops-57034
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5703/
Go to the corresponding LIPIcs Volume Portal

Lutz, Carsten

Complexity and Expressive Power of Ontology-Mediated Queries (Invited Talk)

pdf-format:
3.pdf (0.6 MB)

Abstract

Data sets that have been collected from multiple sources or extracted from the web or often highly incomplete and heterogeneous, which makes them hard to process and query. One way to address this challenge is to use ontologies, which provide a way to assign a semantics to the data, to enrich it with domain knowledge, and to provide an enriched and uniform vocabulary for querying. The combination of a traditional database query with an ontology is called an ontology-mediated query (OMQ). The aim of this talk is to survey fundamental properties of OMQs such as their complexity, expressive power, descriptive strength, and rewritability into traditional query languages such as SQL and Datalog. A central observation is that there is a close and fruitful connection between OMQs and constraint satisfaction problems (CSPs) as well as related fragments of monadic NP, which puts OMQs into a more general perspective and gives raise to a number of interesting results.

BibTeX - Entry

@InProceedings{lutz:LIPIcs:2016:5703,
  author =	{Carsten Lutz},
  title =	{{Complexity and Expressive Power of Ontology-Mediated Queries (Invited Talk)}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{2:1--2:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Nicolas Ollinger and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5703},
  URN =		{urn:nbn:de:0030-drops-57034},
  doi =		{10.4230/LIPIcs.STACS.2016.2},
  annote =	{Keywords: Ontology-Mediated Queries, Description Logic, Constraint Satisfaction}
}

Keywords: Ontology-Mediated Queries, Description Logic, Constraint Satisfaction
Collection: 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Issue Date: 2016
Date of publication: 16.02.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI