A Survey of Temporal Knowledge Discovery Paradigms and Methods
---
paper_title: Advanced Database Systems

paper_content:

Advanced Database System by Carlo Zaniolo, Stefano Ceri, Christos Faloutsos, Richard T. Snodgrass, V.S. Subrahmanian, and Roberto Zicari Preface 1 Introduction Part I Active Databases 2 Syntax and Semantics of Active Databases 2.1 Starburst 2.1.1 Syntax of the Starburst CREATE RULE Statement 2.1.2 Semantics of Active Rules in Starburst 2.1.3 Other Active Rule Commands 2.1.4 Examples of Active Rule Executions 2.2 Oracle 2.2.1 Syntax of the Oracle CREATE TRIGGER Statement 2.2.2 Semantics of Oracles Triggers 2.2.3 Example of Trigger Executions 2.3 DB2 2.3.1 Syntax of the DB2 CREATE TRIGGER Statement 2.3.2 Semantics of DB2 Triggers 2.3.3. Examples of Trigger Executions 2.4 Chimera 2.4.1 Summary of Chimera 2.4.2 Syntax of the Chimera Define Trigger Statement 2.4.3 Semantics of Chimera Triggers 2.4.4 Examples of Trigger Executions 2.5 Taxonomy of Active Database Concepts 2.6 Bibliographic Notes 2.7 Exercises 3 Applications of Active Databases 3.1 Integrity Management 3.1.1 Rule Generation 3.1.2 Example 3.2 Derived Data Maintenance 3.2.1 Rule Generation 3.2.2 Example 3.3 Replication 3.4 Workflow Management 3.5 Business Rules 3.5.1 A Case Study: Energy Management System (EMS) 3.5.2 Database Schema for the EMS Case Study 3.5.3 Business Rules for the EMS Case Study 3.6 Bibliographic Notes 3.7 Exercises 4 Design Principles for Active Rules 4.1 Properties of Active Rule Execution 4.1.1 Termination 4.1.2 Confluence 4.1.3 Observable Determinism 4.2 Rule Modularization 4.2.1 Behavioral Stratification 4.2.2 Assertional Stratification 4.2.3 Event-Based Stratification 4.3 Rule Debugging and Monitoring 4.4 IDEA Methodology 4.4.1 Active Rule Design 4.4.2 Active Rule Prototyping 4.4.3 Active Rule Implementation 4.4.4 Design Tools Supporting the IDEA Methodology 4.5 Summary and Open Problems 4.6 Bibliographic Notes 4.7 Exercises Part II Temporal Databases 5 Overview of Temporal Databases 5.1 A Case Study 5.1.1 Temporal Projection 5.1.2 Temporal Join 5.1.3 Summary 5.2 The Time Domain 5.3 Time Data Types 5.4 Associating Facts with Time 5.4.1 Dimensionality 5.4.2 Underlying Data Model 5.4.3 Representative Data Models 5.5 Temporal Query Languages 5.6 Summary 5.7 Bibliographic Notes 5.8 Exercises 6 TSQL2 6.1 Time Ontology 6.2 Data Model 6.3 Language Constructs 6.3.1 Schema Definition 6.3.2 The SELECT Statement 6.3.3 Restructuring 6.3.4 Partitioning 6.3.5 The VALID Clause 6.3.6 The Modification Statements 6.3.7 Event Relations 6.3.8 Transaction-Time Support 6.3.9 Aggregates 6.3.10 Schema Evolution and Versioning 6.4 Other Constructs 6.5 Summary 6.6 Bibliographic Notes 6.7 Exercises 7 Implementation 7.1 System Architecture 7.2 Adding Temporal Support 7.2.1 DDL Compiler 7.2.2 Query Compiler 7.2.3 Run-Time Evaluator 7.3 Minimal support Needed for TSQL2 7.3.1 Data Dictionary and Data Files 7.3.2 DDL Compiler 7.3.3 Query Compiler 7.3.4 Run-Time Evaluator 7.3.5 Transaction and Data Manager 7.4 Summary and Open Problems 7.5 Bibliographic Notes 7.6 Exercises Part III Complex Queries and Reasoning 8 The Logic of Query Languages 8.1 Datalog 8.2 Relational Calculi 8.3 Relational Algebra 8.4 From Safe Datalog to Relational Algebra 8.4.1 Commercial Query Languages 8.5 Recursive Rules 8.6 Stratification 8.7 Expressive Power and Data Complexity 8.8 Syntax and Semantics of Datalog Languages 8.8.1 Syntax of First-Order Logic and Datalog 8.8.2 Semantics 8.8.3 Interpretations 8.9 The Models of a Program 8.10 Fixpoint-Based Semantics 8.10.1 Operational Semantics: Powers of Tp 8.11 Bibliographic Notes 8.12 Exercises 9 Implementation of Rules and Recursion 9.1 Operational Semantics: Bottom-Up Execution 9.2 Stratified Programs and Iterated Fixpoint 9.3 Differential Fixpoint Computation 9.4 Top-Down Execution 9.4.1 Unification 9.4.2 SLD-Resolution 9.5 Rule-Rewriting Methods 9.5.1 Left-Linear and Right-Linear Recursion 9.5.2 Magic Sets Method 9.5.3 The Counting Method 9.5.4 Supplementary Magic Sets 9.6 Compilation and Optimization 9.6.1 Nonrecursive Programs 9.6.2 Recursive Predicates 9.6.3 Selecting a Method for Recursion 9.6.4 Optimization Strategies and Execution Plan 9.7 Recursive Queries in SQL 9.7.1 Implementation of Recursive SQL Queries 9.8 Bibliographic Notes 9.9 Exercises 10 Database Updates and Nonmonotonic Reasoning 10.1 Nonmonotonic Reasoning 10.2 Stratification and Well-Founded Methods 10.2.1 Locally Stratified Programs 10.2.2 Well-Founded Models 10.3 Datalog (1s) and Temporal Reasoning 10.4 XY-Stratification 10.5 Updates and Active Rules 10.6 Nondeterministic Reasoning 10.7 Research Directions 10.8 Bibliographic Notes 10.9 Exercises Part IV Spatial, Text, and Multimedia Databases 11 Traditional Indexing Methods 11.1 Secondary Keys 11.1.1 Inverted Files 11.1.2 Grid File 11.1.3 k-D Trees 11.1.4 Conclusions 11.2 Spatial Access Methods (SAMs) 11.2.1 Space-Filling Curves 11.2.2 R-Trees 11.2.3 Transforming to Higher-D Points 11.2.4 Conclusions 11.3 Text Retrieval 11.3.1 Full Text Scanning 11.3.2 Inversion 11.3.3 Signature Files 11.3.4 Vector Space Model and Clustering 11.3.5 Conclusions 11.4 Summary and Future Research 11.5 Bibliographic Notes 11.6 Exercises 12 Multimedia Indexing 12.1 Basic Idea 12.2 GEMINI for Whole Match Queries 12.3 1-D Time Series 12.3.1 Distance Function 12.3.2 Feature Extraction and Lower-Bounding 12.3.3 Introduction to DFT 12.3.4 Energy-Concentrating Properties of DFT 12.3.5 Experiments 12.4 2-D Color Images 12.4.1 Image Features and Distance Functions 12.4.2 Lower-Bounding 12.4.3 Experiments and Conclusions 12.5 Subpattern Matching 12.5.1 Sketch of the Approach-ST-Index 12.5.2 Experiments 12.6 Summary and Future Research 12.7 Bibliographic Notes 12.8 Exercises Part V Uncertainty in Databases and Knowledge Bases 13 Models of Uncertainty 13.1 Introduction 13.1.1 Uncertainty in DBs: An Image Database Example 13.1.2 Uncertainty in DBs: A Temporal Database Example 13.1.3 Uncertainty in DBs: A Null-Value Example 13.2 Models of Uncertainty 13.2.1 Fuzzy Sets 13.2.2 Lattice-Based Approaches 13.2.3 Relationship to Fuzzy Logic 13.2.4 Probability Theory 13.3 Bibliographic Notes 13.4 Exercises 14 Uncertainty in Relational Databases 14.1 Lattice-Based Relational Databases 14.1.1 An Example 14.1.2 Querying Lattice-Based Databases 14.2 Probabilistic Relational Databases 14.2.1 Probabilistic Relations 14.2.2 Annotated Relations 14.2.3 Converting Probabilistic Tuples to Annotated Tuples 14.2.4 Manipulating Annotated Relations 14.2.5 Querying Probabilisitc Databases 14.3 Bibliographic Notes 14.4 A Final Note 14.5 Exercises 15 Including Uncertainty in Deductive Databases 15.1 Generalized Annotated Programs (GAPs) 15.1.1 Lattice-Based KBs: Model Theory 15.1.2 Lattice-Based KBs: Fixpoint Theory 15.1.3 Lattice-Based KBs: Query Processing 15.2 Probabilisic Knowledge Bases 15.2.1 Probabilistic KBs: Fixpoint Theory 15.2.2 Probabilistic KBs: Model Theory 15.2.3 Probabilistic KBs: Query Processing 15.3 Bibliographic Notes 15.4 Research Directions 15.5 Summary 15.6 Exercises Part VI Schema and Database Evolution in Object Database Systems 16 Object Databases and Change Management 16.1 Why Changes Are Needed 16.2 The Essence of Object Databases 16.2.1 Basics of Object Databases 16.2.2 Standards 16.2.3 Change Management in Object Database Systems 16.3 Bibliographic Notes 16.4 Exercises 17 How to Change the Schema 17.1 Changing the Schema Using Primitives 17.1.1 Taxonomy of Schema Modifications 17.1.2 Schema Evolution Primitives in O2 17.2 Schema Invariants 17.3 Semantics of Schema Modifications 17.4 Bibliographic Notes 17.5 Exercises 18 How to Change the Database 18.1 Immediate vs. Deferred Transformations 18.1.1 Immediate Database Trasformation 18.1.2 Deferred Database Transformation 18.2 Preserving Structural Consistency 18.2.1 Structural Consistency Preserving Primitives 18.2.2 Structural Consistency Modifying Primitives 18.3 User-Defined and Default Transformations 18.3.1 Default Database Transformations 18.3.2 User-Defined Database Transformations 18.3.3 User-Defined Object Migration Functions 18.4 Implementing Database Updates in O2 18.4.1 Problems with Deferred Database Transformations 18.4.2 Data Structures 18.4.3 the Deferred Database Update Algorithm 18.5 Related Work 18.6 Bibliographic Notes 18.7 Exercises 19 How to Change the Database Fast 19.1 Factors Influencing the Performance of a Database Transformation 19.1.1 Immediate Database Tranformation 19.1.2 Deferred Transformation 19.1.3 Hybrid 19.2 How to Benchmark Database Updates 19.2.1 Basic Benchmark Organization 19.2.2 How to Run the Benchmark 19.3 Performance Evaluation 19.3.1 Small Databases 19.3.2 Large Databases 19.4 Open Problems 19.5 Bibliographic Notes Bibliography Author Index Subject Index
---
paper_title: Maintaining knowledge about temporal intervals

