Is analogy between database and probability concepts legitimate?

Question

In Relational Databases: Tutorial for Statisticians Joe R. Hill casts probability view onto database theory. In Table 1 the author summarized the parallels between the two disciplines, describing relation structure together with three relational algebra operations in probabilistic terms.

I seek clarification on 2 items:

1. What probability distribution corresponds to empty relation? An intermediate step in Dr.Hill's paper is indicator function -- which is standard trick of thinking about relations in functional terms. My understanding is that the author generalizes {0,1} valued indicator function to probability distribution. There, the 1 valued tuples are assigned not vanishing discrete probabilities (assuming discrete domain), while all the tuples not belonging to relation inherit their 0 indicator function value as probability. My objection is that this would work for nonempty sets of tuples only.
2. Missing from the parallels is Relational Algebra union operation -- what probability concept is it analogous to? If we take average, then it would fail to honor associativity law.

Edit: Resolved confusion with transformation constraint. Consider a relation

x y
---
1 a
2 a
3 b

honoring FD x->y. One can match it with joint distribution like this

\ |  1   2   3  |
--+-------------+----
a | 1/4 1/4  0  | 1/2
b |  0   0  1/2 | 1/2
--+-------------+----
  | 1/4 1/4 1/2 |  1

Still the analogy is weak: there is well known interpretation of Functional dependencies in terms of entropy.

Answer 1

I would expect that the empty relation corresponds to the always-zero probability distribution. Disjoint union corresponds to addition of probability distributions. However, standard union would be more complicated. I don't really know if there is some way to encode the standard union for probability distributions. (I have heard people say that probability distributions form a boolean algebra. So there must be some operation that serves as the union.)

Answer 2

[from comp.databases.theory]

On Wednesday, 11 April 2012 15:02:41 UTC-7, [email protected] wrote:

A (named attribute) relation can be seen as a set of or mapping on multi(-named-)dimensional points. Functional dependencies are properties of relation values and expressions.

Database relational operators are designed so that there is a correspondence between relation expressions and predicates (and predicate expressions aka wffs). The value of a relation expression is the extension of a corresponding predicate (and wff) where the relation value's attributes are the predicate's parameters (and the wff's free variables). A relation expression has an associated predicate (and wff) built from it in a certain way according to its operators and its variables' given predicates (and wffs). The fundamental theorem of the relational model is that IF the body of each relation variable's value is the set of tuples that make a given predicate (or wff) true THEN the body of each relation expression's value is the set of tuples that make that expression's predicate (or wff) true. Eg if the predicate of relation R is R(X,Y) "person X loves person Y" and the predicate of relation variable S is S(Y,Z) "person Y loves food Z" then the expression for (R JOIN S) PROJECT_AWAY Z is EXISTS Z [S(X,Y) AND R(Y,Z)] "there exists a Z such that person X loves person Y and person Y loves food Z" ie "person X loves person Y who loves some food".

Probability operators for treating relations as probability distributions will do different things (in general) than database operators. They will satisfy different theorems.

A relation with a functional dependency can represent a function. Composition and images are relevant in databases when a relation expression corresponds to a function's (or wff term's) value. To the extent that distributions are used as (relational or functional) mappings such representation-independent mapping-oriented operators will appear in that system.

So what we can expect is that what the two systems have in common is... they both somehow involve a relation as a set of or mapping on multi(-named-)dimensional points. Correspondences between operators other than ones that are oriented to mappings would be coincidental. I don't call that much of an analogy/parallel.

