Bounds in Ontology-Based Data Access via Circuit Complexity

Ontology-based data access is an approach to organizing access to a database augmented with a logical theory. In this approach query answering proceeds through a reformulation of a given query into a new one that can be answered without any use of theory. Thus the problem reduces to the standard dat...

Full description

Saved in:
Bibliographic Details
Published in:Theory of computing systems 2017-08, Vol.61 (2), p.464-493
Main Author: Podolskii, Vladimir V.
Format: Article
Language:English
Subjects:
Boolean algebra
Circuits
Complexity
Computer Science
Knowledge representation
Ontology
Theory
Theory of Computation
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Ontology-based data access is an approach to organizing access to a database augmented with a logical theory. In this approach query answering proceeds through a reformulation of a given query into a new one that can be answered without any use of theory. Thus the problem reduces to the standard database setting. However, the size of the query may increase substantially during the reformulation. In this survey we review a recently developed framework on proving lower and upper bounds on the size of this reformulation by employing methods and results from Boolean Circuit Complexity. The survey does not assume from the reader any prior knowledge on ontology-based data access.
ISSN:1432-4350
1433-0490
DOI:10.1007/s00224-016-9707-z