Circuit complexity meets ontology-based data access

DOI10.1007/978-3-319-20297-6_2MaRDI QIDQ3194705zbMATH OpenOpenAlexFDO

Authors Vladimir V. Podolskii

Publication date 20 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.01296

Mathematics Subject Classification ID

Database theory (68P15) Networks and circuits as models of computation; circuit complexity (68Q06)

Abstract: 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 which 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.

Recommendations

• Bounds in ontology-based data access via circuit complexity
• Ontology-mediated queries. Combined complexity and succinctness of rewritings via circuit complexity
• The price of query rewriting in ontology-based data access
• Ontology-based data access: a study through disjunctive Datalog, CSP, and MMSNP
• Temporalizing ontology-based data access

Cites work

• Boolean function complexity. Advances and frontiers.
• Exponential lower bounds and separation for query rewriting
• scientific article; zbMATH DE number 4008289 (Why is no real title available?)
• Linking Data to Ontologies
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• On the succinctness of query rewriting over shallow ontologies
• The DL-Lite Family and Relations
• The monotone circuit complexity of Boolean functions
• The price of query rewriting in ontology-based data access
• Towards more expressive ontology languages: the query answering problem
• Tractable reasoning and efficient query answering in description logics: The DL-Lite family

Cited in

(4)

• Bounds in ontology-based data access via circuit complexity
• Query and predicate emptiness in ontology-based data access
• On translating Lambek grammars with one division into context-free grammars
• Reducing global consistency to local consistency in ontology-based data access

This page was built for publication: Circuit complexity meets ontology-based data access

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3194705)