I doubt that relations are an appropriate abstraction for distributions per se. I expect that a relation is just one constituent of a proper distribution representation (which would include notions of dependent and independent coordinates/variables/attributes and calculating and renormalizing probabilities to sum to 1 and multiplying and summing for conditional and marginal probabilities and binary mappings in particular) and that any relevant operators on relations (which generally won't be database ones) are in turn used to define other operators on distribution representations per se. The paper's abstract says that conditional distributions and marginal distributions are given by selection and projection respectively. However I expect that what is actually the case is that for their relational representation of (some of) a distribution some notion of removing rows and columns happens as part of complex relation operators implementing distribution operations. That is human vague reminiscence, not semantic correspondence.

philip

On Monday, 16 April 2012 15:12:27 UTC-7, [email protected] wrote:

Having now read the paper, the situation is as expected. (Except its notion of distribution has a very simple relation representation.)

This paper has nothing to do with the notion of tuples' associated 0-to-1 values that was discussed in comp.databases.theory.

1. It is a great paper. Although it could be clearer about what it means by "correspond" and "parallel". (Hill also doesn't really understand the relational model: why its values and operators and primitive operator set are what they are.)

The paper defines functions representing relations and functions representing probability mass distributions. The functions have domains that are all possible tuples on some attributes. A relation's indicator function returns 0-or-1 per whether a tuple is absent from or present in the relation. A distribution's probability function returns a 0-to-1 probability. By definition the sum of a probability function over all tuples is 1.

The paper gives certain definitions and theorems with parallel structure in expressions and semantics. The definitions and theorems involve the function representations of relations and distributions. (The parallels are not about tuple-based representations per se.) It does not purport to prove them or to make any other claim than that there are a lot of parallels.

2. The paper does not associate probabilities with tuples in the relation viewpoint. Its use of an indicator function has nothing to do with probabilities.

The paper would be clearer if the indicator functions were boolean instead of 0-or-1. Because Hill uses multiplication (implicitly expressed by adjacency) as a hack to express conjunction: 0-or-1 TIMES 0-or-1 for F-or-T AND F-or-T. Only the distribution semantics has multiplication.

3. We can define for a distribution a corresponding "positive" relation whose indicator is zero iff the probability is: its tuples are those the distribution gives positive probabilities. A distribution operator maps its arguments' positive relations to its result's positive relation the way its corresponding relation operator maps those positive relations. (There is a homomorphism from distributions to relations.) The paper doesn't mention this. But it isn't needed by the paper!

Since every distribution has probabilities summing to 1, there is at least one tuple in every distribution, and no distribution has an empty positive relation. This is irrelevant to the paper!

Informally, the fact that the relation theorems are parallel to distribution theorems means that they are either about the values returned by functions or about functions; ie they are about non-empty relations. (Formally, they are vacuously true for empty relations.)

Interestingly the (only) non-emtpy 0-attribute relation, holding the (only) 0-attribute tuple, corresponds to the (only) distribution on the (only) 0-dimensional space, namely the one giving 1 for its (only) point, the (only) 0-dimensional point.

4. The set of tuples mapped by a distribution to positive values can be represented by a relation. (Namely its positive relation.) So distribution operations that drop indicated attributes (marginals) or that drop tuples per conditions (conditionals) have definitions and theorems reminiscent of those of relation projection and restriction (respectively).

A distribution can be represented by a relation. (Namely the relation got from its positive relation by extending each tuple by an attribute giving its image in the probability function.) So some theorems about distributions as mappings are like theorems about relations as mappings.

A relation can be represented by a relation got from it by extending each tuple by an attribute with the value 1. So some theorems about relations having given attributes plus a 0-to-1 one will be similar for such relations and relations representing distributions. And some theorems will be the very same for the 0-to-1 extra-attribute relation representations of relations and distributions. Put another way, some theorems about functions on given attributes returning 0-to-1 will apply to both relation indicator functions and to distribution probability functions.

5. Is it not obvious what a distribution union is, ie when an event can be generated from either of two independent distributions on the same variables, and that it would involve addition and division by 2, and its positive relation the union of argument positive relations? (Even though that still has nothing to do with corresponding primitive operator sets.)

6. I don't know what you mean by "the analogy is weak". (FD vs transformation constraint.) The paper is clear about the "analogy". It gives precise definitions and theorems. Read the paper more closely. Don't jump to conclusions about the paper's claims and then criticize a misinterpretation of them.

In conclusion (1) (a) there is no correspondence set up with relations let alone empty relations; but there's nothing wrong with that and (b) it happens that there is a correspondence between distributions and non-empty relations; but there's nothing wrong with that and (c) the paper does not use "indicator function value as probability"; but absent relation tuples are nevertheless associated with zero; but there's nothing wrong with that and (2) (a) there is no correspondence set up with primitive operator sets; but there is no such correspondence; so there's nothing wrong with that and (b) distribution union has a simple correspondence with relation union. You don't seem to understand the senses of the correspondences and parallels.

philip