Evaluation of relational algebras incorporating the time dimension in databases

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Evaluation of relational algebras incorporating the time dimension in databases

Full text

Pdf (3.76 MB)

Source

ACM Computing Surveys (CSUR) archive
Volume 23 , Issue 4 (December 1991) table of contents

Pages: 501 - 543

Year of Publication: 1991

ISSN:0360-0300

Authors

L. Edwin McKenzie, Jr.	AFCAC/SY, Hanscom AFB, MA
Richard Thomas Snodgrass	Univ. of Arizona, Tucson

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 70, Citation Count: 33

Additional Information:

references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/125137.125166 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	ALLEN, J. F., AND HAYES, P. J. 1985. A commonsense theory of time, in Proceedings of the International Joint Conference on Artificial Intelligence. (Los Angeles, Calif. Aug. 1985), pp. 528-531.
	2	Tera Lougenia Anderson, The database semantics of time, 1981
	3	ANDERSON, T. L. 1982. Modeling time at the conceptual level, in Proceedings of the International Conference on Databases: Improving Usability and Responsiveness. P. Scheuermann, Ed. (Jerusalem, Israel, June 1982). Academic Press, pp. 273-297.
	4	Gad Ariav, A temporally oriented data model, ACM Transactions on Database Systems (TODS), v.11 n.4, p.499-527, Dec. 1986 [doi>10.1145/7239.7350]
	5	ARIAV, G., AND CLIFFORD, J. 1986. Temporal data management: Models and systems, in New Directions for Database Systems. Ablex Publishmg Corporation, Norwood, N.J., Chap 12, pp. 168-185.
	6	Jacov Ben-Zvi, The time relational model, 1982
	7	BHARGAVA, G, AND GADIA, S. K. 1990. The concept of error in a database: An application of temporal databases, in Proceedings of 1990 COMAD International Conference on Management of Data. N. Prakash, Ed. Tara McGraw- Hill, New Delhi, pp. 106-121.
	8	G. Bhargava , S. K. Gadia, Relational Database Systems with Zero Information Loss, IEEE Transactions on Knowledge and Data Engineering, v.5 n.1, p.76-87, February 1993 [doi>10.1109/69.204093]
	9	BROOKS, F. P. 1956. The analytic design of automatic data processing systems. Ph.D. dissertation. Harvard Univ.
	10	BUBENKO, J. A., JR. 1977. The temporal dimension in information modeling, in Architecture and Models in Data Base Management Systems. North-Holland Publishing, The Netherlands, pp. 93-118.
	11	Peter Pin-Shan Chen, The entity-relationship model—toward a unified view of data, ACM Transactions on Database Systems (TODS), v.1 n.1, p.9-36, March 1976 [doi>10.1145/320434.320440]
	12	CLIFFORD, J. 1982. A model for historical databases, in Proceedings of Workshop on Logical Bases for Data Bases. (Toulouse, France).
	13	James Clifford , Albert Croker, The Historical Relational Data Model (HRDM) and Algebra Based on Lifespans, Proceedings of the Third International Conference on Data Engineering, p.528-537, February 03-05, 1987
	14	CLIFFORD, J, AND RAO, A. 1987 A simple, general structure for temporal domains, in Proceedings of the Con{erence on Temporal Aspects in Information Systems. (France). AFCET, pp. 23 30.
	15	James Clifford , Abdullah Uz Tansel, On an algebra for historical relational databases: two views, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.247-265, May 1985, Austin, Texas, United States
	16	James Clifford , David S. Warren, Formal semantics for time in databases, ACM Transactions on Database Systems (TODS), v.8 n.2, p.214-254, June 1983 [doi>10.1145/319983.319986]
	17	E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
	18	E. F. Codd, The relational model for database management: version 2, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	19	CROKER, A., AND CLIFFORD, J. 1989. On completeness of historical relational data models. Tech. Rep. New York University.
	20	Peter Dadam , Vincent Y. Lum , H.-D. Werner, Integration of Time Versions into a Relational Database System, Proceedings of the 10th International Conference on Very Large Data Bases, p.509-522, August 27-31, 1984
	21	DATE, C J. 1986. An informal definition of the relational model, in Relational Database: Selected Writings. Addison-Wesley, Reading, Mass., Chap. 2. pp. 21-31.
	22	S Misbah Deen, A relational language with deductions, functions, and recursions, Data & Knowledge Engineering, v.1 n.2, p.139-154, June 1985 [doi>10.1016/0169-023X(85)90032-1]
	23	Ramez Elmasri , Shamkant B. Navathe, Fundamentals of database systems, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1989
	24	ENDERTON, H. B. 1970. Elements of Set Theory. Academic Press, New York.
	25	Shashi K. Gadia, Toward a Multihomogeneous Model for a Temporal Database, Proceedings of the Second International Conference on Data Engineering, p.390-397, February 05-07, 1986
	26	Shashi K. Gadia, A homogeneous relational model and query languages for temporal databases, ACM Transactions on Database Systems (TODS), v.13 n.4, p.418-448, Dec. 1988 [doi>10.1145/49346.50065]
	27	Shashi K. Gadia , Jay H. Vaishnav, A query language for a homogeneous temporal database, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.51-56, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325412]
	28	Shashi K. Gadia , Chuen-Sing Yeung, A generalized model for a relational temporal database, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.251-259, June 01-03, 1988, Chicago, Illinois, United States
	29	Eric N. Hanson, A performance analysis of view materialization strategies, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.440-453, May 27-29, 1987, San Francisco, California, United States
	30	Eric N. Hanson, Processing queries aganist database procedures: a performance analysis, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.295-302, June 01-03, 1988, Chicago, Illinois, United States
	31	C. S. Jensen , L. Mark , N. Roussopoulos, Incremental Implementation Model for Relational Databases with Transaction Time, IEEE Transactions on Knowledge and Data Engineering, v.3 n.4, p.461-473, December 1991 [doi>10.1109/69.109107]
	32	JONES, S., MASON. P, ANn STAMPER, R. 1979. LEGOL 2.0: A relational specification language for complex rules. Inf. Syst. 4, 4, (Nov), 293 305.
	33	Manfred R. Klopprogge, TERM: An Approach to Include Time Dimension in the Entity-Relationship Model, Proceedings of the Second International Conference on the Entity-Relationship Approach to Information Modeling and Analysis, p.473-508, October 12-14, 1981
	34	Anthony Klug, Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions, Journal of the ACM (JACM), v.29 n.3, p.699-717, July 1982 [doi>10.1145/322326.322332]
	35	LINDGREEN, P. 1982. The information graph, in Proceedings of the 1st Scandinavian Research Seminar on Information Modelling and Database Management. (University of Tampere, Jan ), pp. 103-127.
	36	LORENTZOS, N. A 1988. A formal extension of the relational model for the representation and mampulatlon of generic intervals Ph.D. dissertation, Birkbeck College. Umversity of London.
	37	N. A. Lorentzos , R. G. Johnson, Extending relational algebra to manipulate temporal data, Information Systems, v.13 n.3, p.289-296, May 1, 1988 [doi>10.1016/0306-4379(88)90040-3]
	38	V Lum , P Dadam , R Erbe , J Guenauer , P Pistor , G Walch , H Werner , J Woodfill, Designing DBMS support for the temporal dimension, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
	39	David Maier, Theory of Relational Databases, Computer Science Pr, 1983
	40	Frank Manola , Umeshwar Dayal, PDM: an object-oriented data model, Proceedings on the 1986 international workshop on Object-oriented database systems, p.18-25, September 23-26, 1986, Pacific Grove, California, United States
	41	N. G. Martin , Shamkant B. Navathe , Rafi Ahmed, Dealing with Temporal Schema Anomalies in History Databases, Proceedings of the 13th International Conference on Very Large Data Bases, p.177-184, September 01-04, 1987
	42	MCKENZlE, E. 1986. Bibliography: Temporal databases. ACM SIGMOD Record 15, 4 (Dec), 40-52.
	43	Leslie Edwin Mckenzie, Jr. , Richard Snodgrass, An algebraic language for query and update of temporal databases, 1988
	44	E. McKenzie , Richard Thomas Snodgrass, Schema evolution and the relational algebra, Information Systems, v.15 n.2, p.207-232, 1990 [doi>10.1016/0306-4379(90)90036-O]
	45	MCKENzIE, E , AND SNODGRASS, R. 1991. Supporting valid time in an histomcal relational algebra: Proofs and Extensions. Tech. Rep. TR 91-15 Dept. of Computer Science, Univ. of Arizona
	46	NAVATHE, S. B., AND AHMED, R. 1987. TSQL--A language interface for history databases, in Proceedings of the Conference on Temporal Aspects zn Information Systems. (France, May) AFCET, pp. 113 128.
	47	S. B. Navathe , R. Ahmed, A temporal relational model and a query language, Information Sciences: an International Journal, v.49 n.1-3, p.147-175, Oct.-Dec. 1989 [doi>10.1016/0020-0255(89)90026-1]
	48	Ricky Overmyer , Michael Stonebraker, Implementation of a time expert in a data base system, ACM SIGMOD Record, v.12 n.3, p.51-60, April 1982 [doi>10.1145/984505.984509]
	49	Phyllis Reisner, Human Factors Studies of Database Query Languages: A Survey and Assessment, ACM Computing Surveys (CSUR), v.13 n.1, p.13-31, March 1981 [doi>10.1145/356835.356837]
	50	REISNER. P., BOYCE, R F., AND CH^MBERLrN, D. D. 1975. Human factors evaluation of two data base query languages: Square and sequel, m Proceedings of the AFIPS National Computer Conference (Arhngton, Va ) AFIPS Press, pp 447 452.
	51	RESCHER, N. C., AND URQU~ART, A. 1971. Temporal Logic. Springer-Verlag, New York.
	52	Nicholas Roussopoulos, An incremental access method for ViewCache: concept, algorithms, and cost analysis, ACM Transactions on Database Systems (TODS), v.16 n.3, p.535-563, Sept. 1991 [doi>10.1145/111197.111215]
	53	Rubik Sadeghi, A database query language for operations on historical data, 1987
	54	SADEGHI, R., SAMSON, W. B., AND DEEN, S M. 1987. HQL: A historical query language. Tech. Rep. Dundee College of Technology.
	55	N. L. Sarda, Algebra and query language for a historical data model, The Computer Journal, v.33 n.1, p.11-18, Feb. 1990 [doi>10.1093/comjnl/33.1.11]
	56	David W. Shipman, The functional data model and the data languages DAPLEX, ACM Transactions on Database Systems (TODS), v.6 n.1, p.140-173, March 1981 [doi>10.1145/319540.319561]
	57	John Miles Smith , Philip Yen-Tang Chang, Optimizing the performance of a relational algebra database interface, Communications of the ACM, v.18 n.10, p.568-579, Oct. 1975 [doi>10.1145/361020.361025]
	58	Richard Snodgrass, The temporal query language TQuel, ACM Transactions on Database Systems (TODS), v.12 n.2, p.247-298, June 1987 [doi>10.1145/22952.22956]
	59	Richard Snodgrass , Ilsoo Ahn, A taxonomy of time databases, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.236-246, May 1985, Austin, Texas, United States
	60	Richard Snodgrass , Ilsoo Ahn, Temporal databases, Computer, v.19 n.9, p.35-41, Sept. 1986 [doi>10.1109/MC.1986.1663327]
	61	Michael D. Soo, Bibliography on temporal databases, ACM SIGMOD Record, v.20 n.1, p.14-23, March 1991 [doi>10.1145/122050.122054]
	62	STAM, R., A~qU S~ODGRASS, R. 1988. A bibliography on temporal databases. Database Eng. 7, 4 (Dec.), 231-239
	63	Abdullah Uz Tansel, Adding time dimension to relational model and extending relational algebra, Information Systems, v.11 n.4, p.343-355, Oct. 1986 [doi>10.1016/0306-4379(86)90014-1]
	64	Abdullah Uz Tansel, A Statistical Interface for Historical Relational Databases, Proceedings of the Third International Conference on Data Engineering, p.538-546, February 03-05, 1987
	65	TANSEL, A. U., ANn ARKUN, M. E. 1985 Equivalence of historical relational calculus and historical relational algebra. Tech. Rep. Bernard M. Baruch College, City Univ. of New York.
	66	Abdullah Uz Tansel , M. Erol Arkun, HQUEL, a query language for historical relational databases, Proceedings of the 3rd international workshop on Statistical and scientific database management, p.135-142, July 22-24, 1986
	67	A. U. Tansel , M. E. Arkun , G. Ösoyoğlu, Time-by-Example Query Language for Historical Databases, IEEE Transactions on Software Engineering, v.15 n.4, p.464-478, April 1989 [doi>10.1109/32.16597]
	68	Peter MacLeod Thompson, A temporal data model based on accounting principles, University of Calgary, Calgary, Alta., Canada, 1991
	69	Alexander Tuzhilin , James Clifford, A temporal relational algebra as a basis for temporal relational completeness, Proceedings of the sixteenth international conference on Very large databases, p.13-23, September 1990, Brisbane, Australia
	70	Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
	71	Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
	72	Scott L. Vandenberg , David J. DeWitt, Algebraic support for complex objects with arrays, identity, and inheritance, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.158-167, May 29-31, 1991, Denver, Colorado, United States
	73	YEUNG, C. S. 1986 Query languages for a heteroeneous temporal database. Master's Thesis, EE/CS Dept. Texas Tech. Univ.

