ArchIS: an XML-based approach to transaction-time temporal database systems

Effective support for temporal applications by database systems represents an important technical objective that is difficult to achieve since it requires an integrated solution for several problems, including (i) expressive temporal representations and data models, (ii) powerful languages for temporal queries and snapshot queries, (iii) indexing, clustering and query optimization techniques for managing temporal information efficiently, and (iv) architectures that bring together the different pieces of enabling technology into a robust system. In this paper, we present the ArchIS system that achieves these objectives by supporting a temporally grouped data model on top of RDBMS. ArchIS’ architecture uses (a) XML to support temporally grouped (virtual) representations of the database history, (b) XQuery to express powerful temporal queries on such views, (c) temporal clustering and indexing techniques for managing the actual historical data in a relational database, and (d) SQL/XML for executing the queries on the XML views as equivalent queries on the relational database. The performance studies presented in the paper show that ArchIS is quite effective at storing and retrieving under complex query conditions the transaction-time history of relational databases, and can also assure excellent storage efficiency by providing compression as an option. This approach achieves full-functionality transaction-time databases without requiring temporal extensions in XML or database standards, and provides critical support to emerging application areas such as RFID.     

A temporal logic approach to object certification

A brief overview is made of the use of temporal logic formalisms for specifying and verifying concurrent systems in general and information systems in particular. The requirements imposed by object-orientation on such formalisms are examined. A logic is proposed fulfilling those requirements (except concerning non-monotonic features), allowing the uniform treatment of both local and global properties of systems with concurrent, interacting components organized in classes, and supporting specialization. A semantics and a calculus (following an axiomatic, Hilbert style) are presented in detail. The calculus includes rules for the sound inheritance and reflection of theorems between classes. Practical aspects of the usage of such a logic for both specification and verification are considered. To this end a set of metatheorems is provided for expediting the proof of invariants. Finally, the need and availability of automatic theorem proving for systems querying is briefly discussed.     

Carla: A rule language for specifying communications architectures

Due to the unique requirements of a series of projects to specify communications architectures using graphical representations (Cara and MFD), we have developed the communications-oriented rule-based language Carla (Cara Rule Language), which provides an executable specification of the architecture being developed. Carla is designed to provide the ability to specify and simulate high-level, possibly incomplete, specifications of communications architectures, and to allow the developer to refine the specification through the addition of behavior-describing rules. Carla is also well-suited to creating black-box specifications of any system whose behavior depends on input/output history. We describe the features of the language, discuss various design issues, and provide examples of various communications protocols specified in Carla.     

Vibes: A visual language for specifying behavioral requirements of algorithms

Manually verifying the behavior of software systems with respect to a set of requirements is a time-consuming and error-prone task. If the verification is automatically performed by a model checker however, time can be saved, and errors can be prevented. To be able to use a model checker, requirements need to be specified using a formal language. Although temporal logic languages are frequently used for this purpose, they are neither commonly considered to have sufficient usability, nor always naturally suited for specifying behavioral requirements of algorithms. Such requirements can be naturally specified as regular language recognizers such as deterministic finite accepters, which however suffer from poor evolvability: the necessity to re-compute the recognizer whenever the alphabet of the underlying model changes. In this paper, we present the visual language Vibes that both is naturally suited for specifying behavioral requirements of algorithms, and enables the creation of highly evolvable specifications. Based on our observations from controlled experiments with 23 professional software engineers and 21 M.Sc. computer science students, we evaluate the usability of Vibes in terms of its understandability, learnability, and operability. This evaluation suggests that Vibes is an easy-to-use language.     

A safe regression testing approach for safety critical systems

