Supporting User-Defined Granularities in a Spatiotemporal Conceptual Model

Granularities are integral to spatial and temporal data. A large number of applications require storage of facts along with their temporal and spatial context, which needs to be expressed in terms of appropriate granularities. For many real-world applications, a single granularity in the database is insufficient. In order to support any type of spatial or temporal reasoning, the semantics related to granularities needs to be embedded in the database. Specifying granularities related to facts is an important part of conceptual database design because under-specifying the granularity can restrict an application, affect the relative ordering of events and impact the topological relationships. Closely related to granularities is indeterminacy, i.e., an occurrence time or location associated with a fact that is not known exactly. In this paper, we present an ontology for spatial granularities that is a natural analog of temporal granularities. We propose an upward-compatible, annotation-based spatiotemporal conceptual model that can comprehensively capture the semantics related to spatial and temporal granularities, and indeterminacy without requiring new spatiotemporal constructs. We specify the formal semantics of this spatiotemporal conceptual model via translation to a conventional conceptual model. To underscore the practical focus of our approach, we describe an on-going case study. We apply our approach to a hydrogeologic application at the United States Geologic Survey and demonstrate that our proposed granularity-based spatiotemporal conceptual model is straightforward to use and is comprehensive.     

A complete temporal relational algebra

Various temporal extensions to the relational model have been proposed. All of these, however, deviate significantly from the original relational model. This paper presents a temporal extension of the relational algebra that is not significantly different from the original relational model, yet is at least as expressive as any of the previous approaches. This algebra employs multidimensional tuple time-stamping to capture the complete temporal behavior of data. The basic relational operations are redefined as consistent extensions of the existing operations in a manner that preserves the basic algebraic equivalences of the snapshot (i.e., conventional static) algebra. A new operation, namely temporal projection, is introduced. The complete update semantics are formally specified and aggregate functions are defined. The algebra is closed, and reduces to the snapshot algebra. It is also shown to be at least as expressive as the calculus-based temporal query language TQuel. In order to assess the algebra, it is evaluated using a set of twenty-six criteria proposed in the literature, and compared to existing temporal relational algebras. The proposed algebra appears to satisfy more criteria than any other existing algebra. Edited by Wesley Chu. Received February 1993 / Accepted April 1995     

Symbolic user-defined periodicity in temporal relational databases

Calendars and periodicity play a fundamental role in many applications. Recently, some commercial databases started to support user-defined periodicity in the queries in order to provide "a human-friendly way of handling time" (see, e.g., TimeSeries in Oracle 8). On the other hand, only few relational data models support user-defined periodicity in the data, mostly using "mathematical" expressions to represent periodicity. In this paper, we propose a high-level "symbolic" language for representing user-defined periodicity which seems to us more human-oriented than mathematical ones, and we use the domain of Gadia's temporal elements in order to define its properties and its extensional semantics. We then propose a temporal relational model which supports user-defined "symbolic" periodicity (e.g., to express "on the second Monday of each month") in the validity time of tuples and also copes with frame times (e.g., "from 1/1/98 to 28/2/98"). We define the temporal counterpart of the standard operators of the relational algebra, and we introduce new temporal operators and functions. We also prove that our temporal algebra is a consistent extension of the classical (atemporal) one. Moreover, we define both a fully symbolic evaluation method for the operators on the periodicities in the validity times of tuples, which is correct but not complete, and semisymbolic one, which is correct and complete, and study their computational complexity.     

不确定时态信息表示的统一模型

时态信息表示和推理是人工智能研究中的一个重要课题,现有的模型大多只能表示确定时态信息,然而现实生活中很多事件的发生结束等时态信息都是不确定的。故提出了一个表示不确定时态信息的统一模型,可用于描述各种具有确定或不确定时态信息的事件。该模型首先定义各类时态对象(如时间点、时间区间)以及它们之间的关系,并给出时态对象间的传递关系表,利用该表能进行时态一致性约束满足问题的求解。最后,给出了两个不确定时态推理的例子,表明了该模型的实际应用意义。     

Qualitative and quantitative temporal constraints and relationaldatabases: theory, architecture, and applications

