Advertisement

Author Archives

Research and Advances

Progressive acyclic digraphs—a tool for database integrity

A progressive acyclic diagraph (PAD) algorithm accepts are requests and maintains a graph in an acyclic state. When a request creates a cycle, nodes are “detached” until the new arc can be entered acyclically. This process is important in certain areas of database implementation in which there are constraints on the permissible sequences of actions. Two PAD algorithms are presented; one uses a simple path matrix representation and the other uses a list with an “artificial gradient.” Experiments suggest that for large N the second is considerably faster, though both are asymptotically O(NR), where N is the number of nodes and R is the expected number of nodes reachable along paths from any given node.
Research and Advances

Compact list representation: definition, garbage collection, and system implementation

Compact lists are stored sequentially in memory, rather than chained with pointers. Since this is not always convenient, the Swym system permits a list to be chained, compact, or any combination of the two. A description is given of that list representation and the operators implemented (most are similar to those of LISP 1.5). The system garbage collector attempts to make all lists compact; it relocates and rearranges all of list storage using temporary storage. This unique list-compacting garbage collection algorithm is presented in detail. Several classes of the macros used to implement the system are described. Finally, consideration is given to those design factors essential to the success of a plex processing system implementation.

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved