Jeffrey D. Ullman

TCS Journal 2000 Journal Article

Information integration using logical views

• Jeffrey D. Ullman

A number of ideas concerning information-integration tools can be thought of as constructing answers to queries using views that represent the capabilities of information sources. We review the formal basis of these techniques, which are closely related to containment algorithms for conjunctive queries and/or Datalog programs. Then we compare the approaches taken by AT&T Labs’ “Information Manifold” and the Stanford “Tsimmis” project in these terms.

AAAI Conference 1996 Conference Paper

The Database Approach to Knowledge Representation

• Jeffrey D. Ullman

The database theory community, centered around the PODS (Principles of Database Systems) conference has had a long-term interest in logic as a way to represent "data, " "information," and "knowledge" (take your pick on the term - it boils down to facts or atoms and rules, usually Horn clauses). The approach of this community has been "slow and steady," preferring to build up carefully from simple special cases to more general ideas, always paying attention to how efficiently we can process queries and perform other operations on the facts and rules. A powerful theory has developed, and it is beginning to have some impact on applications, especially information-integration engines.

FOCS Conference 1986 Conference Paper

Parallel Complexity of Logical Query Programs

• Jeffrey D. Ullman
• Allen Van Gelder

We consider the parallel time complexity of logic programs without function symbols, called logical query programs, or Datalog programs. We give a PRAM algorithm for computing the minimum model of a logical query program, and show that for programs with the "polynomial fringe property, " this algorithm runs in logarithmic time. As a result, the "linear" and "piecewise linear" classes of logic programs are in NC. Then we examine several nonlinear classes in which the program has a single recursive rule that is an "elementary chain" We show that certain nonlinear programs are related to GSM mappings of a balanced parentheses language, and that this relationship implies the "polynomial fringe property; " hence such programs are in NC. Finally, we describe an approach for demonstrating that certain logical query programs are log space complete for P, and apply it to both elementary single rule programs and nonelementary programs.

FOCS Conference 1984 Conference Paper

A Communication-Time Tradeoff

• Christos H. Papadimitriou
• Jeffrey D. Ullman

We show a nontrivial tradeoff between the communication c and time t required to compute a collection of values whose dependencies form a grid, i. e. , value (i, j) depends on the values (i-1, j) and (i, j-1). No matter how we share the responsibility for computing the nodes of the n x n grid among processors, the law ct = /spl Omega/(n/sup 3/) must hold. Further, there must be a single path through the grid along which there are d communication steps, where dt = /spl Omega/(n/sup 2/). Depending on the machine organization, either law may be the more significant.

TCS Journal 1984 Journal Article

Connections in acyclic hypergraphs

• David Maier
• Jeffrey D. Ullman

We demonstrate a sense in which the equivalence between blocks (subgraphs without articulation points) and biconnected components (subgraphs in which there are two edge-disjoint paths between any pair of nodes) that holds in ordinary graph theory can be generalized to hypergraphs. The result has an interpretation for relational databases that the universal relations described by acyclic join dependencies are exactly those for which the connections among attributes are defined uniquely. We also exhibit a relationship between the process of Graham reduction (Graham, 1979) of hypergraphs and the process of tableau reduction (Aho, Sagiv and Ullman, 1979) that holds only for acyclic hypergraphs.

STOC Conference 1984 Conference Paper

Correcting Faults in Write-Once Memory

• Danny Dolev
• David Maier 0001
• Harry G. Mairson
• Jeffrey D. Ullman

STOC Conference 1983 Conference Paper

On Notions of Information Transfer in VLSI Circuits

• Alfred V. Aho
• Jeffrey D. Ullman
• Mihalis Yannakakis

Several papers have recently dealt with techniques for proving area-time lower bounds for VLSI computation by “crossing sequence” methods. A number of natural questions are raised by these definitions.

TCS Journal 1982 Journal Article

The theory of functional and template dependencies

• Fereidoon Sadri
• Jeffrey D. Ullman

Template dependencies were introduced by Sadri and Ullman [17] to generalize existing forms of data dependencies. It was hoped that by studying a large and natural class of dependencies, we could solve the inference problem for these dependencies, while that problem was elusive for restricted subsets of the template dependencies, such as embedded multivalued dependencies. At about the same time, other generalizations of known dependency forms were developed, such as the implicational dependencies of Fagin [11] and the algebraic dependencies of Yannakakis and Papadimitriou [20]. Unlike the template dependencies, the latter forms include the functional dependencies as special cases. In this paper we show that no nontrivial functional dependency follows from template dependencies, and we characterize those template dependencies that follow from functional dependencies. We then give a complete set of axioms for reasoning about combinations of functional and template dependencies. As a result, template dependencies augmented by functional dependencies can serve as a substitute for the more general implicational or algebraic dependencies, providing the same ability to represent those dependencies that appear ‘in nature’, while providing a somewhat simpler notation and set of axioms than the more general classes.