Many different applications in different areas need to deal with both: databases, in order to take into account large amounts of structured data; and quantitative and qualitative temporal constraints about such data. We propose an approach that extends: temporal databases and artificial intelligence temporal reasoning techniques and integrate them in order to face such a need. Regarding temporal reasoning, we consider some results that we proved recently about efficient query answering in the Simple Temporal Problem framework and we extend them in order to deal with partitioned sets of constraints and to support relational database operations. Regarding databases, we extend the relational model in order to consider also qualitative and quantitative temporal constraints both in the data (data expressiveness) and in the queries (query expressiveness). We then propose a modular architecture integrating a relational database with a temporal reasoner. We also consider classes of applications that fit into our approach and consider patient management in a hospital as an example     

基于BCDM的含有变量的双时态关系代数研究*

在BCDM(双时态概念数据模型)中,时间变元Now和UC的存在解决了时态记录的频繁更新问题;但是时态变元的存在又给数据库的操作带来某种不确定性甚至是错误,同时引起关系代数运算的歧义。基于BCDM,通过绑定时间变元,用时态映射的集合定义时态关系,由此建立了一种含有时间变元的双时态关系代数体系。该关系代数体系在双时态运算下是封闭的。     

Reconciling point-based and interval-based semantics in temporal relational databases: a treatment of the Telic/Atelic distinction

The analysis of the semantics of temporal data and queries plays a central role in the area of temporal databases. Although many different algebrae and models have been proposed, almost all of them are based on a point-based (snapshot) semantics for data. On the other hand, in the areas of linguistics, philosophy, and recently, artificial intelligence, an oft-debated issue concerns the use of an interval-based versus a point-based semantics. In this paper, we first show some problems inherent in the adoption of a point-based semantics for data, then argue that these problems arise because there is no distinction drawn in the data between telic and atelic facts. We then introduce a three-sorted temporal model and algebra including coercion functions for transforming relations of one sort into relations of the other at query time which properly copes with these issues.     

An intensional approach for periodic data in relational databases

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.     

Applying the persistent set approach in temporal reasoning

Since Hanks and McDermott raised the problem of temporal projection (e.g. the Yale shooting problem) and showed that classical nonmonotonic logics failed to solve it, many solutions have been proposed. However, as indicated by some researchers, most of them are not completely satisfactory. In Zhang and Foo [22], we presented a theory of actions called thepersistent set approach (PSA). In this paper, we extend our previous work to deal with temporal reasoning. Different from those minimality-based approaches, we propose a persistence-based formalization of actions within the situation calculus framework, and show that this gives natural and intuitive solutions to the problem of temporal projection in many cases. Explanations of some of the differences between persistence and minimality are given. We show that our approach also provides a unified framework for representing actions with disjunctive effects, while most of the current methods are inappropriate for dealing with these actions in the general case.     

Querying now-relative data

Now-relative temporal data play an important role in most temporal applications, and their management has been proved to impact in a crucial way the efficiency of temporal databases. Though several temporal relational approaches have been developed to deal with now-relative data, none of them has provided a whole temporal algebra to query them. In this paper we overcome such a limitation, by proposing a general algebra which is parametrically adapted to cope with the relational approaches to now-relative data in the literature, i.e., MIN, MAX, NULL and POINT approaches. Besides being general enough to provide a query language for several approaches in the literature, our algebra has been designed in such a way to satisfy several theoretical and practical desiderata: closure with respect to representation languages, correctness with respect to the “consensus” BCDM semantics, reducibility to the standard non-temporal algebra (which involves interoperability with non-temporal relational databases), implementability and efficiency. Indeed, the experimental evaluation we have drawn on our implementation has shown that only a slight overhead is added by our treatment of now-relative data (with respect to an approach in which such data are not present).     

Relational completeness of query languages for annotated databases

Annotated relational databases can be queried either by simply making the annotations explicitly available along the ordinary data, or by adapting the standard query operators so that they have an implicit effect also on the annotations. We compare the expressive power of these two approaches. As a formal model for the implicit approach we propose the color algebra, an adaptation of the relational algebra to deal with the annotations. We show that the color algebra is relationally complete: it is equivalent to the relational algebra on the explicit annotations. Our result extends a similar completeness result established for the query algebra of the MONDRIAN annotation system, from unions of conjunctive queries to the full relational algebra. We also show that the color algebra is nonredundant: no operator can be expressed in terms of the other operators. We also present a generalization of the color algebra that is relationally complete in the presence of built-in predicates on the annotations.     