paper_content:

An interval-based temporal logic is introduced, together with a computationally effective reasoning algorithm based on constraint propagation. This system is notable in offering a delicate balance between
---
paper_title: Handling discovered structure in database systems

paper_content:

Most database systems research assumes that the database schema is determined by a database administrator. With the recent increase in interest in knowledge discovery from databases and the predicted increase in the volume of data expected to be stored it is appropriate to reexamine this assumption and investigate how derived or induced, rather than database administrator supplied, structure can be accommodated and used by database systems. The paper investigates some of the characteristics of inductive learning and knowledge discovery as they pertain to database systems and the constraints that would be imposed on appropriate inductive learning algorithms is discussed. A formal method of defining induced dependencies (both static and temporal) is proposed as the inductive analogue to functional dependencies. The Boswell database system exemplifying some of these characteristics is also briefly discussed.
---
paper_title: Knowledge discovery from databases: The NYU project

paper_content:

More and more application domains, from financial market analysis to weatherprediction, from monitoring supermarket purchases to monitoring satellite images, arebecomingly increasingly data-intensive. The result is massive databases that are growingat a rapid rate - it has been estimated that the worldA¢Â¬Â"s electronic data almostdoubles every year. With this rate of data explosion, there is a pressing need for computersto play an increasing role in analyzing these huge data repositories which areimpossible to penetrate manually. The challenge is to ferret out the regularities in thedata that will prove to be interesting to the user.A group in the Information Systems department at the NYU Business School hasbeen working in this area for a number of years. The focus of our project is now on thediscovery of patterns from time series data. In this paper we give an overview of thekinds of databases we are "miningA¢Â¬Â? and the kinds of temporal patterns and rules whichwe are attempting to discover. In the first phase of this research, we have developed ataxonomy of patterns as a way to organize our research agenda. We wish to share thetaxonomy with the research community in the "knowledge discovery in databases" areasince we have found it useful in classifying the universe of regularities or patterns intodistinct types, that is, patterns which differ in terms of their structure and the amount6f search effort required to find them. Although the primary focus of our project ison time series data, and the examples we will present are chosen from this arena, thetaxonomy is general enough to apply to any type of data.
---
paper_title: A temporal logic for reasoning about processes and plans

