Factorised Representations of Query Results

Details Factorised Representations of Query Results Factorised Representations of Query Results

2011-04-05

arxiv.org/abs/1104.0867v1

Computer Science

Databases

44 pages, 13 figures

Scientific paper

Query tractability has been traditionally defined as a function of input database and query sizes, or of both input and output sizes, where the query result is represented as a bag of tuples. In this report, we introduce a framework that allows to investigate tractability beyond this setting. The key insight is that, although the cardinality of a query result can be exponential, its structure can be very regular and thus factorisable into a nested representation whose size is only polynomial in the size of both the input database and query. For a given query result, there may be several equivalent representations, and we quantify the regularity of the result by its readability, which is the minimum over all its representations of the maximum number of occurrences of any tuple in that representation. We give a characterisation of select-project-join queries based on the bounds on readability of their results for any input database. We complement it with an algorithm that can find asymptotically optimal upper bounds and corresponding factorised representations.

Affiliated with

Also associated with

No associations

Rating

Factorised Representations of Query Results 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 Factorised Representations of Query Results, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Factorised Representations of Query Results will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-321550