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.
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.
6609876
MobiEyes: A Distributed Location Monitoring Service Using Moving Location Queries
With the growing popularity and availability of mobile communications, our ability to stay connected while on the move is becoming a reality instead of science fiction as it was just a decade ago. An important research challenge for modern location-based services is the scalable processing of location monitoring requests on a large collection of mobile objects. The centralized architecture, though studied extensively in literature, would create intolerable performance problems as the number of mobile objects grows significantly. This paper presents a distributed architecture and a suite of optimization techniques for scalable processing of continuously moving location queries. Moving location queries can be viewed as standing location tracking requests that continuously monitor the locations of mobile objects of interest and return a subset of mobile objects when certain conditions are met. We describe the design of MobiEyes, a distributed real time location monitoring system in a mobile environment. The main idea behind the MobiEyes' distributed architecture is to promote a careful partition of a real time location monitoring task into an optimal coordination of server-side processing and client-side processing. Such a partition allows evaluating moving location queries with a high degree of precision using a small number of location updates, thus providing highly scalable location monitoring services. A set of optimization techniques are used to limit the amount of computation to be handled by the mobile objects and enhance the overall performance and system utilization of MobiEyes. Important metrics to validate the proposed architecture and optimizations include messaging cost, server load, and amount of computation at individual mobile objects. We evaluate the scalability of the MobiEyes location monitoring approach using a simulation model based on a mobile setup. Our experimental results show that MobiEyes can lead to significant savings in terms of server load and messaging cost when compared to solutions relying on central processing of location information
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.
12929111
Type Safety in the Context of Method Updates
This paper presents a framework for checking and maintaining type safety in the presence of method evolution. A method update often affects all components of the method, including the inter face and the implementation. The type safety problem is addressed as two levels of type consistency. The first level relates to the type checking of methods in the context of the class inheritance hierarchy, and concerns the semantics of the polymorphism of methods. The second level considers the implementation parts of methods by capturing and preserving the semantics of the chain of calling relationships among relevant methods. A graph-based approach is used to achieve this two-level type consistency required at the level of class inheritance hierarchy and the level of method invocation. We demonstrate that the two levels of type consistency checking combined provide a better control of the run-time type error problems.
14344981
Mutation operators for Object-Z specification
As a powerful means of measuring a test set, mutation testing has been applied to program-based testing for a long time. However, with the development of formal specification technique, the formal specifications also play an important role in software testing. For measuring the quality of the specification-based test cases, researchers provide some mutation operators for the logic predicates. With the emergence of the object-oriented formal specifications, these mutation operators cannot completely model the faults arise in an object-oriented specification and from the misunderstanding of the specification. This paper investigates the faults that may occur in the object-oriented specifications, and gives a set of mutation operators for the Object-Z specifications to model these faults. These mutation operators provide an approach to measuring specification-based test cases and validating the Object-Z specifications.
38207892
On the Relations Between Arboricity and Independent Number Or Covering Number
In this paper, the following results are obtained: a(G) + β(G) ⩽ p + 1, ⌈p2⌉ ⩽ a(G)β(G), ⌈p2⌉ ⩽ a′(G) + gb′(G) ⩽ pa′(G) + α′(G) ⩽ 2⌈p2⌉ (δ ⩽ 1) and all bounds are sharp, where p = ¦V(G)¦, ⌈x⌉ denotes the smallest integer greater than or equal to x, a(G) is the vertex arboricity, a′(G) is the edge arboricity, α′(G) is the edge covering number, β(G) is the vertex independent number, β′(G) is the edge independent number, and δ is the minimum degree of G.
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.
2115447
Security and privacy requirements analysis within a social setting
Security issues for software systems ultimately concern relationships among social actors stakeholders, system users, potential attackers - and the software acting on their behalf. We propose a methodological framework for dealing with security and privacy requirements based on i*, an agent-oriented requirements modeling language. The framework supports a set of analysis techniques. In particular, attacker analysis helps identify potential system abusers and their malicious intents. Dependency vulnerability analysis helps detect vulnerabilities in terms of organizational relationships among stakeholders. Countermeasure analysis supports the dynamic decision-making process of defensive system players in addressing vulnerabilities and threats. Finally, access control analysis bridges the gap between security requirement models and security implementation models. The framework is illustrated with an example involving security and privacy concerns in the design of agent-based health information systems. In addition, we discuss model evaluation techniques, including qualitative goal model analysis and property verification techniques based on model checking.
28219085
Reducing Parametric Automata: A Multimedia Protocol Service Case Study
The Capability Exchange Signalling (CES) protocol is a control protocol for multimedia communications developed by the International Telecommunication Union (ITU) [3]. Our goal is to verify this protocol against the set of allowable sequences of service primitives (i.e. user observable events), known as the service language. Thus the first step to verify the CES protocol is to obtain the CES service language. By using automata reduction techniques [2], our approach is to extract the service language from the Occurrence Graph (OG) of the Coloured Petri Net (CPN) model [4] for the protocol’s service definition. The OG of a CPN model is a directed graph comprising all reachable states (nodes) and state changes (edges) of the model.