paper_content:

Much previous work in artificial intelligence has neglected representing time in all its complexity. In particular, it has neglected continuous change and the indeterminacy of the future. To rectify this, I have developed a first-order temporal logic, in which it is possible to name and prove things about facts, events, plans, and world histories. In particular, the logic provides analyses of causality, continuous change in quantities, the persistence of facts (the frame problem), and the relationship between tasks and actions. It may be possible to implement a temporal-inference machine based on this logic, which keeps track of several “maps” of a time line, one per possible history.
---
paper_title: Maintaining knowledge about temporal intervals

paper_content:

An interval-based temporal logic is introduced, together with a computationally effective reasoning algorithm based on constraint propagation. This system is notable in offering a delicate balance between
---
paper_title: Learning to Predict Rare Events in Event Sequences

paper_content:

Learning to predict rare events from sequences of events with categorical features is an important, real-world, problem that existing statistical and machine learning methods are not well suited to solve. This paper describes timeweaver, a genetic algorithm based machine learning system that predicts rare events by identifying predictive temporal and sequential patterns. Timeweaver is applied to the task of predicting telecommunication equipment failures from 110,000 alarm messages and is shown to outperform existing learning methods.
---
paper_title: Discovering frequent event patterns with multiple granularities in time sequences

paper_content:

