Search

A compositional method of constructing data dependency graphs for Ada programs is presented. These graphs are useful in a program development environment for analyzing data dependencies and tracking information flow within a program. Graphs for primitive program statements are combined together to form graphs for larger program units. Composition rules are described for iteration, recursion, exception handling, and tasking, as well as for simpler Ada constructs. The correctness of the construction and the practicality of the technique are discussed. >

We investigate the question of when two entity-relationship diagrams (ERD's) should be considered equivalent, in the sense of representing the same information. This question is very important for a database design process which uses the ERD model, and can be interpreted in various ways. We give three natural and increasingly stricter criteria for developing concepts of equivalence for ERD's. We first give a notion of "domain data compatibility" which ensures that the ERD's in question represent the same universe of data in an aggregate sense. Then we define the set of functional dependencies which are naturally embedded in each ERD, and use it to develop a concept of "data dependency equivalence" which ensures that the ERD's satisfy the same constraints (functional dependencies) among the represented data. Finally, we give our strongest criterion, instance data equivalence, which requires the ERD's to have the same power to represent instances of data. We develop several alternate forms of this third notion, including some giving efficient tableaux tests for its occurrence. Indeed, for each type of equivalence, we give a polynomial-time algorithm to test for it.

The control of concurrent access to shared resources is an important feature of both centralized and distributed operating systems. In conventional systems, exclusive access is the rule while concurrent access is the exception. Dataflow computer systems, along with an applicative style of programming, provide an execution environment in which this philosophy is reversed. In these latter systems, it is necessary to reexamine the manner in which synchronization of access to shared resources is specified and implemented. A basic design for a dataflow resource manager is reviewed, illustrating the clear separation between access mechanism and scheduling policy. The semantics of the access mechanism is based solely on the principle of data dependency. Specifications are presented for a general scheduler to further constrain or order accesses to the resource. Using ``open path expressions'' as a very high-level specification language for synchronization, it is shown how to automatically synthesize a scheduler as a distributed network of communicating modules.

Database design is based on the concept of data dependency, which is the interrelationship between data contained in various sets of attributes. In particular, functional, multivalued and acyclic join, dependencies play an essential role in the design of database schemas. The basic definition of an information metric and how this notion can be used in relational database are discussed in this paper. We use Shannon entropy as an information metric to quantify the information associated with a set of attributes. Thus, we prove that data dependencies can be formulated in terms of entropies. These formulas make the numerical computation and testing of data dependencies feasible. Among the different types of data dependencies, the acyclic join dependency is most important to the design of a relational database schema. The acyclic join dependency, with multivalued dependency as a special case, impose a constraint on the information-preserving decomposition of a relation. It is interesting that this constraint on a relation is similar to Gibbs' condition for separating physical systems in statistical mechanics. They both assert that entropy is preserved during the decomposition process. That is, the entropies of the corresponding set of attributes must satisfy the inclusion–exclusion identity.