Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

We're running some benchmarks for an approximative query-answering system. It's sufficient to just think of it as running some SQL queries with joins. We are counting the results returned as part of the benchmark. However, the results often contain a lot of redundancy, so just counting results seems coarse.

Consider the following table containing results for a query like "for the US, give me its states and its car manufacturers":

================================
|| ?us_state | ?us_car_manu   ||
||============================||
|| Alabama   | Chrysler       ||
|| Alaska    | Chrysler       ||
|| ...         ...            ||
|| Wyoming   | Chrysler       ||
|| Alabama   | General Motors ||
|| Alaska    | General Motors ||
|| ...         ...            ||
|| Wyoming   | General Motors ||
|| Alabama   | Ford           ||
|| Alaska    | Ford           ||
|| ...         ...            ||
|| Wyoming   | Ford           ||
===============================

All 200 (50 × 4) results are of course unique. However, given that there is an inherent Cartesian product, the number of results flatters the amount of "information content" or "entropy" of the table: every additional car manufacturer adds fifty results for the fifty US states. (Again, this is just an example; I'm not interested in better ways to represent or run this particular query.)

As such, we're looking for a metric that will give an indication as to the (loosely speaking) redundancy-free content in the table for better comparison of content across different results for different queries. Other result tables may contain a mix of different types of Cartesian products (e.g., consider generalising the query to any country, where each country itself has its own product of states and car manufacturers, etc.).

Currently we're working off a simple metric which just counts unique term–position combinations: for the above example, the metric gives 50 + 4 = 54. This may be sufficient for comparison, but is not sensitive to the combination of terms for individual results.

Thanks to Wikipedia, I'm aware of—but not familiar with—the notion of entropy in information theory. However, I'm unclear on how the concept of entropy could be applied to this use-case. (I'm not interested in the entropy of the result strings; each term can be considered a "symbol".) Roughly speaking, each query variable could be considered as a free variable with the result terms in that column providing a set of possible outcomes and their frequency of occurrence being used as a probability mass function. This way I could compute the Shannon entropy for each column. But thereafter, I don't know how columns can be combined, or how tuples or results can be considered ... if a notion of conditional entropy would be better, etc.

And so ...

Does anyone have pointers to related material on the measure of entropy/redundancy/etc. in tables or similar structures?

Otherwise, does anyone have any ideas on how to use Shannon entropy in a convincing way for tabular data?

share|improve this question
add comment

1 Answer

Information-theoretic approach to database dependency theory has long history; here is couple of references:

share|improve this answer
2  
Please do not only post links but try to give an overview over the linked material. –  Raphael Aug 4 '12 at 9:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.