An important usage of time sequences is to discover temporal patterns. The discovery process usually starts with a user specified skeleton, called an event structure, which consists of a number of variables representing events and temporal constraints among these variables; the goal of the discovery is to find temporal patterns, i.e., instantiations of the variables in the structure that appear frequently in the time sequence. The paper introduces event structures that have temporal constraints with multiple granularities, defines the pattern discovery problem with these structures, and studies effective algorithms to solve it. The basic components of the algorithms include timed automata with granularities (TAGs) and a number of heuristics. The TAGs are for testing whether a specific temporal pattern, called a candidate complex event type, appears frequently in a time sequence. Since there are often a huge number of candidate event types for a usual event structure, heuristics are presented aiming at reducing the number of candidate event types and reducing the time spent by the TAGs testing whether a candidate type does appear frequently in the sequence. These heuristics exploit the information provided by explicit and implicit temporal constraints with granularity in the given event structure. The paper also gives the results of an experiment to show the effectiveness of the heuristics on a real data set.
---
paper_title: Finding temporal patterns - A set-based approach

paper_content:

We created an inference engine and query language for expressing temporal patterns in data. The patterns are represented by using temporally-ordered sets of data objects. Patterns are elaborated by reference to new objects inferred from original data, and by interlocking temporal and other relationships among sets of these objects. We found the tools well-suited to define scenarios of events that are evidence of inappropriate use of prescription drugs, using Medicaid administrative data that describe medical events. The tools' usefulness in research might be considerably more general.
---
paper_title: Data-Driven D iscovery of Quantitative Rules in Relational Databases

paper_content:

A quantitative rule is a rule associated with quantitative information which assesses the representativeness of the rule in the database. An efficient induction method is developed for learning quantitative rules in relational databases. With the assistance of knowledge about concept hierarchies, data relevance, and expected rule forms, attribute-oriented induction can be performed on the database, which integrates database operations with the learning process and provides a simple, efficient way of learning quantitative rules from large databases. The method involves the learning of both characteristic rules and classification rules. Quantitative information facilitates quantitative reasoning, incremental learning, and learning in the presence of noise. Moreover, learning qualitative rules can be treated as a special case of learning quantitative rules. It is shown that attribute-oriented induction provides an efficient and effective mechanism for learning various kinds of knowledge rules from relational databases. >
---
paper_title: Database Issues in Knowledge Discovery and Data Mining

