|
|
|
     |
                                     |
Return to Optimization
We study the problem of economical representation of subsets of structured sets, that is, sets equipped with a set cover. Given a structured set U, and a language L whose expressions define subsets of U, the problem of Minimum Description Length in L (L-MDL) is: "given a subset V of U, and a shortest string in L that defines V ". We show that the simple set cover is enough to model a number of realistic database structures. We focus on two important families: hierarchical and multidimensional organizations. The former is found in the context of semistructured data such as XML, the latter in the context of statistical and OLAP databases. In the case of general OLAP databases, data organization is a mixture of multidimensionality and hierarchy, which can also be viewed naturally as a structured set. We study the complexity of the L-MDL problem in several settings, and provide an efficient algorithm for the hierarchical case. Finally, we illustrate the application of the theory to summarization of large result sets, (multi) query optimization for ROLAP queries, and XML queries.
@inproceedings {DBLP:conf/pods/MendelzonP03, author = {Alberto O. Mendelzon and Ken Q. Pu}, booktitle = {PODS}, title = {Concise descriptions of subsets of structured sets.}, pages = {123-133}, year = {2003}, url = {db/conf/pods/pods2003.html#MendelzonP03}, ee = {http://doi.acm.org/10.1145/773153.773166}, crossref = {conf/pods/2003}, bibsource = {DBLP, http://dblp.uni-trier.de} }  ©2004 Association for Computing Machinery |
