Verification of an active control system using temporal process algebra

In this paper we describe complementary approaches that can be used to ensure the reliability of real-time systems, such as those used in active structural control systems. These approaches include both model-checking and simulation, and are based on a temporal process algebra. We combine these formal methods with a high-level, graphical modeling technique, Modechart, to specify an active structural control system consisting of several processors. Timing requirements on the system are specified and verified with a combination of process algebraic models and modal logic, and various simulation concepts are described for debugging models and for gaining insight into system behavior.     

The interaction of integrity constraints in an information system

Four families of integrity constraints in a relational database have been investigated: the functional dependency, the decomposition, the cross, and the inclusion. For each family, a complete set of inference rules is presented. Also, a necessary and sufficient condition for a constraint to be a consequence of other constraints of the same family is proved, using the duality between crosses and decompositions. This condition is applied and a new algorithm is presented to solve the membership problem for the decompositions.     

Rewriting queries using views with access patterns under integrity constraints

We study the problem of rewriting queries using views in the presence of access patterns, integrity constraints, disjunction and negation. We provide asymptotically optimal algorithms for (1) finding minimally containing and (2) maximally contained rewritings respecting the access patterns (which we call executable) and for (3) deciding whether an exact executable rewriting exists. We show that rewriting queries using views in this case reduces (a) to rewriting queries with access patterns and constraints without views and also (b) to rewriting queries using views under constraints without access patterns. We show how to solve (a) directly and how to reduce (b) to rewriting queries under constraints only (semantic optimization). These reductions provide two separate routes to a unified solution for problems 1, 2 and 3 based on an extension of the relational chase theory to queries and constraints with disjunction and negation. We also handle equality and arithmetic comparisons. We also show that in an information integration setting, maximally contained rewritings are given by the certain answers (under the usual semantics) for a set of constraints derived from the binding patterns. That is, except for defining the appropriate constraints, binding patterns do not need special treatment. Finally, we show that if there is an exact executable rewriting, there is an executable rewriting which is a union of conjunctive queries with negation.     

Maintenance of implication integrity constraints under updates to constraints

Semantic integrity constraints are used for enforcing the integrity of the database as well as for improving the efficiency of the database utilization. Although semantic integrity constraints are usually much more static as compared to the data itself, changes in the data semantics may necessitate corresponding changes in the constraint base. In this paper we address the problems related with maintaining a consistent and non-redundant set of constraints satisfied by the database in the case of updates to the constraint base. We consider implication constraints as semantic integrity constraints. The constraints are represented as conjunctions of inequalities. We present a methodology to determine whether a constraint is redundant or contradictory with respect to a set of constraints. The methodology is based on the partitioning of the constraint base which improves the efficiency of algorithms that check whether a constraint is redundant or contradictory with respect to a constraint base. Received August 19, 1993 / Accepted July 7, 1997     

Refining imprecise data by integrity constraints

Uncertain data in databases were originally denoted as null values, which represent the meaning of ‘values unknown at present.” Null values were generalized into partial values, which correspond to a set of possible values, to provide a more powerful notion. In this paper, we derive some properties to refine partial values into more informative ones. In some cases, they can even be refined into definite values. Such a refinement is possible when there exist range constraint on attribute domains, or referential integrities, functional dependencies, or multivalued dependencies among attributes.

Our work actually eliminates redundant elements in a partial value. By this process, we not only provide a more concise and informative answer to users, but also speedup the computation of queries issued afterward. Besides, it reduces the communication cost when imprecise data are requested to be transmitted from one site to another site in a distributed environment.     

UCDOS特显功能FOXBASE实现技术

本文介绍了用ＦＯＸＢＡＳＥ＋数据库管理系统实现ＵＣＤＯＳ特显功能的方法和技术，提高了用户界面设计的水平．     

Geometry-based propagation of temporal constraints

