Windows on the world

ABSTRACT

We discuss the philosophy, history and theory of window functions. Window functions (sometimes called connections) are a means to treat a relational database as a semantic whole, rather than as an arbitrary collection of relations. Simply stated, a window function maps a database state and a relation scheme to a relation over the scheme. Window functions are the basis for all existing universal scheme interfaces. We present an assumption inherent in universal scheme interfaces, the unique role assumption.Window functions have evolved along two paths, giving rise to computational definitions and weak instance definitions. We examine several examples of each type of window function, with special attention to the association-object window function of PIQUE. We then look at properties we feel a reasonable window function should satisfy, notably the containment condition and faithfulness. We also define implicit objects, which are relation schemes that a window function treats in a special manner, and which are useful for describing the behavior of window functions.

REFERENCES

• 1: <AK> A.V. Aho, B.W. Kernighan. research!user/ava/q/README, 1980.
• 2: 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]
• 3: <ASU1> A.V. Aho, Y. Sagiv, J.D. Ullman. Equivalence of relational expressions, SIAM J. on Computing 8(2), May 1979, 218--248.
• 4: A. V. Aho , Y. Sagiv , J. D. Ullman, Efficient optimization of a class of relational expressions, ACM Transactions on Database Systems (TODS), v.4 n.4, p.435-454, Dec. 1979 [doi>10.1145/320107.320112]
• 5: <AC> A.K. Arora, C.R. Carlson. The information preserving properties of relational database transformations, VLDB IV, October 1978, 352--359.
• 6: Catriel Beeri , Ronald Fagin , David Maier , Alberto Mendelzon , Jeffrey Ullman , Mihalis Yannakakis, Properties of acyclic database schemes, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.355-362, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802489]
• 7: Catriel Beeri , Ronald Fagin , David Maier , Mihalis Yannakakis, On the Desirability of Acyclic Database Schemes, Journal of the ACM (JACM), v.30 n.3, p.479-513, July 1983 [doi>10.1145/2402.322389]
• 8: Catriel Beeri , Henry F. Korth, Compatible attributes in a universal relation, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588121]
• 9: <BMSU> C. Beeri, A.O. Mendelzon, Y. Sagiv, J.D. Ullman. Equivalence of relational database schemes, SIAM J. on Computing 10(2), May 1981, 352--370.
• 10: Philip A. Bernstein, Synthesizing third normal form relations from functional dependencies, ACM Transactions on Database Systems (TODS), v.1 n.4, p.277-298, Dec. 1976 [doi>10.1145/320493.320489]
• 11: Joachim Biskup , Umeshwar Dayal , Philip A. Bernstein, Synthesizing independent database schemas, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582118]
• 12: C. Robert Carlson , Robert S. Kaplan, A generalized access path model and its application to a relational data base system, Proceedings of the 1976 ACM SIGMOD international conference on Management of data, June 02-04, 1976, Washington, D.C.
• 13: Ronald Fagin , Alberto O. Mendelzon , Jeffrey D. Ullman, A simplied universal relation assumption and its properties, ACM Transactions on Database Systems (TODS), v.7 n.3, p.343-360, Sept. 1982 [doi>10.1145/319732.319735]
• 14: <Gr> M.H. Graham. On the universal relation, CSRG Report, Univ. of Toronto, December 1979.
• 15: <Ho1> P. Honeyman. Extension Joins, VLDB VI, October 1980, 239--244.
• 16: Peter Honeyman, Testing satisfaction of functional dependencies, Journal of the ACM (JACM), v.29 n.3, p.668-677, July 1982 [doi>10.1145/322326.322330]
• 17: <Ho3> P. Honeyman. Finding lossless joins, unwritten manuscript, 1982.
• 18: <Ko> System/U: a progress report, XP2 Workshop on Relational Database Theory, June 1981.
• 19: <KU> H.F. Korth, J.D. Ullman. System/U: A database system based on the universal relation assumption. XP1 Workshop on Relational Database Theory, June--July 1980.
• 20: <KMRS> S.M. Kuck, D.A. McNabb, S.V. Rice, Y. Sagiv. The Parafrase database user's manual, Computer Science Technical Report 80-1046, Univ. of Illinois, December 1980.
• 21: Sharon McCure Kuck , Yehoshua Sagiv, A universal relation database system implemented via the network model, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588135]
• 22: Eliezer L. Lozinskii, Construction of relations in relational databases, ACM Transactions on Database Systems (TODS), v.5 n.2, p.208-224, June 1980 [doi>10.1145/320141.320155]
• 23: <Ma> D. Maier. Discarding the universal instance assumption: preliminary results, XP1 Workshop on Relational Database Theory, June--July 1980.
• 24: <MMSU> D. Maier, A.O. Mendelzon, F. Sadri, J.D. Ullman. Adequacy of decompositions of relational databases, J. of Computer and System Sciences 17(2), December 1980, 368--379.
• 25: 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]
• 26: <MR> D. Maier, D. Rozenshtein. The case for subscheme relations, unpublished manuscript, 1982.
• 27: D. Maier , D. Rozenshtein , S. Salveter , J. Stein , D. S. Warren, Toward logical data independence: a relational query language without relations, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582362]
• 28: David Maier , Jeffrey D. Ullman, Maximal objects and the semantics of universal relation databases, ACM Transactions on Database Systems (TODS), v.8 n.1, p.1-14, March 1983 [doi>10.1145/319830.319831]
• 29: <MUV1> D. Maier, J.D. Ullman, M.Y. Vardi. The equivalence of universal relation definitions, unpublished manuscript, 1982.
• 30: <MUV2> D. Maier, J.D. Ullman, M.Y. Vardi. Beyond universal instances, manuscript in preparation, 1982.
• 31: David Maier , David S. Warren, Specifying connections for a universal relation scheme database, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582355]
• 32: <Me> A.O. Mendelzon. Database states and their tableaux, XP2 Workshop on Relational Database Theory, June 1981.
• 33: <Os> S.L. Osborn. Towards a universal relation interface, VLDB V, October 1979, 52--60.
• 34: Jorma Rissanen, Independent components of relations, ACM Transactions on Database Systems (TODS), v.2 n.4, p.317-325, Dec. 1977 [doi>10.1145/320576.320580]
• 35: <Ro1> D. Rozenshtein. Query and authorization of updates in the association-object data model, Computer Science Technical Report 82-040, SUNY at Stony Brook, May 1982.
• 36: David Rozenshtein, Query and role playing in the association-object data model, 1983
• 37: 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]
• 38: <Sa2> Y. Sagiv. A characterization of globally consistent databases and their correct access paths, Computer Science Technical Report, Univ. of Illinois, July 1981.
• 39: Edward Sciore, The universal instance and database design, 1980
• 40: Edward Sciore, Improving semantic specification in a relational database, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582124]
• 41: Kathryn L. Schenk , James R. Pinkert, An algorithm for servicing multi-relational queries, Proceedings of the 1977 ACM SIGMOD international conference on Management of data, August 03-05, 1977, Toronto, Ontario, Canada [doi>10.1145/509404.509408]
• 42: John Miles Smith , Diane C. P. Smith, Database abstractions: aggregation and generalization, ACM Transactions on Database Systems (TODS), v.2 n.2, p.105-133, June 1977 [doi>10.1145/320544.320546]
• 43: <St> J. Stein, Data definition and update in the association-object data model, Doctoral dissertation in preparation, SUNY at Stony Brook, 1983.
• 44: Jeffrey D. Ullman, The U. R. strikes back, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588114]
• 45: <Va> Y. Vassiliou. Functional dependencies and incomplete information, VLDB VI, October 1980, 260--269.
• 46: <Wa> A. Walker. A universal table relational data base model with blank entries, unpublished manuscript, 1979.
• 47: <Ya> M. Yannakakis. Algorithms for acyclic database schemes, VLDB VII, September 1981, 82--94.