CITED BY 33

	Kristian Torp , Leo Mark , Christian S. Jensen, Efficient Differential Timeslice Computation, IEEE Transactions on Knowledge and Data Engineering, v.10 n.4, p.599-611, July 1998
	Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993
	Michael H. Böhlen , Christian S. Jensen , Richard Thomas Snodgrass, Temporal statement modifiers, ACM Transactions on Database Systems (TODS), v.25 n.4, p.407-456, Dec. 2000
	James Clifford , Albert Croker , Alexander Tuzhilin, On completeness of historical relational query languages, ACM Transactions on Database Systems (TODS), v.19 n.1, p.64-116, March 1994
	Ralf Hartmut Güting , Michael H. Böhlen , Martin Erwig , Christian S. Jensen , Nikos A. Lorentzos , Markus Schneider , Michalis Vazirgiannis, A foundation for representing and querying moving objects, ACM Transactions on Database Systems (TODS), v.25 n.1, p.1-42, March 2000
	Jan Chomicki , David Toman , Michael H. Böhlen, Querying ATSQL databases with temporal logic, ACM Transactions on Database Systems (TODS), v.26 n.2, p.145-178, June 2001
	Janne Skyt , Christian S. Jensen , Leo Mark, A foundation for vacuuming temporal databases, Data & Knowledge Engineering, v.44 n.1, p.1-29, January 2003
	Paolo Terenziani , Richard Thomas Snodgrass, Reconciling Point-Based and Interval-Based Semantics in Temporal Relational Databases: A Treatment of the Telic/Atelic Distinction, IEEE Transactions on Knowledge and Data Engineering, v.16 n.5, p.540-551, May 2004
	John F. Roddick , Noel G. Craske , Thomas J. Richards, Handling Discovered Structure in Database Systems, IEEE Transactions on Knowledge and Data Engineering, v.8 n.2, p.227-240, April 1996
	Ming Xiong , Krithi Ramamritham , John A. Stankovic , Don Towsley , Rajendran Sivasankaran, Scheduling Transactions with Temporal Constraints: Exploiting Data Semantics, IEEE Transactions on Knowledge and Data Engineering, v.14 n.5, p.1155-1166, September 2002
	Heidi Gregersen , Christian S. Jensen, Temporal Entity-Relationship Models-A Survey, IEEE Transactions on Knowledge and Data Engineering, v.11 n.3, p.464-497, May 1999
	Abdullah Uz Tansel , Erkan Tin, The Expressive Power of Temporal Relational Query Languages, IEEE Transactions on Knowledge and Data Engineering, v.9 n.1, p.120-134, January 1997
	Shashi K. Gadia , Sunil S. Nair, Algebraic Identities and Query Optimization in a Parametric Model for Relational Temporal Databases, IEEE Transactions on Knowledge and Data Engineering, v.10 n.5, p.793-807, September 1998
	Elpida T. Keravnou, A Multidimensional and Multigranular Model of Time for Medical Knowledge-Based Systems, Journal of Intelligent Information Systems, v.13 n.1-2, p.73-120, July-Oct. 1999
	Gultekin Ozsoyoglu , Richard Thomas Snodgrass, Temporal and Real-Time Databases: A Survey, IEEE Transactions on Knowledge and Data Engineering, v.7 n.4, p.513-532, August 1995
	Jef Wijsen , Alexis Bès, On query optimization in a temporal SPC algebra, Data & Knowledge Engineering, v.44 n.2, p.165-192, February 2003
	Giedrius Slivinskas , Christian S. Jensen , Richard Thomas Snodgrass, A Foundation for Conventional and Temporal Query Optimization Addressing Duplicates and Ordering, IEEE Transactions on Knowledge and Data Engineering, v.13 n.1, p.21-49, January 2001
	Vittorio Brusoni , Luca Console , Paolo Terenziani , Barbara Pernici, Qualitative and Quantitative Temporal Constraints and Relational Databases: Theory, Architecture, and Applications, IEEE Transactions on Knowledge and Data Engineering, v.11 n.6, p.948-894, November 1999
	Abdullah Uz Tansel, Temporal Relational Data Model, IEEE Transactions on Knowledge and Data Engineering, v.9 n.3, p.464-479, May 1997
	Paolo Terenziani, Symbolic User-Defined Periodicity in Temporal Relational Databases, IEEE Transactions on Knowledge and Data Engineering, v.15 n.2, p.489-509, February 2003
	Stanley Y. W. Su , Soon J. Hyun , Hsin-Hsing M. Chen, Temporal Association Algebra: A Mathematical Foundation for Processing Object-Oriented Temporal Databases, IEEE Transactions on Knowledge and Data Engineering, v.10 n.3, p.389-408, May 1998
	Lavinia Egidi , Paolo Terenziani, A flexible approach to user-defined symbolic granularities in temporal databases, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
	Rajiv Bagai , Mehmet A. Orgun, A temporal paraconsistent relational algebra for incomplete and inconsistent information, Proceedings of the 33rd annual on Southeast regional conference, March 17-18, 1995, Clemson, South Carolina
	Christian S. Jensen , Leo Mark , Nick Roussopoulos , Timos Sellis, Using differential techniques to efficiently support transaction time, The VLDB Journal — The International Journal on Very Large Data Bases, v.2 n.1, p.75-116, January 1993
	Rodolfo Sabás Gómez , Juan Carlos Augusto, Expressiveness of temporal query languages: on the modelling of intervals, interval relationships and states, Artificial Intelligence Review, v.26 n.4, p.269-289, December 2006
	Debabrata Dey , Terence M. Barron , Veda C. Storey, A complete temporal relational algebra, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.3, p.167-180, August 1996
	Michael Böhlen , Johann Gamper , Christian S. Jensen, An algebraic framework for temporal attribute characteristics, Annals of Mathematics and Artificial Intelligence, v.46 n.3, p.349-374, March 2006
	Joel Richardson, Supporting Lists in a Data Model (A Timely Approach), Proceedings of the 18th International Conference on Very Large Data Bases, p.127-138, August 23-27, 1992
	Nabil I. Hachem , Ke Qiu , Michael A. Gennert , Matthew O. Ward, Managing Derived Data in the Gaea Scientific DBMS, Proceedings of the 19th International Conference on Very Large Data Bases, p.1-12, August 24-27, 1993
	Michael H. Böhlen , Richard Thomas Snodgrass , Michael D. Soo, Coalescing in Temporal Databases, Proceedings of the 22th International Conference on Very Large Data Bases, p.180-191, September 03-06, 1996
	Stavros Kokkotos , Efstathios V. Ioannidis , Themis Panayiotopoulos , Constantine D. Spyropoulos, On the issue of valid time(s) in temporal databases, ACM SIGMOD Record, v.24 n.3, p.40-43, Sept. 1995
	Niki Pissinou , Richard Thomas Snodgrass , Ramez Elmasri , Inderpal S. Mumick , Tamer Özsu , Barbara Pernici , Arie Segev , Babis Theodoulidis , Umeshwar Dayal, Towards an infrastructure for temporal databases: report of an invitational ARPA/NSF workshop, ACM SIGMOD Record, v.23 n.1, p.35-51, March 1994
	TheodoreK. Apostolopoulos , VictoriaC. Daskalou, Temporal Network Management Information Model andServices, Journal of Network and Systems Management, v.6 n.3, p.245-265, September 01, 1998

INDEX TERMS

Primary Classification:
H. Information Systems
H.2 DATABASE MANAGEMENT
H.2.1 Logical Design
Subjects: Data models

General Terms:
Design, Languages, Performance

Keywords:
aggregate, chronon, historical relation, homogeneity, query optimization, snapshot relation, transaction time, valid time

REVIEW

"Martin E. Modell : Reviewer"

All data are time-dependent in that they reflect an action that occurred or a state that existed at a specified time. If all previous values of data were archived when changes were made, rather than being overlaid with new data, the archived d more...

Collaborative Colleagues:

L. Edwin McKenzie, Jr.: colleagues

Richard Thomas Snodgrass: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player