2326738
Adaptable, efficient, and modular coordination of distributed extended transactions
The authors describe a method for building a variety of coordination protocols as well as distributed extended transaction primitives. The method is called open coordination protocol (OCP), and is applied to construct many variants of commit-transaction, as well as distributed split-transaction and distributed join-group. OCP adopts a modular decomposition of popular coordination protocols (e.g., two-phase commit) into microprotocols, and then chooses appropriate microprotocols to build new coordination protocols or extended transaction primitives with desired features (e.g., split-transaction with read-only optimization). They use incremental specialization to improve the efficiency of each implemented protocol.
9143242
Update Monitoring: The CQ Project
In rapidly growing open environments such as the Internet, users experience information starvation in the midst of data overload, due to difficulties similar to finding the needle in a haystack. Update monitoring is a promising area of research where we bring the right information to the user at the right time, instead of forcing the user through manual browsing or repeated submission of queries. As an example of update monitoring research, we outline our work in the Continual Queries (CQ) project, including its basic concepts, software architecture, and current implementation status.
12589406
VISTA: Validating and Refining Clusters Via Visualization
Clustering is an important technique for understanding of large multidimensional datasets. Most of clustering research to date has been focused on developing automatic clustering algorithms and cluster validation methods. The automatic algorithms are known to work well in dealing with clusters of regular shapes, for example, compact spherical shapes, but may incur higher error rates when dealing with arbitrarily shaped clusters. Although some efforts have been devoted to addressing the problem of skewed datasets, the problem of handling clusters with irregular shapes is still in its infancy, especially in terms of dimensionality of the datasets and the precision of the clustering results considered. Not surprisingly, the statistical indices works ineffective in validating clusters of irregular shapes, too. In this paper, we address the problem of clustering and validating arbitrarily shaped clusters with a visual framework (VISTA). The main idea of the VISTA approach is to capitalize on the power of visualization and interactive feedbacks to encourage domain experts to participate in the clustering revision and clustering validation process. The VISTA system has two unique features. First, it implements a linear and reliable visualization model to interactively visualize multi-dimensional datasets in a 2D star-coordinate space. Second, it provides a rich set of user-friendly interactive rendering operations, allowing users to validate and refine the cluster structure based on their visual experience as well as their domain knowledge.
33902172
An Object-Centered Approach for Manipulating Hierarchically Complex Objects
We present an object-centered approach for manipulating hierarchically complex objects, which covers an extended object model and an object-centered query algebra. Extensions of the object model are mainly based on a separation of structural and semantic elements in modeling complex objects, including a general distinction between aggregation reference and association reference, an introduction of type inheritance into aggregation hierarchies and a support for combination of aggregation inheritance with subtype inheritance. Based on the extensions, we develop a query algebra as an integral part of the model. Unlike most of existing algebra-based query languages, our object algebra takes complex object collectively as a unit of high level queries and allows complex objects to be accessed at all levels of aggregation hierarchies without having resort to any kind of path expressions. Features of aggregation hierarchies, such as acyclicity and aggregation inheritance, have played important roles in such a development. We have also formally described the output type of each operator in order for dynamic classification of query results in the IsA type/class lattice. Although the design is based on the chosen object-oriented model, other object-oriented databases are possible. We feel that the proposal largely covers the query requirements for complex objects, and meanwhile provides users with an opportunity to remain within the framework of the model of complex objects while querying database. As a consequence, the flexibility and adaptability of the object-oriented model against schema changes 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.
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.
24660543
A note on the lower bounds of signed domination number of a graph
Abstract Let G = (V, E) be a graph. For a function f : V → {−1, 1}, the weight of f is w(f) = Σv ∈ V f(v). For a vertex v in V, we define f[v] = Σu∈N[v] f(u). A signed dominating function of G is a function f : V → {−1, 1} such that f[v] ⩾ 1 for all v ∈ V. The signed domination number γs(G) of G is the minimum weight of a signed dominating function on G. A signed dominating function of a weight γs(G) we call a γs-function of G. In this paper, we study the signed domination problem of general graph, and obtain some lower bounds of the signed domination number of a graph, and show that these lower bounds are sharp, and extend a result in Dunbar et al. (1995).
8242993
Designing Web-Based Systems in Social Context: A Goal and Scenario Based Approach
In order to design a better web-based system, a designer would like to have notations to visualize how design experts’ know-how can be applied according to one’s specific social and technology situation. We propose the combined use of a goal-oriented language GRL and a scenarios-oriented notation UCM for representing design knowledge of web-based systems and information systems in general. Goals are used to depict business objectives, functional and non-functional system requirements. Tasks are used in the exploration of alternative technologies and their operationalizations into system constructs. Actors are used to do role-based analysis on social relationships. Scenarios are used to describe elaborated business processes or workflow. The approach is illustrated with an example of designing a web-based training system.
42350068
Tackling the Infinite State Space of a Multimedia Control Protocol Service Specification
Coloured Petri Nets (CPNs) are used to model the service provided by an International Standard for the control of multimedia communications over telecommunication networks including the Internet, known as the Capability Exchange Signalling (CES) protocol. The state space of the CPN model includes all of the possible sequences of user observable events, known as the service language, which is a useful baseline against which the protocol can be verified. However, the CES service CPN possesses an infinite state space, due to unbounded communication channels. We parameterize the CPN with the channel capacity, propose and prove a recursive formula for its state space and provide an algorithm for its construction. The algorithm generates the state space for capacity l, from the state space for capacity l - 1, providing incremental state space generation rather than generating a new state space for each value of l. The state space is linear in the size of the channel.
35610063
A Specification-Based Approach to Testing Polymorphic Attributes
The object-oriented features, such as aggregation, inheritance and polymorphism, facilitate software reuse and improve software quality. But those features also cause new problems that traditional testing techniques cannot resolve effectively. Existing researches on object-oriented software testing are mainly based on some graph representations and seldom consider the combinational effect of aggregation, inheritance and polymorphism. For some model-based specifications that do not include graph representations, it is difficult to use the graph based testing techniques to derive test cases. This paper provides an approach to deriving test cases for testing the combinational effect of aggregation, inheritance and polymorphism from a model-based class specification. This approach contains two techniques at intra-class and inter-class testing levels and is mechanized using the algorithms presented in this paper. Finally, through the experimental analysis, we present the effectiveness and applicability of our testing approach.
17663309
Impact of network resource constraints on the performance of wireless sensor relay networks
This work studies the impact of the network resource constraints on the performance of wireless sensor multi-hop relay networks. A differential space-time coding and the cooperative relay scheme for cross layer design is introduced in multi-hop wireless sensor networks. To analyze the network performance of such a system, the relay system from source to destination is simplified as a virtual bit pipe line, and a Markov chain model as well as an M/G/1 queueing system are used. The closed form expression for throughput and delay are derived in the infinite buffer case. A truncated Markov chain model and an M/G/1/K queueing system are used to model the finite buffer situation. Moreover, the system drop probability and the go through delay are studied based on the models.