Exponential Lower Bounds and Separation for Query Rewriting

Details Exponential Lower Bounds and Separation for Query Rewriting Exponential Lower Bounds and Separation for Query Rewriting

2012-02-19

arxiv.org/abs/1202.4193v3

Computer Science

Logic in Computer Science

Scientific paper

We establish connections between the size of circuits and formulas computing monotone Boolean functions and the size of first-order and nonrecursive Datalog rewritings for conjunctive queries over OWL 2 QL ontologies. We use known lower bounds and separation results from circuit complexity to prove similar results for the size of rewritings that do not use non-signature constants. For example, we show that, in the worst case, positive existential and nonrecursive Datalog rewritings are exponentially longer than the original queries; nonrecursive Datalog rewritings are in general exponentially more succinct than positive existential rewritings; while first-order rewritings can be superpolynomially more succinct than positive existential rewritings.

Affiliated with

Also associated with

No associations

Rating

Exponential Lower Bounds and Separation for Query Rewriting does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Exponential Lower Bounds and Separation for Query Rewriting, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exponential Lower Bounds and Separation for Query Rewriting will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-563687