Relational similarity-based model of data part 1: foundations and query systems

We present a general rank-aware model of data which supports handling of similarity in relational databases. The model is based on the assumption that in many cases it is desirable to replace equalities on values in data tables by similarity relations expressing degrees to which the values are similar. In this context, we study various phenomena which emerge in the model, including similarity-based queries and similarity-based data dependencies. Central notion in our model is that of a ranked data table over domains with similarities which is our counterpart to the notion of relation on relation scheme from the classical relational model. Compared to other approaches which cover related problems, we do not propose a similarity-based or ranking module on top of the classical relational model. Instead, we generalize the very core of the model by replacing the classical, two-valued logic upon which the classical model is built by a more general logic involving a scale of truth degrees that, in addition to the classical truth degrees 0 and 1, contains intermediate truth degrees. While the classical truth degrees 0 and 1 represent nonequality and equality of values, and subsequently mismatch and match of queries, the intermediate truth degrees in the new model represent similarity of values and partial match of queries. Moreover, the truth functions of many-valued logical connectives in the new model serve to aggregate degrees of similarity. The presented approach is conceptually clean, logically sound, and retains most properties of the classical model while enabling us to employ new types of queries and data dependencies. Most importantly, similarity is not handled in an ad hoc way or by putting a “similarity module” atop the classical model in our approach. Rather, it is consistently viewed as a notion that generalizes and replaces equality in the very core of the relational model. We present fundamentals of the formal model and two equivalent query systems which are analogues of the classical relational algebra and domain relational calculus with range declarations. In the sequel to this paper, we deal with similarity-based dependencies.     

The relational model with relation-valued attributes

Motivated by new applications of database systems we introduce relations which may have relation-valued attributes and propose a related algebra. Formal definitions for this extended relational model can be given by applying usual notions recursively. The main problem considered in this paper is the formal definition of an appropriate relational algebra for these non-first-normal-form relations. We allow the application of the basic relational operators to any relation-valued attribute within a relation. This leads to a (hierarchically) nested relational algebra.     

A comparison of two approaches to utilizing XML in parametric databases for temporal data

The parametric data model captures an object in terms of a single tuple. This feature eliminates unnecessary self-join operations to combine tuples scattered in a temporal relation. Despite this advantage, this model is relatively difficult to implement on top of relational databases because the sizes of attributes are unfixed. Since data boundaries are not problematic in XML, XML can be an elegant solution to implement parametric databases for temporal data. There are two approaches to implementing parametric databases using XML: (1) a native XML database with XQuery engine, and (2) an XML storage with a temporal query language. To determine which approach is appropriate in parametric databases, we consider four questions: the effectiveness of XML in modeling temporal data, the applicability of XML query languages, the user-friendliness of the query languages, and system performances of two approaches. By evaluating the four questions, we show that the latter approach is more appropriate to utilizing XML in parametric databases.     

Representation and Reasoning with Multi-Point Events

