Incomplete information and dependencies in relational databases

ABSTRACT

An incomplete information relational database combines two types of information about the real world modeled by the database: (a) the information represented by tables with null values ("value not known") allowed as entries, and (b) the data dependencies, which are known to be satisfied in the real world. We view the well known chase procedure as a process which transforms type (b) information into an "equivalent" type (a) form. Assuming that the data dependencies are arbitrary implicational dependencies, we show that this transformation is not quite equivalent, but the corruption of information introduced cannot be discovered if the query language uses the operations of projection, positive selection (i.e. no negation in selection condition), union, natural join and renaming of attributes. This result can be interpreted also as the new important property of chase.The influence of so-called view dependencies on the table with null values is also examined.

REFERENCES

• 1: {BV} Beeri, C., Vardi, M.Y., Formal systems for tuple and equality generating dependencies. To appear in SIAM J. Comput.
• 2: Herve Gallaire , Jack Minker, Logic and Data Bases, Perseus Publishing, 1978
• 3: {I} Imielinski, T., Problems of representing information in the relational database, Doctoral Thesis, Warsaw, 1981.
• 4: {IL1} Imielinski, T., Lipski, W., On representing incomplete information in a relational database, Proc. 7th Internat. Conf. on Very Large Data Bases, Cannes, France, Sept. 1981, pp. 388--397.
• 5: {IL2} Imielinski, T., Lipski, W., Incomplete information in relational data bases, ICS PAS Report 475, May, 1982.
• 6: Tomasz Imielinski , Witold Lipski, Jr., Inverting relational expressions: a uniform and natural technique for various database problems, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588094]
• 7: {K} Kowalski, R., Logic for data description in logic and databases, eds. Gallaire, Minker, 1979.
• 8: Anthony Klug , Rod Price, Determining View dependencies using tableaux, ACM Transactions on Database Systems (TODS), v.7 n.3, p.361-380, Sept. 1982 [doi>10.1145/319732.319738]
• 9: {MMS} Maier, D., Mendelzon, A.O., Sagiv, Y., Testing implications of data dependencies, ACM Trans. on Database Syst. 2 (1977), 201--222.
• 10: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 11: {V} Vassiliou, Y., Functional dependencies and incomplete information, Proc 6 VLDB, Montreal, Canada, Oct. 1980, pp. 260--269.