Abstract
Recently, there has been a lot of interest in temporal granularity, and its applications in temporal dependency theory and data mining. Generalization hierarchies used in multi-dimensional databases and OLAP serve a role similar to that of time granularity in temporal databases, but they also apply to non-temporal dimensions, like space. In this paper, we first generalize temporal functional dependencies for non-temporal dimensions, which leads to the notion of roll-up dependency (RUD).We show the applicability of RUDs in conceptual modeling and data mining. We then indicate that the notion of time granularity used in temporal databases is generally more expressive than the generalization hierarchies in multi-dimensional databases, and show how this surplus expressiveness can be introduced in non-temporal dimensions, which leads to the formalism of RUD with negation (RUD¬). A complete axiomatization for reasoning about RUD¬ is given.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995. 196
J. Berman and W. J. Blok. Positive boolean dependencies. Information Processing Letters, 27:147–150, 1988. 198, 200
C. Bettini, C. Dyreson, W. Evans, R. Snodgrass, and X. Wang. A glossary of time granularity concepts. In O. Etzion, S. Jajodia, and S. Sripada, editors, Temporal Databases: Research and Practice, number 1399 in LNCS State-of-the-art Survey, pages 406–413. Springer-Verlag, 1998. 189
C. Bettini, X. Wang, and S. Jajodia. Testing complex temporal relationships involving multiple granularities and its application to data mining. In Proc. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 68–78, Montreal, Canada, June 1996. ACM Press. 189
L. Cabibbo and R. Torlone. Querying multidimensional databases. In Sixth Int. Workshop on Database Programming Languages, pages 253–269, 1997. 189, 193
J. Gray, S. Chaudhuri, A. Bosworth, A. Layman, D. Reichart, M. Venkatrao, F. Pellow, and H. Pirahesh. Data cube: A relational aggregation operator generalizing group-by, cross-tab, and sub-totals. Data Mining and Knowledge Discovery, 1:29–53, 1997. 189, 195
H. Gregersen and C. S. Jensen. Temporal Entity-Relationship models-a survey. Technical Report TR-3, TimeCenter, 1997. 192
J. Han. OLAP mining: An integration of OLAP with data mining. In Proceedings of the 7th IFIP 2.6 Working Conference on Database Semantics (DS-7), pages 1–9, 1997. 189
V. Harinarayan, A. Rajaraman, and J. Ullman. Implementing data cubes efficiently. In Proc. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 205–216, Montreal, Canada, 1996. 195
C. Jensen, R. Snodgrass, and M. Soo. Extending existing dependency theory to temporal databases. IEEE Trans. on Knowledge and Data Engineering, 8(4):563–582, 1996. 189, 191
R. Khardon, H. Mannila, and D. Roth. Reasoning with examples: Propositional formulae and database dependencies. To appear, 1999. 200
C. Parent, S. Spaccapietra, and E. Zimanyi. Spatio-temporal information systems: a conceptual perspective. Tutorial at ER’98, 1998. 192
Y. Sagiv, C. Delobel, D. S. Parker, Jr., and R. Fagin. An equivalence between relational database dependencies and a fragment of propositional logic. Journal of the ACM, 28(3):435–453, 1981. 200
Y. Sagiv, C. Delobel, D. S. Parker, Jr., and R. Fagin. Correction to “An equivalence between relational database dependencies and a fragment of propositional logic”. Journal of the ACM, 34(4):1016–1018, 1987. 198, 200
B. Tauzovich. Towards temporal extensions to the Entity-Relationship model. In Proc. 10th. Int. Conf. on Entity-Relationship Approach, pages 163–179. ER Institute, 1991. 192
X. Wang, C. Bettini, A. Brodsky, and S. Jajodia. Logical design for temporal databases with multiple granularities. ACM Trans. on Database Systems, 22(2):115–170, 1997. 189, 190, 191, 193, 196, 197
J. Wijsen. Reasoning about qualitative trends in databases. Information Systems, 23(7):469–493, 1998. 189, 191
J. Wijsen. Temporal FDs on complex objects. To appear in the March, 1999 issue of ACM Trans. on Database Systems, 1999. 189, 191, 192
J. Wijsen and R. Ng. Discovering roll-up dependencies. Technical report, The University of British Columbia, Dept. of Computer Science, 1998. Also available at http://www.uia.ua.ac.be/u/jwijsen/. 195
J. Wijsen, R. Ng, and T. Calders. Discovering roll-up dependencies. In Proc. ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, San Diego, CA, 1999. 189, 192
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wijsen, J., Ng, R.T. (1999). Temporal Dependencies Generalized for Spatial and Other Dimensions. In: Böhlen, M.H., Jensen, C.S., Scholl, M.O. (eds) Spatio-Temporal Database Management. STDBM 1999. Lecture Notes in Computer Science, vol 1678. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48344-6_11
Download citation
DOI: https://doi.org/10.1007/3-540-48344-6_11
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66401-7
Online ISBN: 978-3-540-48344-1
eBook Packages: Springer Book Archive