Computer Science – Databases
Scientific paper
2011-04-05
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.
Olteanu Dan
Závodný Jakub
No associations
LandOfFree
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.
Profile ID: LFWR-SCP-O-321550