On characterizing boundedness of database schemes with bounded dependencies

AbstractWe investigate the effect of bounded dependencies on the boundedness of database schemes. The following results are proved. A database scheme with only bounded equality-generating dependencies is always bounded with respect to dependencies; a lossless database scheme with bounded full implicational dependencies is bounded w.r.t. dependencies if and only if the implicational dependencies are equivalent to a single join dependency and some equality-generating dependencies. By a known method, this condition can be tested effectively. These results are relevant in database theory in that they determine in a rather general case whether queries under the representative instance approach can be expressed in relational algebra