Regression testing is important activity during the software maintenance to deal with adverse effects of changes. Our approach is important for safety critical system as usually formal methods are preferred and highly recommended for the safety critical systems but they are also applied for the systems development of other than critical system. Our approach is based on Regression testing using VDM++ which takes two VDM++ specifications, one baseline and other delta (Changed) along with test suite for the baseline version. It compares both versions by using comparator module, identifies the change. By analyzing the change we classify the test cases from original test suite into obsolete, re-testable, and reusable test cases. Our scope is at unit level i.e. at class level. Our approach gets two versions of VDM++ specification and returns regression test suite for the delta version. Our approach distinguishes test cases which are still effective for the delta version of VDM++ specification and it differs from re-test all strategy as it can distinguish the test cases and identifies test cases which are useful for delta version. Test cases reusability and test case reduction is the main objective of our approach. Our approach presents how to perform regression testing using VDM++ specification during the maintenance of systems.     

Protocol design for an automated highway system

A structured use of control, communication and computing techologies in vehicles and in the highway can lead to major increases in highway capacity. Our context is an automated highway system (AHS) in which traffic is organized in platoons of closely spaced vehicles under automatic control. The AHS control tasks are arranged in a three-layer hierarchy. At the top or link layer a centralized controller assigns to each vehicle a path through the highway and sets the target size and speed for platoons to reduce congestion. The remaining two layers are distributed among controllers on each vehicle. A vehicle's platoon layer plans its trajectory to conform to its assigned path and to track the target size. The plan consists of a sequence of elementary maneuvers: merge (combines two platoons into one), split (separates one platoon into two), and change lane (enables a single car to change lane). Once the protocol layer determines that a particular maneuver can safely be initiated, it instructs its regulation layer to execute the corresponding precomputed feedback control law which implements the maneuver. This paper focuses on the design of the platoon layer. In order of ensure that it is safe to initiate a maneuver, the platoon layer controller enters into a negotiation with its neighbors. This negotiation is implemented as a protocol—a structured sequence of message exchanges. After a protocol terminates successfully, the movement of the vehicles involved is coordinated and the maneuver can be initiated. A protocol is designed in two stages. In the first stage, the protocol is described as an informal state machine, one machine per vehicle. The informal state machine does not distinguish between actions and conditions referring to the vehicle's environment and those referring to the protocol itself. In the second stage this distinction is enforced and the protocol machines are specified in the formal language COSPAN. COSPAN software is then used to show that the protocol indeed works correctly. One can now be reasonably confident that, properly implemented, the protocol designed here will work as intended.Work supported by the PATH program, Institute of Transportation Studies, University of California, Berkeley, and NSF Grant ECS-911907. It is a pleasure to thank Dr. Bob Kurshan for providing COSPAN and explaining its use, Ellen Sentovich for help with COSPAN, Max Holm for computer support, Anuj Puri for comments which improved parts of the design, and members of the PATH Seminar on AVCS where this design was first presented and discussed. The authors alone are responsible for the views expressed here.     

Managing requirements specifications for product lines - An approach and industry case study

Software product line development has emerged as a leading approach for software reuse. This paper describes an approach to manage natural-language requirements specifications in a software product line context. Variability in such product line specifications is modeled and managed using a feature model. The proposed approach has been introduced in the Swedish defense industry. We present a multiple-case study covering two different product lines with in total eight product instances. These were compared to experiences from previous projects in the organization employing clone-and-own reuse. We conclude that the proposed product line approach performs better than clone-and-own reuse of requirements specifications in this particular industrial context.     

Making Web services tradable: A policy-based approach for specifying preferences on Web service properties

In service-oriented architectures, applications are developed by incorporating services which are often provided by different organizations. Since a service might be offered under different configurations by various different organizations, sophisticated service selection and negotiation algorithms are required. Policies capture the conditions under which services are offered or requested and thereby constrain the negotiation space. However, current policy languages are ill-suited to realize beneficial trade-offs within a negotiation, since they support only Boolean decisions and cannot capture all relevant service information.Therefore, we present a novel policy language in this work that provides two main contributions: (i) we enable the specification of constraints on functional as well as non-functional properties of Web services. The functional properties include data objects and the behaviour, whereas the non-functional properties include QoS attributes. (ii) Given such constraints, we show how the concept of utility function policies can be used to define cardinal preferences over functional as well as non-functional properties. This is required to rank Web service offers, define their prices, and consequently to realize automated negotiations between service providers and requesters.     