STOC Conference 1981 Conference Paper

Optimal Wiring between Rectangles

• Danny Dolev
• Kevin Karplus
• Alan Siegel
• Alex Strong
• Jeffrey D. Ullman

STOC Conference 1981 Conference Paper

Properties of Acyclic Database Schemes

• Catriel Beeri
• Ronald Fagin
• David Maier 0001
• Alberto O. Mendelzon
• Jeffrey D. Ullman
• Mihalis Yannakakis

There is a class of database descriptions, involving one “acyclic” join dependency and a collection of functional dependencies, and nothing else, that appears powerful enough to describe most any real-world body of data in relational database terms. Further, this class has many desirable properties. Some properties make operations like updates and the selection of joins to implement a query over a universal relation especially easy. Other properties of interest were studied by other researchers who described the same class in radically different terms, and found desirable properties in their own contexts. It is the purpose of this paper to define the class formally, to give its important properties and the equivalences with the other classes mentioned, and to explain the importance of each property. This paper is intended to summarize the results that will appear in more detail in [FMU] and [BFMY].

STOC Conference 1980 Conference Paper

A Complete Axiomatization for a Large Class of Dependencies in Relational Databases

• Fereidoon Sadri
• Jeffrey D. Ullman

Relational database theory has discovered complete axiomatizations for functional and multivalued dependencies. However, a database design system that makes use of dependencies declared by the user must deal with some more general kinds of dependencies than these— at least with embedded multivalued dependencies. Yet no axiomatization for embedded multivalued dependencies is known. In this paper, we define a more general class of dependencies, called “template dependencies” and give a complete axiomatization for these. We then discuss the interaction between functional dependencies and template dependencies.

FOCS Conference 1980 Conference Paper

The Compilation of Regular Expressions into Integrated Circuits (Extended Abstract)

• Robert Floyd 0001
• Jeffrey D. Ullman

We consider the design of integrated circuits to implement arbitrary regular expressions. In general, we may use the McNaughton-Yamada algorithm to convert a regular expression of length n into a nondeterministic finite automaton with at most 2n states and 4n transitions. Instead of converting the nondeterministic device to a deterministic one, we propose two ways of implementing the nondeterministic device directly. First, we could produce a PLA (programmable logic array) of approximate dimensions 4n × 4n by representing the states directly by columns, rather than coding the states in binary. This approach, while theoretically suboptimal, makes use of carefully developed technology and, because of the care with which PLA implementation has been done, may be the preferred technique in many real situations. Another approach is to use the hierarchical structure of the automaton produced from the regular expression to guide a hierarchical layout of the circuit. This method produces a circuit 0(√n) on a side and is, to within a constant factor, the best that can be done in general.

STOC Conference 1979 Conference Paper

Deadlock-Free Packet Switching Networks

• Sam Toueg
• Jeffrey D. Ullman

STOC Conference 1979 Conference Paper

Equivalence of Relational Database Schemes

• Catriel Beeri
• Alberto O. Mendelzon
• Yehoshua Sagiv
• Jeffrey D. Ullman

We investigate the question of when two database schemes embody the same information. We argue that this question reduces to the equivalence of the sets of fixed points of the project-join mappings associated with the two database schemes in question. When data dependencies are given, we need only consider those fixed points that satisfy the dependencies. A polynomial algorithm to test the equivalence of database schemes, when there are no dependencies, is given. We also provide an exponential algorithm to handle the case where there are functional and/or multivalued dependencies. Furthermore, we give a polynomial time test to determine whether a project-join mapping preserves a set of functional dependencies, and a polynomial time algorithm for equivalence of database schemes whose project-join mappings do preserve the given set of functional dependencies. Lastly, we introduce the “update sets” approach to database design as an application of these results.

FOCS Conference 1979 Conference Paper

Modeling Communications Protocols by Automata

• Alfred V. Aho
• Jeffrey D. Ullman
• Mihalis Yannakakis

Using a pair of finite-state automata to model the transmitter-receiver protocol in a data communications system, we derive lower bounds on the size of automata needed to achieve reliable communication across an error-phone channel. We also show that, at the cost of increasing the size of the automata, a transmission rate close to the theoretical maximum can be achieved.

TCS Journal 1977 Journal Article

Economy of description by parsers, DPDA's, and PDA's

• Matthew M. Geller
• Harry B. Hunt
• Thomas G. Szymanski
• Jeffrey D. Ullman

It is shown that there is a sequence of languages E 1, E 2, … such that every correct prefix parser (one which detects errors at the earliest possible moment, e. g. , LR or LL parsers) for E n has size 2 cn, yet a deterministic PDA recognizing E n exists and has size O(n 2). There is another easily described sequence of languages N 1, N 2, … for which N has a nondeterministic PDA of size O(n 2), but no deterministic PDA of size less than 2 cn. It is shown moreover, that this latter gap can be made arbitrarily large for different sequences of languages.

