Inverting relational expressions: a uniform and natural technique for various database problems

ABSTRACT

Let f be a relational expression and let q be a relation. It appears, surprisingly enough, that the concept of the table introduced in order to represent incomplete information can be used as a tool for representing {r f(r) ⊇ q} for a class of relational expressions built up from projection, join and positive selection. This fact, together with some other known properties of tables has wide applications and leads to a new technique for expressing and solving many database problems, especially those concerned with views. This technique is, we believe, more natural and systematic than those previously used such as tableau techniques. Some applications, like view dependencies, translating states between views and the view equivalence problem are presented.

REFERENCES

• 1: A. V. Aho , C. Beeri , J. D. Ullman, The theory of joins in relational databases, ACM Transactions on Database Systems (TODS), v.4 n.3, p.297-314, Sept. 1979 [doi>10.1145/320083.320091]
• 2: {ASU} Aho, A V., Sagiv, Y, Ullman, J D, Equivalences among relational expressions SIAM J Comput 84 (1979) 218-246
• 3: {BMSU} Beeri, C, Mendelson, A O, Sagiv, Y, Ullman, J D, Equivalence of relational database schemes SIAM J Comput 10 (1981) 352-370
• 4: F. Bancilhon , N. Spyratos, Update semantics of relational views, ACM Transactions on Database Systems (TODS), v.6 n.4, p.557-575, Dec. 1981 [doi>10.1145/319628.319634]
• 5: {BV} Beeri, C, Vardi, M, A proof procedure for data dependencies The Hebrew University, Dept of Computer Science, December, 1980
• 6: Ronald Fagin, Horn clauses and database dependencies (Extended Abstract), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.123-134, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804660]
• 7: {FMU} Fagin, R, Mendelson, A O, Ullman, J D, A simplified universal relation assumption and its properties Techn Rep RJ 2900, IBM Research Labs, San Jose, CA, November, 1980
• 8: Herve Gallaire , Jack Minker, Logic and Data Bases, Perseus Publishing, 1978
• 9: Marc H. Graham , Alberto O. Mendelzon, Notions of dependency satisfaction, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588142]
• 10: {IL1} Imielinski, T, Lipski, W, On representing incomplete information in a relational database Proc 7 VLDB, Cannes, France, September, 1981, pp 388-397
• 11: Tomasz Imieliński , Witold Lipski, Jr., A technique for translating states between database schemata, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582363]
• 12: {IL3} Imielinski, T, Lipski, W, Incomplete information and dependencies Submitted for publication
• 13: 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]
• 14: {M} Mendelson, A O, Database states and their tableaux Proc XP2 Workshop on Relational Database Theory, 1981
• 15: David Maier , Alberto O. Mendelzon , Yehoshua Sagiv, Testing implications of data dependencies, ACM Transactions on Database Systems (TODS), v.4 n.4, p.455-469, Dec. 1979 [doi>10.1145/320107.320115]
• 16: {R} Reiter, R, On closed world databases In Logic and Databases (M Gallaire and J Minker, Eds) Plenum Press, New York, 1978, pp 58-76
• 17: Jorma Rissanen, On equivalences of database schemes, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588116]
• 18: Yehoshua Sagiv, Can we use the universal instance assumption without using nulls?, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582336]
• 19: Yannis Vassiliou, A formal treatment of imperfect information in database management, 1980
• 20: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983