Scen@rist: an approach for verifying self-adaptive systems using runtime scenarios

Software Quality Journal - Traditional runtime quantitative verification approaches for self-adaptive systems usually rely on the use of state-transition models to describe the system behaviour and...     

Distributed simulation of modular time Petri nets: An approach and a case study exploiting temporal uncertainty

This paper proposes an approach to modular modelling and simulation of complex time-critical systems. The modelling language is represented by Merlin and Farber’s Time Petri Nets (TPNs) augmented with inhibitor arcs and modular constructs borrowed from the Petri Net Markup Language (PNML) interchange format. Analysis techniques depend on Temporal Uncertainty Time Warp (TUTW), a time warp algorithm capable of exploiting temporal uncertainty in general optimistic simulations over a networked context. A key feature of the approach is the fact that TPN models naturally exhibit a certain degree of temporal uncertainty which the TUTW control engine can exploit to achieve good speedup without a loss in the accuracy of the simulation results. The developed TUTW/TPN kernel is demonstrated by modelling and simulation of a real-time system example.A preliminary version of this paper was presented at 38th SCS Annual Simulation Symposium, April 4–6, 2005, San Diego (CA), IEEE Computer Society, pp. 233–240. Franco Cicirelli achieved a PhD in computer science from the University of Calabria (Unical), DEIS—department of electronics informatics and systems science. As a postdoc, he is making research on agent and service paradigms for the development of distributed systems, parallel simulation, Petri nets, distributed measurement systems. He holds a membership with ACM. Angelo Furfaro, PhD, is a computer science assistant professor at Unical, DEIS, teaching object-oriented programming. His research interests are centred on: multi-agent systems, modeling and analysis of time-dependent systems, Petri nets, parallel simulation, verification of real-time systems, distributed measurement systems. He is a member of ACM. Libero Nigro is a full professor of computer science at Unical, DEIS, where he teaches object-oriented programming, software engineering and real-time systems courses. He directs the Software Engineering Laboratory (www.lis.deis.unical.it). His current research interests include: software engineering of time-dependent and distributed systems, real-time systems, Petri nets, modeling and parallel simulation of complex systems, distributed measurement systems. Prof. Nigro is a member of ACM and IEEE.     

VVSL: A language for structured VDM specifications

VVSL is a VDM specification language of the British School with modularisation constructs allowing sharing of hidden state variables and parameterisation constructs for structuring specifications, and with constructs for expressing temporal aspects of the concurrent execution of operations which interfere via state variables. The modularisation and parameterisation constructs have been inspired by the kernel design language COLD-K from the ESPRIT project 432: METEOR, and the constructs for expressing temporal aspects by various temporal logics based on linear and discrete time. VVSL is provided with a well-defined semantics by defining a translation to COLD-K extended with constructs which are required for translation of the VVSL constructs for expressing temporal aspects.In this paper, the syntax for the modularisation and parameterisation constructs of VVSL is outlined. Their meaning is informally described by giving an intuitive explanation and by outlining the translation to COLD-K. It is explained in some detail how sharing of hidden state variables is modelled. Examples of the use of the modularisation and parameterisation constructs are also given. These examples are based on a formal definition of the relational data model. With respect to the constructs for expressing temporal aspects, the ideas underlying the use of temporal formulae in VVSL are briefly outlined and a simple example is given.     

Architecture design for internet-based control systems

The Internet is playing an important role in information retrieval, and additionally industrial process manipulation. This paper describes an approach to writing requirements specifications for Internet-based control systems, from which architectures can be derived. The requirements specifications developed are described in terms of a functional model, which is then extended to form an information architecture. Distinct from the functional model, the information architecture provides an indication as to the architectural structure of subsequently developed Internet-based control systems. Three general control structures are generated from the analysis of an information architecture. An integrated-distributed architecture is derived as an ideal implementation, in which a control system is linked to the Internet at all levels of a control system hierarchy.     

