Measuring entropy for a table (e.g., SQL results)

Question

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?

Answer 1

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

• An information-theoretic approach to normal forms for relational and XML data by M. Arenas and L. Libkin (2005)

• Information dependencies by M. M. Dalkilic and E. L. Roberston (2000)