10153352
Trigger grouping: a scalable approach to large scale information monitoring
Information change monitoring services are becoming increasingly useful as more and more information is published on the Web. A major research challenge is how to make the service scalable to serve millions of monitoring requests. Such services usually use soft triggers to model users' monitoring requests. We have developed an effective trigger grouping scheme to optimize the trigger processing. The main idea behind this scheme is to reduce repeated computation by grouping monitoring requests of similar structures together. In this paper, we evaluate our approach using both measurements on real systems and simulations. The study shows significant performance gains using the trigger grouping approach. Moreover, the gains are critically dependent on group size and group size distribution (e.g., Zipf). We also discuss the benefit, trade-off, and runtime characteristics of the proposed approach.
599285
Differential evaluation of continual queries
We define continual queries as a useful tool for monitoring of updated information. Continual queries are standing queries that monitor the source data and notify the users whenever new data matches the query. In addition to periodic refresh, continual queries include Epsilon Transaction concepts to allow users to specify query refresh based on the magnitude of updates. To support efficient processing of continual queries, we propose a differential re-evaluation algorithm (DRA), which exploits the structure and information contained in both the query expressions and the database update operations. The DRA design can be seen as a synthesis of previous research on differential files, incremental view maintenance, and active databases.
13182282
InfoFilter: Supporting quality of service for fresh information delivery
With the explosive growth of the Internet and World Wide Web comes a dramatic increase in the number of users that compete for the shared resources of distributed system environments. Most implementations of application servers and distributed search software do not distinguish among requests to different web pages. This has the implication that the behavior of application servers is quite unpredictable. Applications that require timely delivery of fresh information consequently suffer the most in such competitive environments. This paper presents a model of quality of service (QoS) and the design of a QoS-enabled information delivery system that implements such a QoS model. The goal of this development is two-fold. On one hand, we want to enable users or applications to specify the desired quality of service requirements for their requests so that application-aware QoS adaptation is supported throughout the Web query and search processing. On the other hand, we want to enable an application server to customize how it should respond to external requests by setting priorities among query requests and allocating server resources using adaptive QoS control mechanisms. We introduce the Infopipe approach as the systems support architecture and underlying technology for building a QoS-enabled distributed system for fresh information delivery.
17104606
Distributed Query Scheduling Service: An Architecture and Its Implementation
We present the systematic design and development of a distributed query scheduling service (DQS) in the context of DIOM, a distributed and interoperable query mediation system.26 DQS consists of an extensible architecture for distributed query processing, a three-phase optimization algorithm for generating efficient query execution schedules, and a prototype implementation. Functionally, two important execution models of distributed queries, namely moving query to data or moving data to query, are supported and combined into a unified framework, allowing the data sources with limited search and filtering capabilities to be incorporated through wrappers into the distributed query scheduling process. Algorithmically, conventional optimization factors (such as join order) are considered separately from and refined by distributed system factors (such as data distribution, execution location, heterogeneous host capabilities), allowing for stepwise refinement through three optimization phases: Compilation, parallelization, site selection and execution. A subset of DQS algorithms has been implemented in Java to demonstrate the practicality of the architecture and the usefulness of the distributed query scheduling algorithm in optimizing execution schedules for inter-site queries.
13069643
The Role of Polymorphic Reuse Mechanisms in Schema Evolution in an Object-Oriented Database
A seamless approach to the incremental design and reuse of object oriented methods and query specifications is presented. We argue for avoiding or minimizing the effort required for manually reprogramming methods and queries due to schema modifications, and demonstrate how the role of polymorphic reuse mechanisms is exploited for enhancing the adaptiveness of database programs against schema evolution in an object oriented database. The salient features of our approach are the use of propagation patterns and a mechanism for propagation pattern refinement. Propagation patterns are employed as an interesting specification formalism for modeling operational requirements. They encourage the reuse of operational specifications against the structural modification of an object oriented schema. Propagation pattern refinement is suited for the specification of reusable operational modules. It promotes the reusability of propagation patterns toward the operational requirement changes. This approach has a formal basis and emphasizes structural derivation of specifications. The main innovations are in raising the level of abstraction for behavioral schema design, and for making possible the derivation of operational semantics from structural specifications. As a result, both the modularity and reusability of object oriented schemas are increased.
3582970
Building a Semantic Web System for Scientific Applications: An Engineering Approach
This paper presents an engineering experience for building a Semantic Web compliant system for a scientific application – agricultural zoning. First, we define the concept of ontological cover and a set of relationships between such covers. These definitions, based on domain ontologies, can be used, for example, to support the discovery of services on the Web. Second, we propose a semantic acyclic restriction on ontologies which enables the efficient comparison of ontological covers. Third, we present different engineering solutions to build ontology views satisfying the acyclic restriction in a prototype. Our experimental results unveil some limitations of the current Semantic Web technology to handle large data volumes, and show that the combination of such technology with traditional data management techniques is an effective way to achieve highly functional and scalable solutions.
14735447
Representing asymmetric decision problems using coarse valuations
A valuation-based system approach to knowledge representation has shown its advantages in improving computational efficiency and in allowing many decision models including belief networks. This study applies the Dempster-Shafer theory of belief functions and extends its framework to allow coarse valuations, which admit incomplete specification of probabilities and utilities and, therefore, are more flexible in representing asymmetric decision problems. It presents an algorithm for making inferences and decisions in systems using coarse valuations. It shows that a coarse valuation-based system provides a most natural and compact representation of decision problems.
464743
Specifying and analyzing early requirements in Tropos
We present a framework that supports the formal verification of early requirements specifications. The framework is based on Formal Tropos, a specification language that adopts primitive concepts for modeling early requirements (such as actor, goal, and strategic dependency), along with a rich temporal specification language. We show how existing formal analysis techniques, and in particular model checking, can be adapted for the automatic verification of Formal Tropos specifications. These techniques have been implemented in a tool, called the T-Tool, that maps Formal Tropos specifications into a language that can be handled by the NuSMV model checker. Finally, we evaluate our methodology on a course-exam management case study. Our experiments show that formal analysis reveals gaps and inconsistencies in early requirements specifications that are by no means trivial to discover without the help of formal analysis tools.
38352937
Z User Studio: An integrated support tool for Z specifications
This paper introduces an integrated Z support tool, Z User Studio (ZUS), which was developed by the Formal Methods Research Group of Shanghai University. ZUS is an interactive, single-user tool, running under MS-Windows and NT It supports the production of well-formed Z specifications by providing facilities for building, editing, checking and viewing Z specification documents. It displays the Z constructs and symbols, as they would appear in most popular book on Z ZUS has two modes for editing specifications, text-based editor and graphical editor. The graphical editor provides a hierarchical structure directory for every current Z specification. ZUS implements a computer aided test cases generator (TCG).
34284992
An Algorithmic Approach for Sensitivity Analysis of Perturbed Quasi-Birth-and-Death Processes
In this paper, we present an algorithmic approach for sensitivity analysis of stationary and transient performance measures of a perturbed continuous-time level-dependent quasi-birth-and-death (QBD) process with infinitely-many levels. By developing a new LU-type RG-factorization using the censoring technique, we obtain the maximal negative inverse of the infinitesimal generator of the QBD process. The derivatives of the stationary performance measures of the QBD process can then be expressed and computed in terms of the maximal negative inverse, overcoming the computational difficulty arising from the use of group inverses of infinite size in the current literature (see Cao and Chen [11]). We also use a stochastic integral functional to study the transient performance measure of the QBD process and show how to use the algorithmic approach for its sensitivity analysis. As an example, a perturbed MAP/PH/1 queue is also analyzed.
24019518
Obtaining the service language for H.245's multimedia capability exchange signalling protocol: the final step
The capability exchange signalling (CES) protocol is a subprotocol of ITU-T recommendation H.245, "control protocol for multimedia communication". We are interested in verifying this protocol, including verification of its general properties such as absence of deadlocks and livelocks, and verification of the protocol against its service. In previous work, we have analysed the general properties of the CES protocol. In order to verify the protocol against its service, we need to generate the CES service language, which defines all the possible sequences of user observable events. We firstly create the CES service CPN model and then extract the language from the occurrence graph (OG) of the model. In the case of the CES service, this is challenging because we wish to have a general result for arbitrary capacity of the network over which the CES protocol operates. To tackle this problem we introduced into the CPN model a parameter, l, representing the capacity of the communication channel. We derived a recursive formula for the parameterised OG in terms of l. We treat this OG as a finite state automaton (FSA) by nominating acceptance states and apply FSA reduction algorithms to obtain a deterministic FSA that represents the CES service language. We have discovered a recursive formula in l for the CES service language. This paper introduces the CES service via its CPN model as necessary background and presents the final step of the proof of this finding.