A novel algorithm based on the Newton projection scheme [1] is proposed to improve the convergence behavior of circuit simulation. The computation experiment shows that the number of iterations to achieve convergence in Newton-Raphson method can be cut by as much as twenty nine-fold, and the convergence behavior of the Newton iteration is made much more robust using this algorithm. Moreover, the implementation of the proposed algorithm in conventional circuit simulators such as SPICE is very easily done. Both the theoretical background and actual implementation of the algorithm are discussed. The experimental circuit and simulation results are also shown.

We describe an effort in applying database technology to the VLSI design process. By mixing software tools, relational database concepts, sophisticated index management, and existing VLSI design tools, we have built a flexible, interactive VLSI design system that provides data independence and technology independence. Design tools are interfaced with a centralized database to form an integrated design environment.

We describe a comprehensive way to organize information about VLSI technologies. This information is represented both in a syntactical structure and in a database format. The objective of the technology database is to exercise centralized control over all tools that use technology information so that the tools can be made immune to changes in technology to the extent possible. The syntactical representation allows for interchange among different companies, similar to what Electronic Design Interchange Format (EDIF) is designed for.

All eqmvalence is estabhshed between network databases and a subclass of relational databases.A database is a set of files together w~th a set of constraints that the fdes must satisfy.The constraints are spectfied by Bachman diagrams m the network model and by data dependencies m the relational model.The subclass of relatmnal databases of interest ~s characterized by the absence of two properties of data dependencies: conflzct and contention It is proved that network databases with loop-free Bachman diagrams are eqmvalent to relational databases which are free of conflicts and contenUons.When its Bachman dmgram has loops, a network database ts equivalent to a collection of relattonal databases in this subclass.Th~s study of equivalence is also related to database design algorithms.Although the network model cannot capture the nouons of conflict and contention, they are the source of several problems which have been observed in the decomposiuon approach to relational database design, notably the split key problem, the nonumqueness problem, and lossy joins It is shown that the decomposition approach can be apphed to conflict-and contention-free relational databases without any of these problems.The results serve as a theorettcal foundatton for database translatton between different models and for designing multimodel database management systems.

Most database design methods for the relational model produce a flat database, that is, a family of relations with no explicit interrelational connections. The user of a flat database is likely to be unaware of certain interrelational semantics. In contrast, the entity-relationship model provides schema graphs as a description of the database, as well as for navigating the database. Nevertheless, the user of an entity-relationship database may still commit semantic errors, such as performing a lossy join. This paper proposes a nonflat, or hierarchical, view of relational databases. Relations are grouped together to form relation hierarchies in which lossless joins are explicitly shown whereas lossy joins are excluded. Relation hierarchies resemble the schema graphs in the entity-relationship model. An approach to the design of relation hierarchies is outlined in the context of data dependencies and relational decomposition. The approach consists of two steps; each is described as an algorithm. Algorithm DEC decomposes a given universal relation according to a given set of data dependencies and produces a set of nondecomposable relation schemes. This algorithm differs from its predecessors in that it produces no redundant relation schemes. Algorithm RH further structures the relation schemes produced by Algorithm DEC into a hierarchical schema. These algorithms can be useful software tools for database designers.

A distributed database management system for a loosely coupled network of minicomputers is described. The system adopts the Entity-Relationship data model due to its semantic richness and its potential for maintaining a disciplined database structure. The following features of the system are presented: data distribution, query language and locking mechanism. Data distribution will be by clusters. Each cluster is based on an Entity-Relationship schema, is complete in semantics and must be stored wholly at a single computer site. The query language of the system is designed specially for the Entity-Relationship model. The language is very convenient in data retrieval. The locking mechanism incorporated into this system allows concurrent access of many readers and one writer. At the same time, it insures maintenance of the strongest form of consistency.

This paper presents a method for increasing concurrency in shared data bases. A data base is taken to be a collection of entities with structure, such as relations. Concurrency is increased in the sense that several readers and a single writer may access a set of entities. At the same time, either serializability or a slightly weaker form of consistency can be seen by all transactions. Each transaction is assumed to obtain all its resources when it starts. The method also allows for convenient recovery from crashes which do not affect the information on secondary storage.

A generalization of Petri nets and vector addition systems, called GPN and MGPN, is introduced in this paper. Termination properties of this generalized formalism are investigated. Four subclasses of GPN’s are considered. We distinguish forward-conflict-free, backward-conflict-free, forward-concurrent-free and backward-concurrent-free GPN’s. We also study the concept of strongly connected, strongly repetitive and conservative GPN’s. The main results obtained are (i) every strongly connected, strongly repetitive and forward- (or backward-) conflict-free GPN must be conservative, and (ii) every strongly connected, conservative and forward- (or backward-) concurrent-free GPN must be strongly repetitive. Since the class of forward-conflict-free GPN’s contains properly the structures of computation graphs of Karp and Miller and marked graphs, some results appearing in these studies can be obtained as corollaries. Specialized versions of our results for the case of Petri nets are also included.

In this paper we describe a general purpose relational data base system from both user's and system's viewpoints. The system is currently being implemented for the microprogrammable computer Interdata 85 at the Department of Computer Science, University of Kansas. The long range goal of this research is to implement a distributed data base system in a computer link where the Interdata 85 is connected to a large computer of different architecture and language capability, the Honeywell 635. Toward this goal, we propose a new physical storage structure called a binary search tree complex or BST complex. Primitives to manipulate BST complexes can be easily implemented for both machines. Queries, data manipulation operations and data definition operations specified by users can be mapped into these BST complex primitives; therefore the translation process can be independent of machine hardware. In this paper, we outline the capability of a user data language UDL-1 and its implementation in terms of BST complexes. A detailed description of all BST complex primitives appears in [LTD].