Paper Info
Title
Compiling Existential Positive Queries to Bounded-Variable Fragments
Abstract
A crucial property of bounded-variable fragments of first-order logic is that they can be evaluated in polynomial time. It is therefore a useful preprocessing step to rewrite, if possible, a first-order query to a logically equivalent one with a minimum number of variables. However, it may occur that reducing the number of variables causes an increase in formula size. We investigate this trade-off for the existential-positive fragment of first-order queries, where variable minimisation is decidable in general. In particular, we study the blow-up in the formula size when compiling existential-positive queries to the bounded variable fragment of positive first-order logic. While the increase of the formula size is always at most exponential, we identify situations (based on the signature and the number of variables) where only a polynomial blow-up is needed. In all other cases, we show that an exponential lower bound on the formula size of the compiled formula that matches the general upper bound. This exponential lower bound is unconditional, and is the first unconditional lower bound for formula size with respect to the studied compilation; it is proved via establishing a novel interface with circuit complexity which may be of future interest.
Year
DOI
Venue
2019
10.1145/3294052.3319693
Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
Keywords
Field
DocType
bounded-variable logic, compilation, existential positive queries, parameterized complexity
Existentialism,Computer science,Theoretical computer science,Calculus,Bounded function
Conference
ISBN
Citations 
PageRank 
978-1-4503-6227-6
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Christoph Berkholz1497.03
Hubie Chen241840.82