paper_content:

In recent years both the number and the size of organisational databases have increased rapidly. However, although available processing power has also grown, the increase in stored data has not necessarily led to a corresponding increase in useful information and knowledge. This has led to a growing interest in the development of tools capable of harnessing the increased processing power available to better utilise the potential of stored data. The terms "Knowledge Discovery in Databases" and "Data Mining" have been adopted for a field of research dealing with the automatic discovery of knowledge implicit within databases. Data mining is useful in situations where the volume of data is either too large or too complicated for manual processing or, to a lesser extent, where human experts are unavailable to provide knowledge. The success already attained by a wide range of data mining applications has continued to prompt further investigation into alternative data mining techniques and the extension of data mining to new domains. This paper surveys, from the standpoint of the database systems community, current issues in data mining research by examining the architectural and process models adopted by knowledge discovery systems, the different types of discovered knowledge, the way knowledge discovery systems operate on different data types, various techniques for knowledge discovery and the ways in which discovered knowledge is used.
---
paper_title: Handling discovered structure in database systems

paper_content:

Most database systems research assumes that the database schema is determined by a database administrator. With the recent increase in interest in knowledge discovery from databases and the predicted increase in the volume of data expected to be stored it is appropriate to reexamine this assumption and investigate how derived or induced, rather than database administrator supplied, structure can be accommodated and used by database systems. The paper investigates some of the characteristics of inductive learning and knowledge discovery as they pertain to database systems and the constraints that would be imposed on appropriate inductive learning algorithms is discussed. A formal method of defining induced dependencies (both static and temporal) is proposed as the inductive analogue to functional dependencies. The Boswell database system exemplifying some of these characteristics is also briefly discussed.
---
paper_title: Data-Driven D iscovery of Quantitative Rules in Relational Databases

paper_content:

A quantitative rule is a rule associated with quantitative information which assesses the representativeness of the rule in the database. An efficient induction method is developed for learning quantitative rules in relational databases. With the assistance of knowledge about concept hierarchies, data relevance, and expected rule forms, attribute-oriented induction can be performed on the database, which integrates database operations with the learning process and provides a simple, efficient way of learning quantitative rules from large databases. The method involves the learning of both characteristic rules and classification rules. Quantitative information facilitates quantitative reasoning, incremental learning, and learning in the presence of noise. Moreover, learning qualitative rules can be treated as a special case of learning quantitative rules. It is shown that attribute-oriented induction provides an efficient and effective mechanism for learning various kinds of knowledge rules from relational databases. >
---
paper_title: An information theoretic approach to rule induction from databases

paper_content:

An algorithm for the induction of rules from examples is introduced. The algorithm is novel in the sense that it not only learns rules for a given concept (classification), but it simultaneously learns rules relating multiple concepts. This type of learning, known as generalized rule induction, is considerably more general than existing algorithms, which tend to be classification oriented. Initially, it is focused on the problem of determining a quantitative, well-defined rule preference measure. In particular, a quantity called the J-measure is proposed as an information-theoretic alternative to existing approaches. The J-measure quantifies the information content of a rule or a hypothesis. The information theoretic origins of this measure are outlined, and its plausibility as a hypothesis preference measure is examined. The ITRULE algorithm, which uses the measure to learn a set of optimal rules from a set of data samples, is defined. Experimental results on real-world data are analyzed. >
---
paper_title: Learning to Predict Rare Events in Event Sequences

paper_content:

Learning to predict rare events from sequences of events with categorical features is an important, real-world, problem that existing statistical and machine learning methods are not well suited to solve. This paper describes timeweaver, a genetic algorithm based machine learning system that predicts rare events by identifying predictive temporal and sequential patterns. Timeweaver is applied to the task of predicting telecommunication equipment failures from 110,000 alarm messages and is shown to outperform existing learning methods.
---
paper_title: What makes patterns interesting in knowledge discovery systems

