Some Results on the Representative Instance in Relational Databases

From MaRDI portal





Recently, the representative instance has been proposed as a generalized concept of the pure universal relation. Let \(R=\{<R_ 1,F_ 1>,...,<R_ n,F_ n>\}\) be a database scheme, where each \(R_ i\) is a set of attributes and \(F_ i\) is a set of functional dependencies over \(R_ i\). R is said to be consistent if the representative instance of every database \(I=\{r_ 1,...,r_ n\}\) of R satisfies F \((=F_ 1\cup...\cup F_ n)\), that is, if whenever each relation \(r_ i\) satisfies its own functional dependencies \(F_ i\), the representative instance satisfies all the functional dependencies F. In this paper, we present the following two results. (1) It can be determined in \(O(n| F| \| F\|)\) time whether R is consistent, where \(| F|\) is the number of functional dependencies in F and \(\| F\|\) is the size of the description of F. (2) Suppose that R is consistent. Given a subset V of \(R_ 1\cup...\cup R_ n\), we can construct in \(O(n| F| \| F\|)\) time a relational expression such that (a) its value is the total projection of the representative instance onto V for every database of R, (b) it consists of projection, extension join, and union, and (c) it contains neither a redundant union nor a redundant join.











This page was built for publication: Some Results on the Representative Instance in Relational Databases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3738611)