In recent years, the Internet of Things (IoT) has been introduced to offer promising solutions in many areas. A big challenge faced by the IoT is to integrate heterogeneous information sources and process information effectively. As an important element in information integration, temporal reasoning is highly related to the dynamic, sequential aspect of both the information integration and the decision making process. Focusing on temporal reasoning, this paper introduces a method to represent both qualitative and quantitative temporal constraints in a 2-dimensional (2-D) space. Meanwhile, an efficient constraint-based geometric (CG) algorithm for propagating constraints (including inherent constraints and constraint pairs) on events in a 2-D space is proposed. A geometric recombination and intersection (GRI) method, a part of the CG algorithm, is presented to propagate one constraint pair from a geometric point. The experimental results show that in terms of both constructed and realistic benchmarks, the CG algorithm outperforms the existing Floyd-Warshall’s algorithm with the time complexity of O(n ³), especially for benchmarks with a large number of events.     

A general treatment of dynamic integrity constraints

This paper introduces a general, set-theoretic model for expressing dynamic integrity constraints, i.e., integrity constraints on the state changes that are allowed in a given state space. In a managerial context, such dynamic integrity constraints can be seen as representations of “real world” constraints and business rules. This topic has important practical applications in many business areas. The notions of (direct) transition, reversible and irreversible transition, transition relation, and consistency of a transition relation will be introduced. The expected link with Kripke models (for modal and temporal logics) is also made explicit. Several practical examples of dynamic integrity constraints will illustrate the applicability of the theory. Some important subclasses of dynamic integrity constraints in a database context will be identified, e.g., various forms of cumulativity (which can be regarded as “transitional” inclusion dependencies concerning two different “points in time”), non-decreasing values, integrity constraints on initial and final values, life cycles, changing life cycles, and transition and constant dependencies. Several formal properties of these dependencies will be derived. For instance, it turns out that functional dependencies can be considered as “degenerated” transition dependencies. Also, the distinction between primary keys and alternate keys is reexamined, from a dynamic point of view.     

Performance analysis of long-lived cooperative transactions in active DBMS

Active database management systems (ADBMS) are used in different application domains and especially for cooperative and long duration activity management. This paper deals with performance analysis of long-lived cooperative transaction processing in an ADBMS. We first briefly discuss NP-QuadLock – a concurrency control scheme for cooperative and long durational transactions in ADBMS. A restricted version of NP-QuadLock named 2L-QuadLock has been used for simulation. We have modeled such an ADBMS supporting 2L-QuadLock scheme by a queuing model. The failure of the transactions running in such systems has been modeled by a failure recovery model. We have simulated this model for a transaction processing system serving long-lived and cooperative transactions. We also discuss some important emerging application scenarios, where the proposed cooperative complex transaction mechanism can be used (e.g. 3G-service environment, ubiquitous computing environment, feature composition in intelligent network environment, multi-site and multi-domain web-services).

An important objective of our work is to analyze quantitatively (a) the performance penalty on the system due to the partial abort, the number of locks held by a transaction, the number of states of the transactions, and (b) the gain in the performance of the system with the cooperation semantics proposed in 2L-QuadLock concurrency control mechanism. We have analyzed the effect of various parameters such as partial abort rate, cooperation rate, number of locks held by a transaction, multiprogramming level, on the performance metrics such as average service time, average saga length and the degree of compensation. Later, we characterize the application scenarios based on some important simulation parameters, and discuss the application performance needs for each of the application scenarios. The required performance parameters that need to be used for these application scenarios and the corresponding performance results using 2L-QuadLock are also discussed.     

Specification of spatial integrity constraints in pictorialdatabases

A model and a language for specifying spatial integrity constraints in pictorial databases are presented. Spatial integrity constraints are assertions about the correct behavior of database systems that specify acceptable database states and state transitions. They also serve as restrictions on positions occupied by objects in a picture. The language presented primarily uses pictures to specify constraints. The constraint pictures depict unacceptable database states. A data model provides the basic semantics for picture interpretation     

Implementing associations among classes in an environment of active databases

The association is a native concept from relational databases, one that has been adapted to object oriented (OO) modelling. It is an interesting operator used to describe links among objects of a system, commonly included in the most popular diagram-based OO methodologies. However, those methodologies sometimes present a lack of formality that may undermine its use. In this paper we formalize the semantics of associations. Firstly, we will describe an OO model based on different kinds of constraints. Some of them will be especially useful for describing the semantics of associations. Finally, we will present some remarks about implementation by means of triggers, a new feature incorporated in databases to specify an inner active behavior. This article was submitted by the authors in English.     

Localising temporal constraints in scientific workflows