paper_content:

One of the central problems in the field of knowledge discovery is the development of good measures of interestingness of discovered patterns. Such measures of interestingness are divided into objective measures-those that depend only on the structure of a pattern and the underlying data used in the discovery process, and the subjective measures-those that also depend on the class of users who examine the pattern. The focus of the paper is on studying subjective measures of interestingness. These measures are classified into actionable and unexpected, and the relationship between them is examined. The unexpected measure of interestingness is defined in terms of the belief system that the user has. Interestingness of a pattern is expressed in terms of how it affects the belief system. The paper also discusses how this unexpected measure of interestingness can be used in the discovery process.
---
paper_title: What makes patterns interesting in knowledge discovery systems

paper_content:

One of the central problems in the field of knowledge discovery is the development of good measures of interestingness of discovered patterns. Such measures of interestingness are divided into objective measures-those that depend only on the structure of a pattern and the underlying data used in the discovery process, and the subjective measures-those that also depend on the class of users who examine the pattern. The focus of the paper is on studying subjective measures of interestingness. These measures are classified into actionable and unexpected, and the relationship between them is examined. The unexpected measure of interestingness is defined in terms of the belief system that the user has. Interestingness of a pattern is expressed in terms of how it affects the belief system. The paper also discusses how this unexpected measure of interestingness can be used in the discovery process.
---
paper_title: An information theoretic approach to rule induction from databases

paper_content:

An algorithm for the induction of rules from examples is introduced. The algorithm is novel in the sense that it not only learns rules for a given concept (classification), but it simultaneously learns rules relating multiple concepts. This type of learning, known as generalized rule induction, is considerably more general than existing algorithms, which tend to be classification oriented. Initially, it is focused on the problem of determining a quantitative, well-defined rule preference measure. In particular, a quantity called the J-measure is proposed as an information-theoretic alternative to existing approaches. The J-measure quantifies the information content of a rule or a hypothesis. The information theoretic origins of this measure are outlined, and its plausibility as a hypothesis preference measure is examined. The ITRULE algorithm, which uses the measure to learn a set of optimal rules from a set of data samples, is defined. Experimental results on real-world data are analyzed. >
---
paper_title: Finding temporal patterns - A set-based approach

paper_content:

We created an inference engine and query language for expressing temporal patterns in data. The patterns are represented by using temporally-ordered sets of data objects. Patterns are elaborated by reference to new objects inferred from original data, and by interlocking temporal and other relationships among sets of these objects. We found the tools well-suited to define scenarios of events that are evidence of inappropriate use of prescription drugs, using Medicaid administrative data that describe medical events. The tools' usefulness in research might be considerably more general.
---

Title: A Survey of Temporal Knowledge Discovery Paradigms and Methods

Section 1: INTRODUCTION
Description 1: Introduce the topic of temporal data mining, its importance, and provide an overview of the paper's structure.

Section 2: THE SEMANTICS OF TEMPORAL DATA AND TEMPORAL KNOWLEDGE
Description 2: Discuss the conceptual framework for categorizing literature on temporal knowledge discovery based on types of temporal data, mining paradigms, and discovery goals.

Section 3: APRIORI-LIKE DISCOVERY OF ASSOCIATION RULES
Description 3: Examine Apriori-like mechanisms for discovering association rules in temporal data.

Section 4: TEMPLATE-BASED MINING FOR SEQUENCES
Description 4: Discuss methods for describing and discovering common trends in time series and sequence mining.

Section 5: CLASSIFICATION OF TEMPORAL DATA
Description 5: Explore ways to generalize conventional classification algorithms for temporal data and discuss classification techniques for time series and event sequences.

Section 6: MEASURING INTERESTINGNESS OF TEMPORAL PATTERNS
Description 6: Investigate methodologies for determining what constitutes interesting or useful mining results in the context of temporal data mining.

Section 7: DATA MINING REQUIREMENTS AND ENVIRONMENTS
Description 7: Examine the requirements for temporal data mining systems and provide examples of temporal mining systems, as well as discuss temporal mining within temporally aware systems.

Section 8: CONCLUSIONS AND FURTHER RESEARCH
Description 8: Summarize the findings, open issues, and suggest areas for future research in temporal data mining.