Sparing for redundant disk arrays

One of the main advantages of a redundant disk array architecture is that it provides fault tolerance against disk drive failures. This improvement in reliability can be further enhanced if spare drives are also added to the array since a failed drive can be expeditiously replaced. Furthermore, even though data can be reconstructed from the other drives of a redundant array in the event of a drive failure, performance is degraded substantially in this mode of operation. Clearly it is desirable to get out of this degraded mode of operation as quickly as possible. Again, having spare drives in the array will facilitate that. The purpose of this paper is to study some of the issues related to sparing in a redundant disk array. In particular, we will try to understand the effect on reliability of different sparing schemes. We will also examine the economic trade-offs of having spare drives in a system. Recommended by: M. Kitsuregawa     

Structure and attribute index for approximate graph matching in large graphs

The increasing popularity of graph data in various domains has lead to a renewed interest in developing efficient graph matching techniques, especially for processing large graphs. In this paper, we study the problem of approximate graph matching in a large attributed graph. Given a large attributed graph and a query graph, we compute a subgraph of the large graph that best matches the query graph. We propose a novel structure-aware and attribute-aware index to process approximate graph matching in a large attributed graph. We first construct an index on the similarity of the attributed graph, by partitioning the large search space into smaller subgraphs based on structure similarity and attribute similarity. Then, we construct a connectivity-based index to give a concise representation of inter-partition connections. We use the index to find a set of best matching paths. From these best matching paths, we compute the best matching answer graph using a greedy algorithm. Experimental results on real datasets demonstrate the efficiency of both index construction and query processing. We also show that our approach attains high-quality query answers.     

Integrating reliable memory in databases

Recent results in the Rio project at the University of Michigan show that it is possible to create an area of main memory that is as safe as disk from operating system crashes. This paper explores how to integrate the reliable memory provided by the Rio file cache into a database system. Prior studies have analyzed the performance benefits of reliable memory; we focus instead on how different designs affect reliability. We propose three designs for integrating reliable memory into databases: non-persistent database buffer cache, persistent database buffer cache, and persistent database buffer cache with protection. Non-persistent buffer caches use an I/O interface to reliable memory and require the fewest modifications to existing databases. However, they waste memory capacity and bandwidth due to double buffering. Persistent buffer caches use a memory interface to reliable memory by mapping it into the database address space. This places reliable memory under complete database control and eliminates double buffering, but it may expose the buffer cache to database errors. Our third design reduces this exposure by write protecting the buffer pages. Extensive fault tests show that mapping reliable memory into the database address space does not significantly hurt reliability. This is because wild stores rarely touch dirty, committed pages written by previous transactions. As a result, we believe that databases should use a memory interface to reliable memory. Received January 1, 1998 / Accepted June 20, 1998     

A predicate-driven document filing system

This paper presents a predicate-driven document filing system for organizing and automatically filing documents. A document model consists of two basic elements: frame templates representing document classes, and folders which are repositories of frame instances. The frame templates can be organized to form a document type hierarchy, which helps classify and file documents. Frame instances are grouped into a folder on the basis of user-defined criteria, specified as predicates which determine whether a frame instance belongs to a folder. Folders can naturally organized into a folder organization which represents the user's real world document filing system. The predicate consistency problem is discussed to eliminate two abnormalities from a folder organization: inapplicable edges (filing paths) and redundant folders. An evaluating net (including an association dictionary, an instantiation component and a production system) is then proposed for evaluating whether a frame instance satisfies the predicate of a folder during document filing. And the concept of consistency a rule base is also discussed.This work was supported by the Separately Budgeted Research (SBR) grant (No. 421190) from New Jersey Institute of Technology and the Systems Integration Program grant from AT&T Foundation     

A CASE tool for software architecture design

This paper describes the Software Architect's Assistant, an automated visual tool for the design and construction of Regis distributed programs. Unlike conventional CASE tools and their supported methodologies, the Architect's Assistant supports a compositional approach to program development in which the software architecture plays a central role throughout the software life-cycle—from the early design stage through to system management and evolution.In its implementation, we have addressed some of the limitations of existing CASE tools, particularly in the degree of automated support offered to the human developer. Conscious effort has been made to maximise usability and efficiency, primarily by enhancing the level of automation and flexibility together with careful design of the user interface. Our objective is to provide a tool which automates all mundane clerical tasks, enforces program correctness and consistency and, at the same time, accommodates the individual working styles of its users.Although currently specific to the development of Regis programs, the Architect's Assistant embodies concepts and ideas which are applicable to CASE tools in general.     

