A resource-efficient event algebra

Events play many roles in computer systems, ranging from hardware interrupts, over event-based software architecture, to monitoring and managing of complex systems. In many applications, however, individual event occurrences are not the main point of concern, but rather the occurrences of certain event patterns. Such event patterns can be defined by means of an event algebra, i.e., expressions representing the patterns of interest are built from simple events and operators such as disjunction, sequence, etc.We propose a novel event algebra with intuitive operators (a claim which is supported by a number of algebraic properties). We also present an efficient detection algorithm that correctly detects any expression with bounded memory, which makes this algebra particularly suitable for resource-constrained applications such as embedded systems.     

Rule-based composite event queries: the language XChangeEQ and its semantics

Web systems, Web services, and Web-based publish/subscribe systems communicate events as XML messages and in many cases, require composite event detection: it is not sufficient to react to single event messages, but events have to be considered in relation to other events that are received over time. This entails a need for expressive, high-level languages for querying composite events. Emphasizing language design and formal semantics, we describe the rule-based composite event query language XChange^EQ. XChange^EQ is designed to completely cover and integrate the four complementary querying dimensions: event data, event composition, temporal relationships, and event accumulation. Semantics are provided as a model theory with accompanying fixpoint theory, an approach that is established for rule languages but has not been applied to event queries so far. Because they are highly declarative, thus easy to understand and well suited for query optimization, such semantics are desirable for event queries.     

Out-of-order durable event processing in integrated wireless networks

Many events in real world applications are long-lasting events which have certain durations. The temporal relationships among those durable events are often complex. Processing such complex events has become increasingly important in applications of wireless networks. An important issue of complex event processing is to extract patterns from event streams to support decision making in real-time. However, network latencies and machine failures in wireless networks may cause events to be out-of-order. In this work, we analyze the preliminaries of event temporal semantics. A tree-plan model of out-of-order durable events is proposed. A hybrid solution is correspondingly introduced. Extensive experimental studies demonstrate the efficiency of our approach.     

Composite event support in an active database

An intelligent or active database system is able to provide support to engineering applications, which require both data and rules to be managed. CLOSE is an active database, which integrates an object-oriented database, ObjectStore with an expert system, CLIPS. Engineering applications require a broad range of composite events, which are combinations of primitive events such as time events, method events and absolute events. This paper focuses on the design and implementation of composite events. Detection of these composite events is supported by a Rule Manager. The data structures used and the mechanism for composite event detection is described. Example applications are also presented in order to highlight the usefulness of composite events.     

Bundle event structures: A revised cpo approach

Bundle event structures equipped with a partial order ? have been used to give a true concurrency denotational semantics for LOTOS. This model has also been extended by time and stochastic information. Unfortunately it fails to yield a complete partial order (cpo) as we illustrate by an example.We propose a subset of all bundle event structures such that it forms a cpo. This subset is closed under the usual operators on bundle event structures. And as a consequence these operators are continuous. Therefore, this subset can be used to give a denotational semantics of LOTOS.     

An Event Algebra Extension of the Triggering Mechanism in a Component Model for Embedded Systems

In this article we present how the component triggering in SaveCCM, a component model intended for embedded vehicular systems, can be extended by means of an event algebra. The extension allows components to be triggered by complex event patterns, and not only by clock signals or single external events.Separating the detection of triggering conditions from the definition of the triggered services permits more general components and thus improves component reusability. Providing event detection mechanisms within the component model means that triggering conditions are explicitly available for system analysis at design time.An event algebra is used to define the complex triggering conditions. This algebra has a relatively simple declarative semantics and well documented algebraic properties, which facilitates formal and informal reasoning about the system. The algebra also ensures that detection of triggering conditions can be efficiently implemented with limited resources, which is critical in embedded applications.     

External and internal choice with event groups in Event-B

Abrial’s Event-B formalism for refinement-based system development is influenced by Back’s action system approach. Morgan has defined a CSP-like failures-divergence semantics for action systems that distinguishes internal and external choice of actions. Morgan’s semantics has the characteristic that the choice between enabled actions is external while internal choice is represented less directly through nondeterministic effect of actions. Practical experience with Event-B has demonstrated the need to be able to represent both internal and external choice between enabled events more explicitly. In this paper, Morgan’s failures semantics for action systems is modified to allow both internal and external choice to be represented directly. This is achieved by grouping events so that external choice is between event groups and internal choice is within event groups. This leads to a refinement rule for preservation of choice between event groups while allowing for reduction of choice within event groups. We also provide a refinement rule for splitting event groups in order to increase external choice. The refinement rules are justified in terms of failures refinement.     

The time model for event processing in internet of things

