×

Outer measures on finite sets and integrity constraints in relational databases. (English) Zbl 0598.28004

Let \(R=A_ 1...A_ n\) be a relation scheme on the attributes \(A_ 1...A_ n\) and let \(proj_ k(r)\) denote the projection of a relation r(R) onto the set of attributes \(K\subseteq R.\) The mapping \(\mu_ r: PR\to R_+\) given by \(\mu_ r(K)=\log_ 2| proj_ k(r)|\) (the time complexity of searching \(proj_ k(r)\) for a given k-tuple) is shown to be an outer measure on R.
If \(X\subseteq R,\) and x is an X-value, denote the selection of the relation r with X-components equal to x by \(sel_{X=x}(r).\) Then the relation r(R) on a relational scheme R satisfies the multivalued dependency \(X\twoheadrightarrow Y\) if Y is \(\mu_{x,r}\)-measurable for every X-value x, where \(\mu_{x,r}\) is defined by \(\mu_{x,r}(k)=\mu_{sel_{X=x}(r)}(k)\) for all \(k\in PR.\)
The relation r(R) satisfies the functional dependency \(X\to Y\) for \(X,Y\in PR,\) if and only if \(\mu_{x,r}=0\) for any X-value x. Finally, for every regular outer measure \(\mu: PR\to N\) there exists a relation r(R) on the relational scheme R such that \(\mu r=\mu.\) Examples are given.

MSC:

28A12 Contents, measures, outer measures, capacities
68P20 Information storage and retrieval of data
PDFBibTeX XMLCite