Join operations in temporal databases

Joins are arguably the most important relational operators. Poor implementations are tantamount to computing the Cartesian product of the input relations. In a temporal database, the problem is more acute for two reasons. First, conventional techniques are designed for the evaluation of joins with equality predicates rather than the inequality predicates prevalent in valid-time queries. Second, the presence of temporally varying data dramatically increases the size of a database. These factors indicate that specialized techniques are needed to efficiently evaluate temporal joins.We address this need for efficient join evaluation in temporal databases. Our purpose is twofold. We first survey all previously proposed temporal join operators. While many temporal join operators have been defined in previous work, this work has been done largely in isolation from competing proposals, with little, if any, comparison of the various operators. We then address evaluation algorithms, comparing the applicability of various algorithms to the temporal join operators and describing a performance study involving algorithms for one important operator, the temporal equijoin. Our focus, with respect to implementation, is on non-index-based join algorithms. Such algorithms do not rely on auxiliary access paths but may exploit sort orderings to achieve efficiency.Received: 17 October 2002, Accepted: 26 July 2003, Published online: 28 October 2003Edited by: T. Sellis     

Curve reconstruction based on an interval B-spline curve

Curve reconstruction that generates a piece of centric curve from a piece of planar strip-shaped point cloud is a fundamental problem in reverse engineering. In this paper, we present a new curve-reconstruction algorithm based on an interval B-spline curve. The algorithm constructs a rectangle sequence approximating the point cloud using a new data clustering technique, which facilitates the determination of curve order implied in the shape of the point cloud. A quasicentric point sequence and two pieces of boundary point sequences are then computed, based on which a piece of interval B-spline curve representing the geometric shape of the point cloud is constructed. Its centric curve is the final reconstructed curve. The whole algorithm is intuitive, simple, and efficient, as demonstrated by experimental results.     

Development of an object-oriented blackboard model for stamping process planning in progressive die design

This paper reports preliminary work to investigate the suitability of using a blackboard framework as a problem-solving model for stamping process planning in progressive die design. The model is described at two levels: knowledge level and computational level. The knowledge level describes how the stamping process planning domain is represented in a blackboard architecture. The computational level describes how the blackboard architecture is modeled and implemented using object technology. A software prototype has been developed using CLIPS and C++ interfaced with Solid Edge CAD system. An example is presented to illustrate the feasibility and practicality of the proposed approach.     

Characterizing r-perfect codes in direct products of two and three cycles

An r-perfect code of a graph G=(V,E) is a set C⊆V such that the r-balls centered at vertices of C form a partition of V. It is proved that the direct product of Cm and Cn (r?1, m,n?2r+1) contains an r-perfect code if and only if m and n are each a multiple of ²(r+1)+r² and that the direct product of Cm, Cn, and C? (r?1, m,n,??2r+1) contains an r-perfect code if and only if m, n, and ? are each a multiple of r³+³(r+1). The corresponding r-codes are essentially unique. Also, r-perfect codes in C2r×Cn (r?2, n?2r) are characterized.     

Rational Unification in 28 Characters

We present a case study where Synchronising Graphs, a system of parallel graph transformation, are used to solve the syntactic unification problem for first order rational terms (with possibly infinite unifier). The solution we offer is efficient, that is quasi-linear, and simple: a program of 28 characters.     

Gödel-Dummett Counter-models through Matrix Computation

We present a new method for deciding Gödel-Dummett logic. Starting from a formula, it proceeds in three steps. First build a conditional graph based on the decomposition tree of the formula. Then try to remove some cycles in this graph by instantiating these boolean conditions. In case this is possible, extract a counter-model from such an instance graph. Otherwise the initial formula is provable. We emphasize on cycle removal through matrix computation, boolean constraint solving and counter-model extraction.     

Group-Scheduling for Multi-Service Optical Burst Switching (OBS) Networks

We propose a new burst scheduling mechanism for Optical Burst-Switched (OBS) networks. The new approach is made possible by gathering data bursts into groups and performing the scheduling decision for each group collectively. In OBS group-scheduling, bursts will not be considered for scheduling until a pre-defined time period elapses, during which the group of burst header packets would be gathered. By transforming a set of data bursts into a set of corresponding time intervals, the problem of scheduling these bursts is transformed into a combinatorial optimization problem. Graph algorithms are applied to obtain the maximum number of non-overlapping bursts. The proposed OBS group-scheduling scheme is shown to improve the performance of OBS networks over existing scheduling schemes in terms of burst loss probability and channel utilization. With an extension through a sequential optimization, using a Branch-and-Bound technique, the proposed scheme can support multiple classes of service. It is shown that the new scheduling approach has several desired characteristics including fairness and service differentiability among classes in terms of burst loss probability and channel utilization.     

空间数据尺度的概念与逻辑小议

运用空间数据尺度有时会遇到麻烦的概念和逻辑问题,必须仔细严格划定数据的名义尺度、有序尺度、间隔尺度和比率尺度,才会避免自我矛盾。     

Time-series modeling of fishery landings using ARIMA models and Fuzzy Expected Intervals software

Forecasting, using historic time-series data, has become an important tool for fisheries management. ARIMA modeling, Modeling for Optimal Forecasting techniques and Decision Support Systems based on fuzzy mathematics may be used to predict the general trend of a given fish landings time-series with increased reliability and accuracy. The present paper applies these three modeling methods to forecast anchovy fish catches landed in a given port (Thessaloniki, Greece) during 1979–2000 and hake and bonito total fish catches during 1982–2000. The paper attempts to assess the model's accuracy by comparing model results to the actual monthly fish catches of the year 2000. According to the measures of forecasting accuracy established, the best forecasting performance for anchovy was shown by the DSS model (MAPE = 28.06%, RMSE = 76.56, U-statistic = 0.67 and R² = 0.69). The optimal forecasting technique of genetic modeling improved significantly the forecasting values obtained by the selected ARIMA model. Similarly, the DSS model showed a noteworthy forecasting efficiency for the prediction of hake landings, during the year 2000 (MAPE = 2.88%, RMSE = 13.75, U-statistic = 0.19 and R² = 0.98), as compared to the other two modeling techniques. Optimal forecasting produced by combined modeling scored better than application of the simple ARIMA model. Overall, DSS results showed that the Fuzzy Expected Intervals methodology could be used as a very reliable tool for short-term predictions of fishery landings.     

Constraints propagation techniques on intervals for a guaranteed localization using redundant data

In order to estimate continuously the dynamic location of a car, dead reckoning and absolute sensors are usually merged. The models used for this fusion are non-linear and, therefore, classical tools (such as Bayesian estimation) cannot provide a guaranteed estimation. In some applications, integrity is essential and the ability to guaranty the result is a crucial point. There are bounded-error approaches that are insensitive to non-linearity. In this context, the random errors are only modeled by their maximum bounds. This paper presents a new technique to merge the data of redundant sensors with a guaranteed result based on constraints propagation techniques on real intervals. We have thus developed an approach for the fusion of the two ABS wheel encoders of the rear wheels of a car, a fiber optic gyro and a differential GPS receiver in order to estimate the absolute location of a car. Experimental results show that the precision that one can obtain is acceptable, with a guaranteed result, in comparison with an extended Kalman filter. Moreover, constraints propagation techniques are well adapted to a real-time context.