The time management model for event processing in internet of things has a special and important requirement. Many events in real world applications are long-lasting events which have different time granularity with order or out-of-order. The temporal relationships among those events are often complex. An important issue of complex event processing is to extract patterns from event streams to support decision making in real-time. However, current time management model does not consider the unified solution about time granularity, time interval, time disorder, and the difference between workday calendar systems in different organizations. In this work, we analyze the preliminaries of temporal semantics of events. A tree-plan model of out-of-order durable events is proposed. A hybrid solution is correspondingly introduced. A case study is illustrated to explain the time constraints and the time optimization. Extensive experimental studies demonstrate the efficiency of our approach.     

A semantics for Behavior Trees using CSP with specification commands

In this paper we give a formal definition of the requirements translation language Behavior Trees. This language has been used with success in industry to systematically translate large, complex, and often erroneous requirements documents into a structured model of the system. It contains a mixture of state-based manipulations, synchronisation, message passing, and parallel, conditional, and iterative control structures. The formal semantics of a Behavior Tree is given via a translation to a version of Hoare’s process algebra CSP, extended with state-based constructs such as guards and updates, and a message passing facility similar to that used in publish/subscribe protocols. We first provide the extension of CSP and its operational semantics, which preserves the meaning of the original CSP operators, and then the Behavior Tree notation and its translation into the extended version of CSP.     

Sequential event prediction

In sequential event prediction, we are given a “sequence database” of past event sequences to learn from, and we aim to predict the next event within a current event sequence. We focus on applications where the set of the past events has predictive power and not the specific order of those past events. Such applications arise in recommender systems, equipment maintenance, medical informatics, and in other domains. Our formalization of sequential event prediction draws on ideas from supervised ranking. We show how specific choices within this approach lead to different sequential event prediction problems and algorithms. In recommender system applications, the observed sequence of events depends on user choices, which may be influenced by the recommendations, which are themselves tailored to the user’s choices. This leads to sequential event prediction algorithms involving a non-convex optimization problem. We apply our approach to an online grocery store recommender system, email recipient recommendation, and a novel application in the health event prediction domain.     

Enhanced event structures: Towards a true concurrency semantics for E-LOTOS

E-LOTOS is a standard process-algebraic language for formal specification of real-time concurrent and reactive systems. Its originally defined semantics is based on interleaving of events. In the present paper, we propose an enhanced kind of event structures and show how to employ them to give E-LOTOS processes a branching-time true concurrency semantics. The proposed event structures can model real-time processes with data handling and excel in concise representation of event renaming and synchronization.     

主动数据库的时序事件代数

通过引入一元时序算子,表达事件之间任意杂的相对次序关系,在此基础上重新定义了描述复合件的时序事件代数,并证明了该事件代数良好的数学性质,不仅增强了事件描述语言的描述能力,也为处理规划执行的合流性提供了新的方法。     

Process algebra with action dependencies

In this paper, we present a process algebra with a minimal form of semantics for actions given by dependencies. Action dependencies are interpreted in the Mazurkiewicz sense: independent actions should be able to commute, or (from a different perspective) should be unordered, whereas dependent actions are always ordered. In this approach, the process algebra operators are used to describe the conceptual behavioural structure of the system, and the action dependencies determine the minimal necessary orderings and thereby the additionally possible parallelism within this structure. In previous work on the semantics of specifications using Mazurkiewicz dependencies, the main interest has been on linear time. We present in this paper a branching time semantics, both operationally and denotationally. For this purpose, we introduce a process algebra that incorporates, besides some standard operators, also an operator for action refinement. For interpreting the operators in the presence of action dependencies, a new concept of partial termination has to be developed. We show consistency of the operational and denotational semantics; furthermore, we give a axiomatisation of bisimilarity, which is complete for finite terms. Some small examples demonstrate the flexibility of this process algebra in the design of distributed reactive systems. Received: 19 November 1998 / 18 July 2001     

Formalizing the specification and execution of workflows using the event calculus

The event calculus is a logic programming formalism for representing events and their effects especially in database applications. This paper proposes the event calculus as a logic-based methodology for the specification and execution of workflows. It is shown that the control flow graph of a workflow specification can be expressed as a set of logical formulas and the event calculus can be used to specify the role of a workflow manager through a set of rules for the execution dependencies of activities. The proposed framework for a workflow manager maintains a history of events to control the execution of activities. The events are instructions to the workflow manager to coordinate the execution of activities. Based on the already occurred events, the workflow manager triggers new events to schedule new activities in accordance with the control flow graph of the workflow. The net effect is an alternative approach for defining a workflow engine whose operational semantics is naturally integrated with the operational semantics of a deductive database. Within this framework it is possible to model sequential and concurrent activities with or without synchronization. It is also possible to model agent assignment and execution of concurrent workflow instances. The paper, thus, contributes a logical perspective to the task of developing formalization for the workflow management systems.     

