An intensional approach for periodic data in relational databases
Tóm tắt
Periodic data play a major role in many application domains, spanning from manufacturing to office automation, from scheduling to data broadcasting. In many of such domains, the huge number of repetitions make the goal of extesionally storing and accessing such data very challenging. In this paper, we propose a new methodology, based on an intensional representation of periodic data. The representation model we propose captures the notion of periodic granularity provided by the temporal database glossary, and is an extension of the TSQL2 temporal relational data model. We define the algebraic operators, and introduce access algorithms to cope with them, proving that they are correct with respect to the traditional extesional approach. We also provide an experimental evaluation of our approach.
Tài liệu tham khảo
Anselma, L., Terenziani, P., Montani, S., Bottrighi, A. (2006). Towards a comprehensive treatment of repetitions, periodicity and temporal constraints in clinical guidelines. Arificial Intelligence in Medicine, 38(2), 171–195.
Bettini, C., & De Sibi, R. (2000). Symbolic representation of user-defined time granularities. Annals of Mathematics and Artificial Intelligence, 30(1–4), 53–92. citeseer.ist.psu.edu/bettini99symbolic.html.
Bettini, C., Dyreson, C., Evans, W., Snodgrass, R., Wang, X. (1998). A glossary of time granularity concepts. In O. Etzion, S. Jajodia, S. Sripada (Eds.), Temporal databases: Research and practice, number 1399 in LNCS state-of-the-art survey (pp. 406–413). Springer.
Bettini, C., Jajodia, S., Wang, S. (2000). Time granularities in databases, data mining, and temporal reasoning. Springer.
Böhlen, M.H., Snodgrass, R., Soo, M. (1996). Coalescing in temporal databases. In Procs. VLDB (pp. 180–191).
Chomicki, J., & Imielinski, T. (1993). Finite representation of infinite query answers. ACM ToDS, 18(2), 181–223.
Chomicki, J., & Toman, D. (1998). Temporal logic in information systems. In J. Chomicki, G. Saake (Eds.), Logics for databases and information systems (chap. 3, pp. 31–70). Kluwer Academic Publishers.
Codd, E. (1971). Relational completeness of data base sublanguages. In Courant computer science symposia 6, data base systems (pp. 24–25).
Dyreson, C.E., Snodgrass, R.T., Freiman, M. (1995). Efficiently supporting temporal granularities in a DBMS. Tech. Rep. TR 95/07. citeseer.nj.nec.com/dyreson95efficiently.html. Accessed 15 Jan 2013.
Egidi, L., & Terenziani, P. (2004). A lattice of classes of user-defined symbolic periodicities. In Proc. 11th international symposium on temporal representation and reasoning (pp. 21–27).
Egidi, L., & Terenziani, P. (2004a). A lattice of classes of user-defined symbolic periodicities. In IEEE Procs. of TIME’04 (pp. 13–20).
Egidi, L., & Terenziani, P. (2004b). Orthogonal operators for user-defined symbolic periodicities. In Procs. of AIMSA’04, LNAI (vol. 3192, pp. 137–147). Springer.
Egidi, L., & Terenziani, P. (2005). A flexible approach to user-defined symbolic granularities in temporal databases. In Procs. of ACM SAC’05 (pp. 592–597).
Egidi, L., & Terenziani, P. (2006). A mathematical framework for the semantics of symbolic languages representing periodic time. Annals of Mathematics and Artificial Intelligence, 46(3), 317–347.
Egidi, L., & Terenziani, P. (2006). A mathematical framework for the semantics of symbolic languages representing periodic time. Annals of Mathematics and Artificial Intelligence, 46(3), 317–347.
Egidim, L., & Terenziani, P. (2008). A modular approach to user-defined simbolic periodicities. Data & Knowledge Engineering, 66(1), 163–198.
Gao, D., Jensen, C., Snodgrass, R.T., Soo, M. (2005). Join operations in temporal databases. VLDBJ, 14, 2–29.
Hellerstein, J., Koutsupias, E., Papadimitriou, C. (1997). On the analysis of indexing schemes. In 16th ACM SIGACT-SIGMOD-SIGART symposium on principles of database systems.
Jensen, C.S., & Snodgrass, R.T. (1996). Semantics of time-varying information. Information Systems, 21(4), 311–352.
Jensen, C.S., Dyreson, C.E., Böhlen, M.H., Clifford, J., Elmasri, R., Gadia, S.K., Grandi, F., Hayes, P.J., Jajodia, S., Käfer, W., Kline, N., Lorentzos, N.A., Mitsopoulos, Y.G., Montanari, A., Nonen, D.A., Peressi, E., Pernici, B., Roddick, J.F., Sarda, N.L., Scalas, M.R., Segev, A., Snodgrass, R.T., Soo, M.D., Tansel, A.U., Tiberio, P., Wiederhold, G. (1998). The consensus glossary of temporal database concepts, in temporal databases: Research and practice. In O. Etzion, S. Jajodia, S. Sripada (Eds.) Temporal databases: Research and practice, LNCS 1399 (pp. 367–405). Springer.
Kabanza, F., Stevenne, J.M., Wolper, P. (1995). Handling infinite temporal data. Journal of Computer and System Sciences, 51, 3–17.
Kriegel, H.P., Potke, M., Seidl, T. (2001). Object-relational indexing for general interval relationships. In Proc. 7th Int’l symposium on spatial and temporal databases (SSTD’01) (pp. 522–542).
McKenzie, L.E. Jr., & Snodgrass, R.T. (1991). Evaluation of relational algebras incorporating the time dimension in databases. ACM Computing Surveys (CSUR), 23(4), 501–543.
Leban, B., McDonald, D., Forster, D. (1986). A representation for collections of temporal intervals. In Procs. of AAAI’86 (pp. 367–371).
Liu, L., & Tamer Özsu, M. (2009). Encyclopedia of database systems. Springer.
Niezette, M., & Stevenne, J.M. (1992). An efficient symbolic representation of periodic time. In Procs. of CIKM.
Ning, P., Wang, X., Jajodia, S. (2002). An algebraic representation of calendars. Annals of Mathematics and Artificial Intelligence, 36(1–2), 5–38.
Revesz, P.Z., & Cai, M. (2000). Efficient querying of periodic spatiotemporal objects. In R. Dechter (Ed.), CP. Lecture notes in computer science (vol. 1894, pp. 396–410). Springer.
Revesz, P.Z., & Cai, M. (2002). Efficient querying and animation of periodic spatio-temporal databases. Annals of Mathematics and Artificial Intelligence, 36(4), 437–457.
Snodgrass, R.T. (1995). The TSQL2 temporal query language. Kluwer Academic.
Snodgrass, R.T., & Ahn, I. (1985). A taxonomy of time in databases. In S.B. Navathe (Ed.), Proceedings of the 1985 ACM SIGMOD international conference on management of data (pp. 236–246). ACM Press.
Soo, M., & Snodgrass, R. (1993). Multiple calendar support for conventional database management systems. In Proc. Int’l workshop on an infrastructure for temporal databases.
Terenziani, P. (2000). Integrated temporal reasoning with periodic events. Computational Intelligence, 16(2), 210–256.
Terenziani, P. (2003). Symbolic user-defined periodicity in temporal relational databases. IEEE TKDE, 15(2), 489–509.
Terenziani, P. (2009). Temporal periodicity. In L. Liu, & M. Tamer Özsu (Eds.) (pp. 3004–3008). Springer.
Tuzhilin, A., & Clifford, J. (1995). On periodicity in temporal databases. Information Systems, 20(8), 619–639.