Simovici, Dan A.; Godfrey, Colin Outer measures on finite sets and integrity constraints in relational databases. (English) Zbl 0598.28004 Libertas Math. 4, 125-130 (1984). 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 Keywords:relational databases; time complexity of searching; relational scheme; multivalued dependency; functional dependency; regular outer measure PDFBibTeX XMLCite \textit{D. A. Simovici} and \textit{C. Godfrey}, Libertas Math. 4, 125--130 (1984; Zbl 0598.28004)