The task of searching a powerset lattice is part of many problem domains. In Approximate Functional Dependencies (AFDs) mining the algorithm used for searching lattices has been bottom-up breadth first search (BU-BFS). This paper introduces as part of the MoLS framework a method for managing and using inferred information about the status of rules in the lattice. BU-BFS however has limited ability to use inferred information. This paper instead explores the ability of depth first search (DFS) algorithms to use inferred information. The focus on algorithms is motivated by the idea that improved performance from an algorithm is more likely to persist as users make customizations or use different approximation measures. Algorithms are experimentally evaluated and performance is judged based on the portion of the search space for which the approximation measure has been calculated. This presents a machine independent evaluation where differences in performance can be directly attributed to the algorithm.

PIVOT is an important relational operation that allows data in rows to be exchanged for columns. Although most current relational database management systems support PIVOT-type operations, to date a purely formal, algebraic characterization of PIVOT has been lacking. In this paper, we present a characterization in terms of extended relational algebra operators τ (transpose), Π (drop projection), and μ (unique optimal tuple merge). This enables us to (1) draw parallels with PIVOT and existing operators employed in Dynamic Data Mapping Systems (DDMS), (2) formally characterize invertible PIVOT instances, and (3) provide complexity results for PIVOT-type operations. These contributions are an important part of ongoing work on formal models for relational OLAP.

In this article, we develop a relational algebra for metadata integration, Federated Interoperable Relational Algebra (FIRA). FIRA has many desirable properties such as compositionality, closure, a deterministic semantics, a modest complexity, support for nested queries, a subalgebra equivalent to canonical Relational Algebra (RA), and robustness under certain classes of schema evolution. Beyond this, FIRA queries are capable of producing fully dynamic output schemas, where the number of relations and/or the number of columns in relations of the output varies dynamically with the input instance. Among existing query languages for relational metadata integration, only FIRA provides generalized dynamic output schemas, where the values in any (fixed) number of input columns can determine output schemas.Further contributions of this article include development of an extended relational model for metadata integration, the Federated Relational Data Model , which is strictly downward compatible with the relational model. Additionally, we define the notion of Transformational Completeness for relational query languages and postulate FIRA as a canonical transformationally complete language. We also give a declarative, SQL-like query language that is equivalent to FIRA, called Federated Interoperable Structured Query Language (FISQL).While our main contributions are conceptual, the federated model, FISQL/FIRA, and the notion of transformational completeness nevertheless have important applications to data integration and OLAP. In addition to summarizing these applications, we illustrate the use of FIRA to optimize FISQL queries using rule-based transformations that directly parallel their canonical relational counterparts. We conclude the article with an extended discussion of related work as well as an indication of current and future work on FISQL/FIRA.

We present an architecture that enables information visualization activities within a database environment. Our approach presents an abstraction of this transformation process, which we call mapping. The implementation of the mapping process is controlled by the end-user through a Map, which can be used to add order and scale to data.

This paper present details of an integrated database visualization system. The system supports the visualization process from an end-to-end perspective. Included in the system is a mechanism for performing transformations to the data being visualized through the use of database relations. This mapping process provides an abstract mechanism for supporting data to geometry transformations under the control of a user-defined, declarative language. The system supports a wide variety of visualization techniques, including scatterplots, bar charts and surface plots.

Process considerations are a central part of the material for a software engineering course; they are also central to accomplishing full-lifecycle, team-based systems development projects in such a course. This paper discusses the ways in which we have achieved an effective process structure within an academic context of full-year project courses. The key features are a kernel project plan and a process management mechanism. The project plan is a schedule including eight milestones with fixed due dates and quite explicit deliverables. The management is accomplished through an advanced full-year course, whose participants guide the project teams through the process.

No abstract available.

This paper uses the tools of information theory to examine and reason about the information content of the attributes within a relation instance. For two sets of attributes X and Y, an information dependency measure (InD measure) characterizes the uncertainty remaining about the values for the set Y when the values for the set X are known. A variety of arithmetic inequalities (InD inequalities) are shown to hold among InD measures; InD inequalities hold in any relation instance. Numeric constraints (InD constraints) on InD measures, consistent with the InD inequalities, can be applied to relation instances. Remarkably, functional and multivalued dependencies correspond to setting certain constraints to zero, with Armstrong's axioms shown to be consequences of the arithmetic inequalities applied to constraints. As an analog of completeness, for any set of constraints consistent with the inequalities, we may construct a relation instance that approximates these constraints within any positive ε. InD measures suggest many valuable applications in areas such as data mining.

