Size Bounds for Conjunctive Queries with General Functional Dependencies

Details Size Bounds for Conjunctive Queries with General Functional Dependencies Size Bounds for Conjunctive Queries with General Functional Dependencies

2009-09-10

arxiv.org/abs/0909.2030v2

Computer Science

Databases

22 pages, 2 figures

Scientific paper

This paper extends the work of Gottlob, Lee, and Valiant (PODS 2009)[GLV], and considers worst-case bounds for the size of the result Q(D) of a conjunctive query Q to a database D given an arbitrary set of functional dependencies. The bounds in [GLV] are based on a "coloring" of the query variables. In order to extend the previous bounds to the setting of arbitrary functional dependencies, we leverage tools from information theory to formalize the original intuition that each color used represents some possible entropy of that variable, and bound the maximum possible size increase via a linear program that seeks to maximize how much more entropy is in the result of the query than the input. This new view allows us to precisely characterize the entropy structure of worst-case instances for conjunctive queries with simple functional dependencies (keys), providing new insights into the results of [GLV]. We extend these results to the case of general functional dependencies, providing upper and lower bounds on the worst-case size increase. We identify the fundamental connection between the gap in these bounds and a central open question in information theory. Finally, we show that, while both the upper and lower bounds are given by exponentially large linear programs, one can distinguish in polynomial time whether the result of a query with an arbitrary set of functional dependencies can be any larger than the input database.

Affiliated with

Also associated with

No associations

Rating

Size Bounds for Conjunctive Queries with General Functional Dependencies 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 Size Bounds for Conjunctive Queries with General Functional Dependencies, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Size Bounds for Conjunctive Queries with General Functional Dependencies will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-427452