Temporal constraints are often set when complex e-science processes are modelled as scientific workflow specifications. However, many existing processes such as climate modelling often have only a few coarse-grained temporal constraints globally. This is not sufficient to control overall temporal correctness as we can not find temporal violations locally in time for handling. Local handling affects fewer workflow activities, hence more cost effective than global handling with coarse-grained temporal constraints. Therefore, in this paper, we systematically investigate how to localise a group of fine-grained temporal constraints so that temporal violations can be indentified locally for better handling cost effectiveness. The corresponding algorithms are developed. The quantitative evaluation demonstrates that with local fine-grained temporal constraints, we can improve handling cost effectiveness significantly than only with coarse-grained ones.     

Validation of protocols with temporal constraints

Reachability analysis is the most popular and most used method in protocol validation. It consists in constructing a graph called a reachability graph, describing communication of machines exchanging messages through FIFO channels. The states and structure of this graph are then analysed according to given properties to validate the related communication protocol. In this paper, we deal with a generalization of reachability analysis to take into account quantitative temporal constraints in protocol validation. A temporal reachability graph is designed, and we show how it can be used to analyse new general properties of communication protocols submitted to temporal constraints.     

The ramification problem in temporal databases: an approach with conflicting constraints

In this paper we study the ramification problem in the setting of temporal databases. Standard solutions from the literature on reasoning about action are inadequate because they rely on the assumption that fluents persist, and because actions have effects on the next situation only. In this paper we provide a solution to the ramification problem based on an extension of the situation calculus and the work of McCain and Turner. More specifically, we study the case where there are conflicting effects of an action, a particularly complex problem. Also we present a tool which implements the proposed solution.     

数据完整性约束机制的差异性和优先级

数据完整性约束用以保证数据库中数据的正确性、一致性和可靠性。本文分析阐述数据完整性约束类型的差异性和具体实现的约束方法,并通过实验验证对特定字段设置同一类数据完整性约束的方法存在优先级,设置不同类间的数据完整性约束的方法也存在优先级。     

The integrity constraints for similarity-based fuzzy relational databases

This paper first introduces a new definition for the conformance of tuples existing in a similarity-based fuzzy database relation. Then the formal definitions of fuzzy functional and multivalued dependencies are given on the basis of the conformance values presented here. These dependencies are defined to represent relationships between domains of the same relation that exist. The definitions of the fuzzy dependencies presented in this study allow a sound and complete set of inference rules. In this paper, we include examples to demonstrate how the integrity constraints imposed by these dependencies are enforced whenever a tuple is to be inserted or to be modified in a fuzzy database relation. © 1998 John Wiley & Sons, Inc.     

Semantic integrity enforcement in centralized DBMS and distributed DBMS based on slow (geographically distributed) and fast (local area) networks

In this paper we investigate techniques for decreasing the overhead of semantic integrity enforcement or equivalently the overhead of transaction validation with respect to a set of semantic integrity (SI) assertions. We discuss the problem of semantic integrity enforcement from two points of view. First we describe three approaches to decrease the overhead of SI enforcement. Second we analyze the cost of several SI enforcement methods in centralized and distributed database systems based on slow and fast (local) networks.     

Finite satisfiability of integrity constraints in object-orienteddatabase schemas

Checking satisfiability of database constraints is a fundamental problem in database design. In addition, database constraints have to be not only satisfiable but also finitely satisfiable. This problem is generally addressed by using theorem provers that, being developed for first order logic formulas, are based on semidecidable procedures. Furthermore, even in simple cases, theorem provers are quite inefficient in dealing with comparison operators such as, for instance, the equality. In this paper, a decidable, sound, and complete method for checking finite satisfiability of a specific class of integrity constraints for object-oriented databases, including the equality constraints, is presented. The method, that is based on a graph-theoretic approach, has exponential complexity in the worst case, rarely occurring in practice     

Implementing an extended functional data model using PS-algol

A number of data models have been proposed in the literature to improve the usability of database systems. Most of these proposals have not been implemented. It is felt that a working implementation is a necessary prerequisite for a serious study of these proposals. So far, implementing data models has been a daunting task, requiring a large team. We report here on a simple implementation technique using the persistent algorithmic language. PS-algol, which promises to make the task of implementing data models a manageable one. The feasibility of the approach is demonstrated by implementing an entity-based functional data model (extended function data model) using PS-algol.