A semantical framework for supporting subjective and conditional probabilities in deductive databases

We present a theoretical basis for supporting subjective and conditional probabilities in deductive databases. We design a language that allows a user greater expressive power than classical logic programming. In particular, a user can express the fact thatA is possible (i.e.A has non-zero probability),B is possible, but (A B) as a whole is impossible. A user can also freely specify probability annotations that may contain variables. The focus of this paper is to study the semantics of programs written in such a language in relation to probability theory. Our model theory which is founded on the classical one captures the uncertainty described in a probabilistic program at the level of Herbrand interpretations. Furthermore, we develop a fixpoint theory and a proof procedure for such programs and present soundness and completeness results. Finally we characterize the relationships between probability theory and the fixpoint, model, and proof theory of our programs.     

Adaptive structuring of binary search trees using conditionalrotations

Consider a set A={A₁,A₂ ,. . ., A_n} of records, where each record is identified by a unique key. The records are accessed based on a set of access probabilities S=[s₁,s₂ ,. . ., s_N] and are to be arranged lexicographically using a binary search tree (BST). If S is known a priori, it is well known that an optimal BST may be constructed using A and S. The case when S is not known a priori is considered. A new restructuring heuristic is introduced that requires three extra integer memory locations per record. In this scheme, the restructuring is performed only if it decreases the weighted path length (WPL) of the overall resultant tree. An optimized version of the latter method, which requires only one extra integer field per record has, is presented. Initial simulation results comparing this algorithm with various other static and dynamic schemes indicates that this scheme asymptotically produces trees which are an order of magnitude closer to the optimal one than those produced by many of the other BST schemes reported in the literature     

A note on reverse scheduling with maximum lateness objective

The inverse and reverse counterparts of the single-machine scheduling problem $1||L_{\max }$ are studied in [2], in which the complexity classification is provided for various combinations of adjustable parameters (due dates and processing times) and for five different types of norm: $\ell _{1},\ell _{2},\ell _{\infty },\ell _{H}^{\Sigma } $ , and $\ell _{H}^{\max }$ . It appears that the $O(n^{2})$ -time algorithm for the reverse problem with adjustable due dates contains a flaw. In this note, we present the structural properties of the reverse model, establishing a link with the forward scheduling problem with due dates and deadlines. For the four norms $\ell _{1},\ell _{\infty },\ell _{H}^{\Sigma }$ , and $ \ell _{H}^{\max }$ , the complexity results are derived based on the properties of the corresponding forward problems, while the case of the norm $\ell _{2}$ is treated separately. As a by-product, we resolve an open question on the complexity of problem $1||\sum \alpha _{j}T_{j}^{2}$ .     

Industrial cost modelling and multi-objective optimisation for decision support in production systems development

Recent developments in cost modelling, simulation-based multi-objective optimisation, and post-optimality analysis have enabled the integration of costing data and cost estimation into a new methodology for supporting economically sound decision-making in manufacturing enterprises. Within this methodology, the combination of production engineering and financial data with multi-objective optimisation and post-optimality analysis has been proven to provide the essential information to facilitate knowledge-driven decision-making in real-world production systems development. The focus of this paper is to present the incremental cost modelling technique specifically designed for the integration with discrete-event simulation models and multi-objective optimisation within this methodology. A complete example, using the simulation model and data modified from a previous real-world case study, is provided in this paper to illustrate how the methodology and cost modelling are applied for the optimal investment decision support.     

Subjective operational reliability assessment of maritime transportation system

System reliability assessment is one of the major acts in the operation and maintenance of every industrial and service sector, which also holds true for maritime transportation system. The complexity of the maritime transportation system is a prime obstacle in the evaluation of the operational reliability of the system; mainly due to the fact that statistical data on the important parameters and variables is scarce. This makes the application of fuzzy sets and fuzzy logic a viable option to overcome the data problem with regards to imprecision or vagueness in parameters and variables values. In this paper, the different decisive factors, affecting maritime transportation systems, are modeled in the form of linguistic variables. Techniques such as aggregation, mapping of fuzzy sets using distance measure and fuzzy logic rule base are used to arrive at subjective operational reliability value. The complete procedure is demonstrated with an example.