We present a language for querying list-based complex objects. The language is shown to express precisely the polynomial-time generic list-object functions. The iteration mechanism of the language is based on a new approach wherein, in addition to the list over which the iteration is performed, a second list is used to control the number of iteration steps. During the iteration, the intermediate results can be moved to the output list as well as reinserted into the list being iterated over. A simple syntactic constraint allows the growth rate of the intermediate results to be tightly controlled which, in turn, restricts the expressiveness of the language to PTIME.

For many students, the first chance to produce software as part of a team comes with the first work experience outside a university. The difficulties of working with others are compounded by the problems of working in a new environment and for a client with ambiguous and changing goals. Although it is difficult to approximate the "real world" accurately in an academic course, we have implemented two full-year course sequences which apparently give our students some insight into the problems they will face when they leave the university. One course requires the development and implementation of a software product by a team of undergraduates, and the other requires experienced graduate students to act as supervisors for the undergraduate projects. We describe the content and structure of these two sequences, emphasizing how they support and enhance each other. We believe other curricula would benefit from similar courses.

The general problem of formatting microinstructions so as to minimize the width of words in control memory is shown to be computationally difficult. Hence, we should not attempt to solve the general case, but concentrate on heuristics for reasonable subcases.

Many machine languages have two instruction formats, one of which allows addressing of “nearby” operands with “short” (e.g. one word) instructions, while “faraway” operands require “long” format (e.g. two words). Because the distance between an instruction and its operand depends upon the formats of the intervening instructions, the formats of different instructions may be interdependent. An efficient technique is discussed which optimally assigns formats to instructions in a given program and is practical in space as well as time. The more sophisticated problem of arranging operands within programs is discussed. Unfortunately, it is unlikely that an efficient algorithm can guarantee even a good approximation for this problem, since it is shown that r -approximation is NP-complete. Finally, implications of these problems for hardware and software design are considered.

Petri nets have been extensively studied because of their suitabi1ity as models for asynchronous computing. Despite this effort, the mathematical properties of Petri nets are not very well understood. In this paper, we investigate two important special types of Petri nets, the conflict free and the persistent nets, the former being a proper subset of the latter. Our results completely characterize the sets of reachable markings attainable by such nets. Reachability sets of persistent nets are shown to be semilinear. A stronger result is obtained for conflict free nets which results in an exponential time algorithm for deciding boundedness of such nets. The best known upper bound for deciding boundedness of arbitrary nets is Ackerrnann's function. We conclude with a proof that all reachability sets of Petri nets may be realized with a minimal amount of non-persistence.

Computer applications and computer science education for developing nations have received little attention in developed countries, largely because we are naturally interested in first putting our own house in order. This paper is first intended to call attention to the problems of developing nations. It surveys the ways in which developing nations need computing and computer science, and how computer science education can help satisfy these needs. The goals and problems of computer science education are then discussed.

The complexity of decision procedures for the Weak Monadic Second-Order Theories of the Natural Numbers are considered. If only successor is allowed as a primitive, then every alternation of second-order quantifiers causes an exponential increase in the complexity of deciding the validity of a formula. Thus a heirarchy similar in form to Kleene's arithmetic heirarchy may be shown to correspond to the Ritchie functions. On the other hand, if first-order less-than is allowed as a primitive, one existential quantifier suffices for arbitrarily complex (in the Ritchie heirarchy) decision problems. This leads to a normal form, in which every sentence in the theory is equivalent in polynomial time to a sentence with less-than but only one existential second-order quantifier.

It is proven that complexity classes of abstract measures of complexity need not be recursively enumerable, However, the complement of each class is shown to be r.e. The results are extended to complexity classes determined by partial functions, and the properties of these classes are investigated. Properties of effective enumerations of complexity classes are studied. For each measure another measure with the same complexity classes is constructed such that almost every class admits an effective enumeration of efficient devices. Finally complexity classes are shown not to be closed under intersection.

This paper studies possible extensions of the concept of complexity class of recursive functions to partial recursive functions. Many of the well-known results for total complexity classes are shown to have corresponding, though not exactly identical, statements for partial classes. In particular, with two important exceptions, all results on the presentation and decision problems of membership for the two most reasonable definitions of partial classes are the same as for total classes. The exceptions concern presentations of the complements and maximum difficulty for decision problems of the more restricted form of partial classes.

It is proven that complexity classes of abstract measures of complexity need not be recursively enumerable. However, the complement of each class is r.e.