FOCS Conference 1977 Conference Paper

The Theory of Joins in Relational Data Bases (Extended Abstract)

• Alfred V. Aho
• Catriel Beeri
• Jeffrey D. Ullman

Answering queries in a relational database often requires that the natural join of two or more relations be computed. However, not all joins are semantically meaningful. This paper gives an efficient algorithm to determine whether the join of several relations is semantically meaningful (lossless) and an efficient algorithm to determine whether a set of relations has a subset with a lossy join. These algorithms assume that all data dependencies are functional. Similar techniques also apply to the case where data dependencies are multivalued.

STOC Conference 1976 Conference Paper

Finding the Depth of a Flow Graph

• Amelia C. Fong
• Jeffrey D. Ullman

FOCS Conference 1975 Conference Paper

Economy of Descriptions by Parsers, DPDA's, and PDA's

• Matthew M. Geller
• Harry B. Hunt III
• Thomas G. Szymanski
• Jeffrey D. Ullman

It is shown that there is a sequence of languages E1, E2, .. . such that every correct prefix parser (one which detects errors at the earliest possible moment, e. g. , LR or LL parsers) for En has size 2cn, yet a deterministic PDA recognizing En exists and has size O(n2). There is another easily described sequence of languages N1, N2, .. . for which Nn has a nondeterministic PDA of size O(n2) but no deterministic PDA of size less than 2cn. It is shown moreover, that this latter exponential gap can be made arbitrarily large for different sequences of languages.

FOCS Conference 1975 Conference Paper

Evaluating Relational Expressions with Dense and Sparse Arguments

• Thomas G. Szymanski
• Jeffrey D. Ullman

We consider expressions whose arguments are relations and whose operators are chosen from among ∪, ο, *, and -1. We further assume that operands may be designated "sparse" or "dense", in a manner to be made formal subsequently. Our aim is to determine whether the evaluation of such an expression is (a) as hard as general transitive closure (b) as hard as transitive closure for sparse graphs. (c) as hard as connected components of an undirected graph.

STOC Conference 1975 Conference Paper

Node Listings for Reducible Flow Graphs

• Alfred V. Aho
• Jeffrey D. Ullman

In [1], Kennedy conjectures that for every n node reducible flow graph, there is a sequence of nodes (with repetitions) of length O(n log n) such that all acyclic paths are subsequences thereof. Such a sequence would, if it could be found easily, enable one to do various kinds of global data flow analyses quickly. We show that for all reducible flow graphs such a sequence does exist, even if the number of edges is much larger than n . If the number of edges is O(n) , the node listing can be found in O(n log n) time.

STOC Conference 1973 Conference Paper

On Finding Lowest Common Ancestors in Trees

• Alfred V. Aho
• John E. Hopcroft
• Jeffrey D. Ullman

STOC Conference 1972 Conference Paper

A Technique for Speeding Up LR(k) Parsers

• Alfred V. Aho
• Jeffrey D. Ullman

STOC Conference 1972 Conference Paper

Flow Graph Reducibility

• Matthew S. Hecht
• Jeffrey D. Ullman

The structure of programs can often be described by a technique called “interval analysis” on their flow graphs. Here, we characterize the set of flow graphs that can be analyzed in this way in terms of two very simple transformation on graphs. We then give a necessary and sufficient condition for analyzability and apply it to “goto-less programs,” showing that they all meet the criterion.

STOC Conference 1972 Conference Paper

Worst-Case Analysis of Memory Allocation Algorithms

• M. R. Garey
• Ronald L. Graham
• Jeffrey D. Ullman

Various memory allocation problems can be modeled by the following abstract problem. Given a list A = (α 1 ,α 2 ,...α n ,) of real numbers in the range (0, 1], place these in a minimum number of “bins” so that no bin holds numbers summing to more than 1. We let A* be the smallest number of bins into which the numbers of list A may be placed. Since a general placement algorithm for attaining A* appears to be impractical, it is important to determine good heuristic methods for assigning numbers of bins. We consider four such simple methods and analyze the worst-case performance of each, closely bounding the maximum of the ratio of the number of bins used by each method applied to list A to the optimal quantity A*.

STOC Conference 1971 Conference Paper

The Care and Feeding of LR(k) Grammars

• Alfred V. Aho
• Jeffrey D. Ullman

We consider methods of modifying LR(k) parsers [1] while preserving the ability of that parsing method to detect errors at the earliest possible point on the input. Two transformations are developed, and the methods of Korenjak [2] and DeRemer [3] are expressed in terms of these transformations. The relation between these two methods is exposed. Proofs are for the most part omitted, but can be found in [4].

STOC Conference 1970 Conference Paper

Transformations on Straight Line Programs-Preliminary Version

• Alfred V. Aho
• Jeffrey D. Ullman

STOC Conference 1969 Conference Paper

Translations on a Context Free Grammar

• Alfred V. Aho
• Jeffrey D. Ullman