Monitoring dynamic integrity constraints based on temporal logic

Dynamic integrity constraints are used to specify admissible sequences of database states. We present algorithmic fundamentals of monitoring constraints expressed in temporal logic. The essential means are finite transition graphs which can be constructed from temporal formulae by utilizing an appropriate normalform. To ensure admissibility of a state sequence, the integrity monitor has to follow a corresponding path through the graph and to check certain nontemporal conditions in each state; these conditions are provided as edge labels. Thus, monitoring dynamic integrity is reduced to a controlled checking of static integrity. All errors in present database behaviour are detected as well as many inevitable future errors.     

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.     

Implementing ECA rules in an active database

Traditional database systems are designed to manage large volumes of data, but rule support is generally not a strong feature. On the other hand, expert systems have the deductive capability to manage rule processing. A coupling between these two systems to support advanced database applications results in what is termed an active database. An approach to implementing active database systems is to represent knowledge as Event–Condition–Action (ECA) rules. ECA rules determine when and how to react to different kinds of events. This paper focuses on the different type of events supported by an active database CLOSE. A set of primitive and composite events is presented together with examples of their application. Event detection in this system is also discussed.     

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实现技术

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

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.     

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.     

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.     

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.     

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     

Control of Petri nets subject to strict temporal constraints using Max-Plus algebra

In this paper, we treat the control problem of timed discrete event systems under temporal constraints. This type of constraint is very frequent in production systems, transportation network and in networked automation systems. Precisely, we are interested in the validation of strict temporal constraints imposed on the paths in a timed event graph (TEG) by using Max-Plus algebra. Not all the transitions of the considered TEG model are controllable, i.e. only the input transitions are controllable. An analytical approach for computing state feedback controllers is developed. Sufficient condition is given for the existence of causal control laws satisfying the temporal constraints. In the first, a TEG with observable transitions is considered. Then, the proposed approach is extended to the partially observable TEG. The synthesised feedback can be interpreted by places of control connected to the TEG to guarantee the respect of the time constraints. The proposed method is illustrated in the assembly system example.     

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.     

Implementing an embedded compiler using program transformation rules

Domain‐specific languages (DSLs) are well‐recognized to ease programming and improve robustness for a specific domain, by providing high‐level domain‐specific notations and checks of domain‐specific properties. The compiler of a DSL, however, is often difficult to develop and maintain, because of the need to define a specific treatment for a large and potentially increasing number of language constructs. To address this issue, we propose an approach for specifying a DSL compiler using control‐flow sensitive concrete‐syntax based matching rules. These rules either collect information about the source code to carry out checks or perform transformations to carry out compilation. Because rules only mention the relevant constructs, using their concrete syntax, and hide the complexity of control‐flow graph traversal, it is easy to understand the purpose of each rule. Furthermore, new compilation steps can be added using only a small number of lines of code. We explore this approach in the context of the z2z DSL for network gateway development and show that it is beneficial to implement the core of its compiler in this manner.Copyright © 2013 John Wiley & Sons, Ltd.     

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.     

Efficient processing of integrity constraints in deductive databases

One major operation in a deductive database is to verify the contents of the database with integrity constraints whenever the database is changed. The number of facts and integrity constraints in a deductive database often makes the validation process the bottleneck of the system. In this paper, we describe a set of approaches to process integrity constraints efficiently on sequential computers and on massively parallel computers.     

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.