This paper explores using entity-life modeling (ELM) as an effective method for designing concurrent graphical user interfaces in a message processing environment. In ELM, multiple threads of control in the software are modeled on threads of events in the problem environment, and software objects are modeled on objects in the problem. The goal is to identify a minimum number of threads in the problem environment that drive the system while operating on objects. ELM states that threads are primarily those processes that must be rescheduled at particular points in time and those that vie for resources. The intent of this paper is to show that the ELM approach to problem analysis needs to be modified in order to produce optimal designs in a message passing environment. The paper suggests that some reschedulable processes do not need their own threads of control. Instead, the desired effect can be achieved by timers that insert a message into the message queue of a given process at the appropriate time. The paper also proposes a new category of background entities to account for time-consuming calculations that must be carried out concurrently with ordinary message processing.

Although knowledge discovery is increasingly important in databases, discovered knowledge is not always useful to users. It is mainly because the discovered knowledge does not fit user's interests, or it may be redundant or inconsistent with {\it a priori\/} knowledge. Knowledge discovery in databases depends critically on how well a database is characterized and how consistently the existing and discovered knowledge is evolved. This paper describes a novel concept for knowledge discovery and evolution in databases. The key issues of this work include: using a database query to discover new rules; using not only positive examples (answer to a query) but also negative examples to discover new rules; harmonizing existing rules with the new rules. The main contribution of this paper is the development of a new tool for (1) characterizing the exceptions in databases and (2) evolving knowledge as a database evolves.

This paper addresses the problem of semantic query reformulation in the context of object-oriented deductive databases. It extends the declarative object-oriented specifications of F-logic proposed by Kifer and Lausen using the semantic query optimization technique developed by Chakravarthy, Grant, and Minker. In general, query processing in object-oriented databases is expensive when a query incorporates declarative rules, methods and inherited properties. We introduce the technique of semantic query reformulation for F-logic queries which transforms the original query into an equivalent, semantically-rich query that is more efficiently processed. We also discuss the issues of conflict resolution strategies and query evaluation priorities for queries involving the upper bounds of objects in the F-logic ``type'' lattice.

We introduce the concept of rule schema in this paper in order to support constraints in the active object-oriented paradigm. The rule schema provides the meta-knowledge associated with constraints analogous to the way a database schema provides metadata about the database objects. It is used to compile the constraints into clauses which are then ``attached'' to appropriate object attributes. The compiled constraints incorporate the semantics associated with inheritance over generalization hierarchies and references to simple objects which are constituents of complex objects. These clauses are evaluated and enforced whenever an attribute value is retrieved or updated. The update semantics for update propagation of object instances is embedded in the compiled constraints; constraints therefore play a role similar to methods in the model, but are specified explicitly rather than procedurally. They can therefore be managed by the active object-oriented database.

In any environment of multiple information sources it is practically unavoidable that information sources would overlap; that is, describe the same portion of the real world. And when information sources overlap, it is practically unavoidable that information would be inconsistent; that is, describe differently the same portion of the real world. In this report we define a formal framework for resolving extensional inconsistencies that are detected in the process of processing queries against a collection of information sources. This framework establishes basic database concepts, such as schemes, instances, views, queries and integrity constraints, as well as new concepts, such as view equivalence, scheme mappings, multi-databases, multi-database queries and inconsistency. Altogether, it provides the formal foundations necessary for addressing issues of information integration and inconsistency resolution. Our approach to the integration of inconsistent answers is based on information goodness, a measure for estimating the proximity of stored information to the ideal information. We propose to maintain for each information source a goodness base: a set of basic views whose goodness will be useful for inferring the goodness of anticipated queries. When a query is answered inconsistently by individual information sources we propose to (1) estimate the goodness of each answer from the appropriate goodness base, and (2) integrate the individual answers in an answer of the highest goodness. We sketch the architecture of a software agent, called Harmony, that will implement our approach.

We extend the category-partition method, a specification-based method for testing software. Previous work in category-partition has focused on developing structured test specifications that describe software tests. We offer guidance in making the important decisions involved in transforming test specifications to actual test cases. We present a structured approach to making those decisions, including a mechanical procedure for test derivation. With this procedure, we suggest a heuristic for choosing a minimal coverage of the categories identified in the test specifications, suggest parts of the process that can be automated, and offer a solution to the problem of identifying infeasible combinations of test case values. Our method uses formal schema-based functional specifications and is illustrated with an example of a simple file system. We conclude that our approach eases test case creation and leads to effective tests of software. We also note that by basing this procedure on formal specifications, we can identify anomalies in the functional specifications.

We consider communication structures for event ordering algorithms in distributed environments where information flows only in one direction. Example applications are multilevel security and hierarchical databases. Although the most general one-directional communication structure is a partial order, partial orders do not enjoy the property of being consistently-ordered, a formalization of the notion that globally consistent event ordering is ensured. Our main result is that the crown-free property is necessary and sufficient for a communication structure to be consistently-ordered. We discuss the computational complexity of detecting crowns and sketch typical applications.

We consider communication structures for event ordering algorithms in distributed environments where information flows only in one direction. Example applications are multilevel security and hierarchical databases. Although the most general one-directional communication structure is a partial order, partial orders do not enjoy the property of being consistently-ordered, a formalization of the notion that globally consistent event ordering is ensured. Our main result is that the crown-free property is necessary and sufficient for a communication structure to be consistently-ordered. We discuss the computational complexity of detecting crowns and sketch typical applications.

We review three algorithms for concurrency control in secure, multi-level replicated databases. We show by counterexample that the various algorithms, even if suitably modified to correct published problems, still do not guarantee serializability for either general partial orders or general lattices. The counterexamples suggest that the difficulty is a general feature of concurrency control algorithms tailored to the replicated architecture. We make two constructive observations. First, sufficient centralization permits algorithms applicable to general partial orders. Second, the reviewed algorithms are applicable to more restrictive security structures. Specifically, we observe that the intuitively appealing restriction to planar lattices is sufficient.

Data flow and mutation testing are two powerful white box testing techniques for unit-level software testing. Unfortunately, they cannot be completely compared on an analytical basis, for example, mutation is incomparable on an inclusion basis with most data flow criteria. This paper shows that mutation includes the All-defs data flow criterion, but is incomparable with other data flow criteria, and presents results from two empirical comparisons of mutation with the All-uses data flow criterion. For the first comparison, we define a coverage measure that is used for the comparison. The coverage of data flow by mutation is between 99% and 100%, which means that test data that satisfied the mutation criterion also satisfied the data flow criterion in almost all cases. The coverage of mutation by data flow was between 80 and 90%. For the second comparison, we use test data that satisfy the two criteria to detect faults, and compare the criteria on the basis of the faults found. The empirical evidence strongly indicates that while data flow-adequate test sets are close to being mutation-adequate, mutation-adequate test sets are almost invariably data flow-adequate.

Mistix is a simple file system based on the Unix file system. Mistix is used in classroom exercises in graduate software engineering classes at George Mason University. In this document, we supply several different specifications for Mistix. First we give an informal specification. Next, since the informal specification turns out to be difficult to formalize directly, we supply a revised informal specification that matches subsequent formal specifications. We give a model-based specification for Mistix in Z, followed by functional test specifications based on the Category-Partition method. Finally, we give an algebraic specification for Mistix.