Allen's Interval Algebra (IA) and Vilain & Kautz's Point Algebra (PA) consider an interval and a point as basic temporal entities (i.e., events) respectively. However, in many situations we need to deal with recurring events that include multiple points, multiple intervals or combinations of points and intervals. In this paper, we present a framework to model recurring events as multi-point events (MPEs) by extending point algebra. The reasoning tasks are formulated as binary constraint satisfaction problems. We propose a polynomial time algorithm (based on van Beek's algorithm) for finding all feasible relations. For the problem of finding a consistent scenario, we propose a backtracking method with a local search heuristic. We also describe an implementation and a detail empirical evaluation of the proposed algorithms. Our empirical results indicate that the MPE-based approach performs better than the existing approaches.     

Exploiting temporal information in Web search

Time plays important roles in Web search, because most Web pages contain temporal information and a lot of Web queries are time-related. How to integrate temporal information in Web search engines has been a research focus in recent years. However, traditional search engines have little support in processing temporal-textual Web queries. Aiming at solving this problem, in this paper, we concentrate on the extraction of the focused time for Web pages, which refers to the most appropriate time associated with Web pages, and then we used focused time to improve the search efficiency for time-sensitive queries. In particular, three critical issues are deeply studied in this paper. The first issue is to extract implicit temporal expressions from Web pages. The second one is to determine the focused time among all the extracted temporal information, and the last issue is to integrate focused time into a search engine. For the first issue, we propose a new dynamic approach to resolve the implicit temporal expressions in Web pages. For the second issue, we present a score model to determine the focused time for Web pages. Our score model takes into account both the frequency of temporal information in Web pages and the containment relationship among temporal information. For the third issue, we combine the textual similarity and the temporal similarity between queries and documents in the ranking process. To evaluate the effectiveness and efficiency of the proposed approaches, we build a prototype system called Time-Aware Search Engine (TASE). TASE is able to extract both the explicit and implicit temporal expressions for Web pages, and calculate the relevant score between Web pages and each temporal expression, and re-rank search results based on the temporal-textual relevance between Web pages and queries. Finally, we conduct experiments on real data sets. The results show that our approach has high accuracy in resolving implicit temporal expressions and extracting focused time, and has better ranking effectiveness for time-sensitive Web queries than its competitor algorithms.     

构建面向对象时态数据模型的研究

本文通过对现存关系数据库和面向对象数据库的比较分析，总结其优点与不足，并在结合了二者优点的UniSQL/X模型基地上，对该模型进行时态上的扩展，使它能够记录和处理时态信息。在查询代数中，引入了一 些特殊的时态操作，通过聚集、概括和时间参考三种关联对对象进行访问，而且此代数同时反映了时态关系代数和对象代数的特点。     

Arbitrage pricing theory-based Gaussian temporal factor analysis for adaptive portfolio management

Ever since the inception of Markowitz's modern portfolio theory, static portfolio optimization techniques were gradually phased out by dynamic portfolio management due to the growth of popularity in automated trading. In view of the intensive computational needs, it is common to use machine learning approaches on Sharpe ratio maximization for implementing dynamic portfolio optimization. In the literature, return-based approaches which directly used security prices or returns to control portfolio weights were often used. Inspired by the arbitrage pricing theory (APT), some other efforts concentrate on indirect modelling using hidden factors. On the other hand, with regard to the proper risk measure in the Sharpe ratio, downside risk was considered a better substitute for variance. In this paper, we investigate how the Gaussian temporal factor analysis (TFA) technique can be used for portfolio optimization. Since TFA is based on the classical APT model and has the benefit of removing rotation indeterminacy via temporal modelling, using TFA for portfolio management allows portfolio weights to be indirectly controlled by several hidden factors. Moreover, we extend the approach to some other variants tailored for investors according to their investment objectives and degree of risk tolerance.     

Qualitative-probabilistic-network-based modeling of temporal causalities and its application to feedback loop identification

Modeling and analysis of time-series data attract much attention in data mining and knowledge discovery community due to their many applications in financial analysis, automation control, etc. In such applications, time-series data usually contain several attributes that may be causally dependent in historical time slices. Dangerous feedback loops of attributes’ dependent relationships can make the system collapse due to amplification or oscillation of attribute values. Motivated by efficient analysis of causalities in time-series data, we propose a temporal qualitative probabilistic graphical model in this paper. From given time-series sample data, we construct the structure of the temporal qualitative probabilistic network (TQPN) and derive the corresponding qualitative influences on directed edges. We then present the approach for TQPN reasoning with time-series features. Consequently, positive time-series feedback loops are defined, and the approach to identify them is proposed. Preliminary experiments show that our proposed method is not only feasible but also efficient.     

Extending CLIPS to support temporal representation and reasoning

Applications using expert systems for monitoring and control problems often require the ability to represent temporal knowledge and to apply reasoning based on that knowledge. Incorporating temporal representation and reasoning into expert systems leads to two problems in development: dealing with an implied temporal order of events using a non-procedural tool; and maintaining the large number of temporal relations that can occur among facts in the knowledge base. In this paper we explore these problems by using an expert system shell, CLIPS (C Language Integrated Production System), to create temporal relations using common knowledge-based constructs. We also build an extension to CLIPS through a user-defined function which generates the temporal relations from those facts. We use the extension to create and maintain temporal relations in a workflow application that monitors and controls an engineering design change review process. We also propose a solution to ensure truth maintenance among temporally related facts that links our temporal extension to the CLIPS facility for truth maintenance.