Temporal event searches based on event maps and relationships

To satisfy a user’s need to find and understand the whole picture of an event effectively and efficiently, in this paper we formalize the problem of temporal event searches and propose a framework of event relationship analysis for search events based on user queries. We define three kinds of event relationships: temporal, content dependence, and event reference, that can be used to identify to what extent a component event is dependent on another in the evolution of a target event (i.e., the query event). The search results are organized as a temporal event map (TEM) that serves as the whole picture about an event’s evolution or development by showing the dependence relationships among events. Based on the event relationships in the TEM, we further propose a method to measure the degrees of importance of events, so as to discover the important component events for a query, as well as the several algebraic operators involved in the TEM, that allow users to view the target event. Experiments conducted on a real data set show that our method outperforms the baseline method Event Evolution Graph (EEG), and it can help discover certain new relationships missed by previous methods and even by human annotators.     

Formal Semantics for Composite Temporal Events in Active Database Rules

A major thrust of current research in active databases focuses on allowing complex patterns of temporal events to serve as preconditions for rule triggering. Currently, there is no common formalism for specifying the semantics of composite event languages. Different systems have used an assortment of different techniques, including Finite State Automata, Petri Nets and Event Graphs. In this paper, we propose a unifying approach, based on a syntax-directed translation of composite event expressions into Datalog _1S rules, whose formal semantics defines the meaning of the original expressions. We demonstrate our method by providing a formal specification of the Event Pattern Language (EPL) developed at UCLA. This method overcomes problems and limitations affecting previous approaches and is applicable to other languages such as ODE, SNOOP and SAMOS—thus, allowing a more direct comparison across different systems.     

A Logical Formulation of Probabilistic Spatial Databases

There are numerous applications where there: is uncertainty over space and time. Examples of such uncertainty arise in vehicle tracking systems where we are not always sure where a vehicle is now (or may be in the future), and cell and satellite phone applications where we are not sure exactly where a phone may be, and so on. In this paper, we propose the concept of a Spatial Probabilistic Temporal (SPOT) database that contains statements of the form "Object O is in spatial region R at some time / with some probability in the interval [L, U]." We define the syntax and a declarative semantics for SPOT databases based on a mix of logic and linear programming, as well as query algebra. We show alternative implementations of some of these query algebra operators when the SPOT database has a disjoint/less property. Though the declarative semantics of SPOT databases is rooted in linear programming, we have found very efficient algorithms that do not use linear programming methods. We report on experiments we have conducted that show that the system scales to large numbers of SPOT atoms, as well as to fairly fine temporal and spatial granularity.     

统计与科学数据库上的代数操作

针对统计与科学数据库的应用要求,本文以语义数据模型MICSUM2为基础,以C—关系、原子统计表和复合统计表为操作对象,定义了统计与科学数据库上的操作。这些操作构成了C—关系、原子统计表和统计表集合上的代数,简称MS代数。MS代数从两个方面扩展了关系代数,一是MS代数操作具有更丰富的语义和更广泛的操作对象;二是MS代数包括很多支持统计分析查询的新代数操作,MS代数是构造对用户友好的统计与科学数据库查询语言的理论基础。     

Encoding a process algebra using the Event B method

This paper presents the use of the B technique in its event based definition. We show that it is possible to encode, using Event B, the models (i.e., transition systems) associated to a process algebra with asynchronous semantics. The obtained Event B models consider that the Event B model associated to the left hand side of a BNF rule defining the algebra expressions is refined by a model corresponding to the right hand side of the same rule. The translation rules of each operator of a basic process algebra are given. Then, an example illustrating each translation rule is given. This approach is based on a proof technique and therefore it does not suffer from the state number explosion problem occurring in classical model checking. The interest of this work is the capability to validate user tasks or scenarios when using a given system and particularly a critical system. Finally, we discuss the application of this approach for validating user interfaces tasks in the human–computer interaction area.     

基于事件约束的RFID复合事件误检处理

RFID数据采集的不可靠性降低了RFID应用中数据的准确性,并进一步对复合事件的检测产生影响。目前以RFID读数为粒度的清洗方法只能在一定程度上降低原始采集错误的发生频度,而复合事件检测过程又很少对其进行处理。为解决上述问题,将RFID数据从数据层抽象到逻辑语义层作为处理的粒度,提出了复合事件相互之间的约束规则,进行误检处理。通过挖掘已知复合事件之间的相关性对后续发生的事件进行误检判断,考虑了具体应用的逻辑语义,保证了RFID数据的可靠性。