A temporal logic approach to discrete event control for the safety canonical class

This paper presents a temporal logic formulation of discrete event control which forms a new theoretical basis for control analysis and synthesis of a class of discrete event systems (DES). Based on the formulation, a basic supervisory control theory is developed for a control objective specified by an invariance formula belonging to the safety canonical class of Manna and Pneuli. Using the safety canonical class as a basis, the refinement and generalization of the existing basic predicate framework are demonstrated. A simple example illustrates the formal axiomatic means to perform control-theoretic analysis and synthesis under the new formulation.     

Point algebras for temporal reasoning: Algorithms and complexity

We investigate the computational complexity of temporal reasoning in different time models such as totally-ordered, partially-ordered and branching time. Our main result concerns the satisfiability problem for point algebras and point algebras extended with disjunctions—for these problems, we identify all tractable subclasses. We also provide a number of additional results; for instance, we present a new time model suitable for reasoning about systems with a bounded number of unsynchronized clocks, we investigate connections with spatial reasoning and we present improved algorithms for deciding satisfiability of the tractable point algebras.     

ASADAL/SIM: an incremental multi-level simulation and analysis tool for real-time software specifications

Despite considerable advancement in software engineering methods during the past three decades, requirements engineering of large and complex software systems still remains a difficult and active research problem. One such difficulty lies in developing correct and useful methods for the validation and verification of real-time software specifications. One way of analyzing and validating/verifying software specifications is to mathematically derive or prove desired system properties based on formal specification languages. A full scale system analysis using such formal methods is limited in practice because of the required mathematical skills and computational costs. Formal methods are often used to check only a few very critical real-time properties. Simulation is a complementary approach to testing various system characteristics and validating user requirements. It is especially good for providing a rough picture of final system behavior. This paper presents ASADAL/SIM, a tool for multi-level simulation and analysis of real-time software specifications. It is a subsystem of a larger computer-aided real-time software development environment called ASADAL, and complements ASADAL/PROVER, another subsystem of ASADAL which is a formal verification module.^1. With ASADAL/SIM, simulation primitives can be added to evolving specifications in order to assign stochastic behaviors to external entities and internal processes, and to build a simulation model. ASADAL/SIM can execute the model and, at the same time, demonstrate the final system behavior by graphically showing internal workings of the system; catch undesirable system behaviors with breakpoints; and present various analytical results and system statistics ASADAL/SIM, following ASADAL's philosophies of hierarchical system modeling and early system validation, allows users to simulate ‘evolving’ specifications at different, mixed, and wide levels of detail. In particular, algorithmic details may be specified for low level behavioral blocks, and simulated with abstract entities yet to be refined to such a level. This facilitates the tracking of critical data values at the specification level, and eases the next transformation into code level implementation. With ASADAL/SIM, ASADAL becomes an effective and comprehensive supporting tool for various existing software engineering approaches, particularly top-down refinement and incremental development practices. © 1998 John Wiley & Sons, Ltd.     

Generation of test sequences from formal specifications: GSM 11‐11 standard case study

This paper presents the results of a case study on generating test cases for a fragment of the smart card GSM 11‐11 standard. The generation method is based on an original approach using the B notation and techniques of constraint logic programming with sets. The GSM 11‐11 technical specifications were formalized with the B notation. From this B specification, a system of constraints was derived, equivalent to this formal model. Using a set constraint solver, boundary states were computed and test cases were obtained by traversing the constrained reachability graph of the specifications. The purpose of this project was to evaluate the contribution of this testing environment, called B ‐TESTING ‐TOOLS , in an industrial process on a real life‐size application, by comparing the generated test sequences with the already used and high‐quality manually‐designed tests. This comparison enabled us to validate our approach and showed its effectiveness in the validation process of critical applications: the case study gives a wide coverage (about 85%) of the generated tests compared to the pre‐existing tests and a saving of 30% in test design time. Copyright © 2004 John Wiley & Sons, Ltd.