Time Granularities in Databases, Data Mining, and Temporal Reasoning

by Bettini, Claudio; Jajodia, Sushil; Wang, Sean

• ISBN13: 9783540669975
• ISBN10: 3540669973
• Format: Hardcover
• Copyright: 2000-08-01
• Publisher: Springer-Verlag New York Inc

Summary

Calendar units, such as months and days, clock units, such as hours and seconds, and specialized units, such as business days and academic years, play a major role in a wide range of information system applications. System support for reasoning about these units, called granularities in this book, is important for the efficient design, use, and implementation of such applications. The book deals with several aspects of temporal information and provides a unifying model for granularities. It is intended for computer scientists and engineers who are interested in the formal models and technical development of specific issues. Practitioners can learn about critical aspects that must be taken into account when designing and implementing databases supporting temporal information. Lecturers may find this book useful for an advanced course on databases. Moreover, any graduate student working on time representation and reasoning, either in data or knowledge bases, should definitely read it.

Table of Contents

Preface	v
Part I. Time Granularities
Introduction	3	(8)
Formal Notion of Time Granularity	7	(1)
Temporal Databases with Multiple Granularities	8	(2)
Bibliographic Notes	10	(1)
Granularity Systems	11	(36)
Introduction	11	(1)
Formal Notions	12	(7)
Granularity Relationships	13	(4)
Properties	17	(2)
Granularity Conversion	19	(1)
Granularity Systems	19	(4)
Symbolic Representation	23	(12)
The Grouping-Oriented Operations	24	(3)
Granule-Oriented Operations	27	(4)
Syntactic Restrictions on Algebra Operations	31	(1)
Examples	32	(1)
Granularity Conversion	33	(1)
Accommodating Restrictions on Index/Label Sets	34	(1)
Expressiveness and Alternative Representations	35	(7)
Alternative Representations	37	(1)
Collections and Slices	37	(2)
Expressiveness and Relationships	39	(3)
Bibliographic Notes	42	(5)
Part II. Applications to Databases
Design of Temporal Databases with Multiple Granularities	47	(36)
Introduction	47	(3)
Temporal Dimension of Logical Design	48	(2)
Temporal Functional Dependencies	50	(7)
Inference Axioms for TFDs	52	(4)
Closure of Attributes	56	(1)
Temporal Normalization	57	(6)
Temporal Boyce-Codd Normal Form	63	(5)
Decomposing Temporal Module Schemas into TBCNF	64	(4)
Preservation of Dependencies	68	(1)
Temporal Third Normal Form	69	(4)
Decomposing Temporal Module Schemas into T3NF	70	(3)
Discussion	73	(4)
Conclusion	77	(1)
Bibliographic Notes	78	(5)
Querying Temporal Databases with Multiple Views	83	(34)
Introduction	83	(4)
Data Model	87	(2)
The Query Language MQLF	87	(2)
Point-Based Assumptions	89	(3)
An Example: Persistence	89	(1)
Syntax and Semantics of Point-Based Assumptions	90	(2)
Properties of Temporal Modules with Assumptions	92	(2)
Querying a Database with Point-Based Assumptions	94	(4)
Interval-Based Assumptions	98	(3)
An Example: Liquidity	98	(1)
Syntax and Semantics	99	(2)
Querying a Database with Interval-Based Assumptions	101	(3)
Combining Point-Based and Interval-Based Assumptions	104	(2)
Semantic Assumptions on TSQL2 Temporal Relations	106	(4)
Discussion and Conclusion	110	(2)
Bibliographic Notes	112	(5)
Part III. Reasoning with Time Granularities and Its Applications
Constraint Reasoning	117	(36)
Introduction	117	(3)
Temporal Constraint Networks with Granularities	120	(4)
Complexity of Consistency Checking	123	(1)
A Complete Algorithm	124	(11)
Operations on Periodical Sets	125	(9)
Properties of the Algorithm	134	(1)
Approximate Solutions	135	(11)
Conversion of Constraints in Different Granularities	136	(5)
Path-Consistency in a Single-Granularity Network	141	(2)
The Constraint Propagation Algorithm	143	(3)
Network Solutions	146	(2)
Discussion	148	(1)
Bibliographic Notes	149	(4)
An Application to Knowledge Discovery	153	(24)
Introduction	153	(2)
Formalization of the Discovery Problem	155	(3)
Event Structures with Multiple Granularities	156	(1)
The Discovery Problem	157	(1)
Discovering Frequent Complex Event Types	158	(4)
Timed Finite Automata with Granularities	158	(1)
Generating TAGs from Complex Event Types	159	(1)
A Naive Algorithm	160	(2)
Techniques for an Effective Discovery Process	162	(4)
Recognition of Inconsistent Event Structures	163	(1)
Reduction of the Event Sequence	163	(1)
Reduction of the Occurrences of the Reference Type	163	(1)
Reduction of the Candidate Complex Event Types	164	(2)
Effectiveness of the Process and Experimental Results	166	(6)
Experimental Results on the Discovery Process	167	(5)
Discussion and Conclusion	172	(1)
Bibliographic Notes	172	(5)
Part IV. Conclusion
Open Issues and Research Directions	177	(8)
Appendix: Proofs	185	(38)
Proofs of Results in Chap. 2	185	(3)
Proofs of Results in Chap. 3	188	(14)
Proofs of Results in Chap. 4	202	(5)
Proofs of Results in Chap. 5	207	(12)
Proofs of Results in Chap. 6	219	(4)
Bibliography	223	(6)
Index	229