Cloud data lakes emerge as an inexpensive solution for storing very large amounts of data. The main idea is the separation of compute and storage layers. Thus, cheap cloud storage is used for storing the data, while compute engines are used for running analytics on this data in “on-demand” mode. However, to perform any computation on the data in this architecture, the data should be moved from the storage layer to the compute layer over the network for each calculation. Obviously, that hurts calculation performance and requires huge network bandwidth. In this paper, we study different approaches to improve query performance in a data lake architecture. We define an optimization problem that can provably speed up data lake queries. We prove that the problem is NP-hard and suggest heuristic approaches. Then, we demonstrate through the experiments that our approach is feasible and efficient (up to ×30 query execution time improvement based on the TPC-H benchmark).

In recent years, an increasing amount of data is collected in different and often, not cooperative, databases. The problem of privacy-preserving, distributed calculations over separate databases and, a relative to it, the issue of private data release was intensively investigated. However, despite a considerable progress, computational complexity and consequently, the performance of the computations, due to an increasing size of data, remains a limiting factor in real-world deployments. Especially in the case of privacy-preserving computations. In this paper, we suggest sampling as a method of improving computational performance. Sampling was a topic of extensive research in the past that recently received a boost of interest. We provide a sampling method targeted at separate, non-collaborating, vertically partitioned datasets. The method is exemplified and tested on an approximation of intersection set both with and without a privacy-preserving mechanism. An analysis of the bound on the error as a function of the sample size is discussed and a heuristic algorithm is suggested to further improve the performance. The algorithms were implemented and experimental results confirm the validity of the approach.

One can hear "Data Science" defined as a synonym for machine learning or as a branch of Statistics. I shall argue that it is far more than that; it is the natural evolution of the technology of very large-scale data management to solve problems in scientific and commercial fields. To support my argument, I shall give a brief introduction to two algorithms that are important in data science but that are neither machine learning nor statistics: locality-sensitive hashing and counting distinct elements.

Despite extensive research on cryptography, secure and efficient query processing over outsourced data remains an open challenge. This poster continues along the emerging trend in secure data processing that recognizes that the entire dataset may not be sensitive, and hence, non-sensitivity of data can be exploited to overcome some of the limitations of existing encryption-based approaches. In particular, this poster outlines a new secure keyword search approach, called query keyword binning (QB) that allows non-sensitive parts of the data to be outsourced in clear-text while guaranteeing that no information is leaked by joint processing of non-sensitive data (in clear-text) and sensitive data (in encrypted form). QB improves the performance of and strengthens the security of the underlying cryptographic technique by preventing size, frequency-count, and workload-skew attacks.

Despite extensive research on cryptography, secure and efficient query processing over outsourced data remains an open challenge. This paper continues along the emerging trend in secure data processing that recognizes that the entire dataset may not be sensitive, and hence, non-sensitivity of data can be exploited to overcome limitations of existing encryption-based approaches. We propose a new secure approach, entitled query binning (QB) that allows non-sensitive parts of the data to be outsourced in clear-text while guaranteeing that no information is leaked by the joint processing of non-sensitive data (in clear-text) and sensitive data (in encrypted form). QB maps a query to a set of queries over the sensitive and non-sensitive data in a way that no leakage will occur due to the joint processing over sensitive and non-sensitive data. Interestingly, in addition to improve performance, we show that QB actually strengthens the security of the underlying cryptographic technique by preventing size, frequency-count, and workload-skew attacks.

We consider the problem of computing the data-cube marginals of a fixed order k (i.e., all marginals that aggregate over k dimensions), using a single round of MapReduce. The focus is on the relationship between the reducer size (number of inputs allowed at a single reducer) and the replication rate (number of reducers to which an input is sent). We show that the replication rate is minimized when the reducers receive all the inputs necessary to compute one marginal of higher order. That observation lets us view the problem as one of covering sets of k dimensions with sets of a larger size m, a problem that has been studied under the name "covering numbers." We offer a number of constructions that, for different values of k and m meet or come close to yielding the minimum possible replication rate for a given reducer size.

In recent years, an increasing amount of data is collected in different and often, not cooperative, databases. The problem of privacy-preserving, distributed calculations over separate databases and, a relative to it, the issue of private data release were intensively investigated. However, despite a considerable progress, computational complexity, due to an increasing size of data, remains a limiting factor in real-world deployments, especially in case of privacy-preserving computations. In this paper, we suggest sampling as a method of improving computational performance. Sampling was a topic of extensive research that recently received a boost of interest. We provide a sampling method targeted at separate, non-collaborating, vertically partitioned datasets. The method is exemplified and tested on approximation of intersection set both without and with privacy-preserving mechanism. An analysis of the bound on error as a function of the sample size is discussed and heuristic algorithm is suggested to further improve the performance. The algorithms were implemented and experimental results confirm the validity of the approach.

In the first wave of data science education programs, data engineering topics (systems, scalable algorithms, data management, integration) tended to be de-emphasized in favor of machine learning and statistical modeling. The anecdotal evidence suggests this was a mistake: data scientists report spending most of their time grappling with data far upstream of modeling activities. A second wave of data science education is emerging, one with increased emphasis on practical issues in ethics, legal compliance, scientific reproducibility, data quality, and algorithmic bias. The data engineering community has a second chance to influence these programs beyond just providing a set of tools. In this panel, we'll discuss the role of data engineering in data science education programs, and how best to capitalize on emerging opportunities in this space.

Controversially, more data is not necessary better than less data. The explosion of the data lead to a number of interesting practical and theoretical problems. Among those problems are the need to filter, process, verify, index, distribute, protect and make redundant copies of the data. This data “massaging” usually take a lot of time and processing power. However, the quantity of the collected data does not necessary mean quality, as a lot of data is repetitive or does not contain any new information. Nevertheless, it still has to be processed, filtered, consumes high communication volume, has to be protected from breaches and from storage failures. In this position paper we propose to perform data reduction techniques on the collected (big) data prior to gathering of the data in a single location. In many cases (exemplified by two use-cases), especially in Internet-of-Things (IoT), those techniques might save tremendous amounts of power, processing time and network traffic.

This panel critically examines the state of data: how its growth and ubiquity have confronted the computer science and particularly the database community, with new challenges. These challenges require practitioners and teachers to learn new skills and engage with other disciplines in ways they had not done before. Panelists will examine the impact of the 'bigness' of data, and its importance for an ever-increasing array of applications, as well as the implications for traditional ideas of privacy and person-hood. By bringing together data specialists with those trained in social and human sciences, this panel aims to initiate discussion about the new social role the computer scientist and the database community have begun to play.

We describe Shasta, a middleware system built at Google to support interactive reporting in complex user-facing applications related to Google's Internet advertising business. Shasta targets applications with challenging requirements: First, user query latencies must be low. Second, underlying transactional data stores have complex "read-unfriendly" schemas, placing significant transformation logic between stored data and the read-only views that Shasta exposes to its clients. This transformation logic must be expressed in a way that scales to large and agile engineering teams. Finally, Shasta targets applications with strong data freshness requirements, making it challenging to precompute query results using common techniques such as ETL pipelines or materialized views. Instead, online queries must go all the way from primary storage to user-facing views, resulting in complex queries joining 50 or more tables.

A MapReduce algorithm can be described by a mapping schema , which assigns inputs to a set of reducers, such that for each required output there exists a reducer that receives all the inputs participating in the computation of this output. Reducers have a capacity that limits the sets of inputs they can be assigned. However, individual inputs may vary in terms of size. We consider, for the first time, mapping schemas where input sizes are part of the considerations and restrictions. One of the significant parameters to optimize in any MapReduce job is communication cost between the map and reduce phases. The communication cost can be optimized by minimizing the number of copies of inputs sent to the reducers. The communication cost is closely related to the number of reducers of constrained capacity that are used to accommodate appropriately the inputs, so that the requirement of how the inputs must meet in a reducer is satisfied. In this work, we consider a family of problems where it is required that each input meets with each other input in at least one reducer. We also consider a slightly different family of problems in which each input of a list, X , is required to meet each input of another list, Y , in at least one reducer. We prove that finding an optimal mapping schema for these families of problems is NP-hard, and present a bin-packing-based approximation algorithm for finding a near optimal mapping schema.

In Dremel, data is stored as nested relations. The schema for a relation is a tree, all of whose nodes are attributes, and whose leaf attributes hold values. We explore filter and aggregate queries that are given in the Dremel dialect of SQL. Complications arise because of repeated attributes, i.e., attributes that are allowed to have more than one value. We focus on the common class of Dremel queries that are processed on column-stored data in a way that results in query processing time that is linear on the size of the relevant data, i.e., data in the columns that participate in the query. We formally define the data model, the query language and the algorithms for query processing in column-stored data. The concepts of repetition context and semi-flattening are introduced here and play a central role in understanding this class of queries and their algorithms.

The theme of this paper is how to find all instances of a given “sample” graph in a larger “data graph,” using a single round of map-reduce. For the simplest sample graph, the triangle, we improve upon the best known such algorithm. We then examine the general case, considering both the communication cost between mappers and reducers and the total computation cost at the reducers. To minimize communication cost, we exploit the techniques of [1] for computing multiway joins (evaluating conjunctive queries) in a single map-reduce round. Several methods are shown for translating sample graphs into a union of conjunctive queries with as few queries as possible. We also address the matter of optimizing computation cost. Many serial algorithms are shown to be “convertible,” in the sense that it is possible to partition the data graph, explore each partition in a separate reducer, and have the total computation cost at the reducers be of the same order as the computation cost of the serial algorithm.

The all-pairs problem is an input-output relationship where each output corresponds to a pair of inputs, and each pair of inputs has a corresponding output. It models similarity joins where no simplification of the search for similar pairs, e.g., locality-sensitive hashing, is possible, and each input must be compared with every other input to determine those pairs that are "similar." When implemented by a MapReduce algorithm, there was a gap, a factor of 2, between the lower bound on necessary communication and the communication required by the best known algorithm. In this brief paper we show that the lower bound can essentially be met.

Recently, a great deal of interest for Big Data has risen, mainly driven from a widespread number of research problems strongly related to real-life applications and systems, such as representing, modeling, processing, querying and mining massive, distributed, large-scale repositories (mostly being of unstructured nature). Inspired by this main trend, in this paper we discuss three important aspects of Big Data research, namely OLAP over Big Data, Big Data Posting, and Privacy of Big Data. We also depict future research directions, hence implicitly defining a research agenda aiming at leading future challenges in this research field.

In this paper we study the tradeoff between parallelism and communication cost in a map-reduce computation. For any problem that is not "embarrassingly parallel," the finer we partition the work of the reducers so that more parallelism can be extracted, the greater will be the total communication between mappers and reducers. We introduce a model of problems that can be solved in a single round of map-reduce computation. This model enables a generic recipe for discovering lower bounds on communication cost as a function of the maximum number of inputs that can be assigned to one reducer. We use the model to analyze the tradeoff for three problems: finding pairs of strings at Hamming distance d , finding triangles and other patterns in a larger graph, and matrix multiplication. For finding strings of Hamming distance 1, we have upper and lower bounds that match exactly. For triangles and many other graphs, we have upper and lower bounds that are the same to within a constant factor. For the problem of matrix multiplication, we have matching upper and lower bounds for one-round map-reduce algorithms. We are also able to explore two-round map-reduce algorithms for matrix multiplication and show that these never have more communication, for a given reducer size, than the best one-round algorithm, and often have significantly less.

As MapReduce/Hadoop grows in importance, we find more exotic applications being written this way. Not every program written for this platform performs as well as we might wish. There are several reasons why a MapReduce program can underperform expectations. One is the need to balance the communication cost of transporting data from the mappers to the reducers against the computation done at the mappers and reducers themselves. A second important issue is selecting the number of rounds of MapReduce. A third issue is that of skew. If wall-clock time is important, then using many different reduce-keys and many compute nodes may minimize the time to finish the job. Yet if the data is uncooperative, and no provision is made to distribute the data evenly, much of the work is done by a single node.

Implementing recursive algorithms on computing clusters presents a number of new challenges. In particular, we consider the endgame problem: later rounds of a recursion often transfer only small amounts of data, causing high overhead for interprocessor communication. One way to deal with the endgame problem is to use an algorithm that reduces the number of rounds of the recursion. Especially, in an application like transitive closure ("TC") there are several recursive-doubling algorithms that use a logarithmic, rather than linear, number of rounds. Unfortunately, recursive-doubling algorithms can deduce many more facts than the linear TC algorithms, which could negate the cost savings from the elimination of the overhead due to the proliferation of small files. We are thus led to consider TC algorithms that, like the linear algorithms, have the unique decomposition property that assures paths are discovered only once. We find that many such algorithms exist, and we show that they are incomparable, in that any of them could prove best on some data --- even lower in cost than the linear algorithms in some cases. The recursive-doubling approach to TC extends to other recursions as well. However, it is not acceptable to reduce the number of rounds at the expense of a major increase in the number of facts that are deduced. In this paper, we prove it is possible to implement any Datalog program of right-linear chain rules with a logarithmic number of rounds and no order-of-magnitude increase in the number of facts deduced. On the other hand, there are linear recursions for which the two goals of reducing the number of rounds and maintaining the total number of deduced facts cannot be met simultaneously. We show that the reachability problem cannot be solved in logarithmic rounds without using a binary predicate, thus squaring the number of potential facts to be deduced. We also show that the samegeneration recursion cannot be solved in logarithmic rounds without using a predicate of arity three.

Fuzzy/similarity joins have been widely studied in the research community and extensively used in real-world applications. This paper proposes and evaluates several algorithms for finding all pairs of elements from an input set that meet a similarity threshold. The computation model is a single MapReduce job. Because we allow only one MapReduce round, the Reduce function must be designed so a given output pair is produced by only one task, for many algorithms, satisfying this condition is one of the biggest challenges. We break the cost of an algorithm into three components: the execution cost of the mappers, the execution cost of the reducers, and the communication cost from the mappers to reducers. The algorithms are presented first in terms of Hamming distance, but extensions to edit distance and Jaccard distance are shown as well. We find that there are many different approaches to the similarity-join problem using MapReduce, and none dominates the others when both communication and reducer costs are considered. Our cost analyses enable applications to pick the optimal algorithm based on their communication, memory, and cluster requirements.

In this paper, we design and analyze parallel algorithms for skyline queries. The skyline of a multidimensional set consists of the points for which no other point exists that is at least as good along every dimension. As a framework for parallel computation, we use both the MP model proposed in (Koutris and Suciu, PODS 2011), which requires that the data is perfectly load-balanced, and a variation of the model in (Afrati and Ullman, EDBT 2010), the GMP model, which demands weaker load balancing constraints. In addition to load balancing, we want to minimize the number of blocking steps, where all processors must wait and synchronize. We propose a 2-step algorithm in the MP model for any dimension of the dataset, as well a 1-step algorithm for the case of 2 and 3 dimensions. Moreover, we present a 1-step algorithm in the GMP model for any number of dimensions.

We survey the recent wave of extensions to the popular map-reduce systems, including those that have begun to address the implementation of recursive queries using the same computing environment as map-reduce. A central problem is that recursive tasks cannot deliver their output only at the end, which makes recovery from failures much more complicated than in map-reduce and its nonrecursive extensions. We propose several algorithmic ideas for efficient implementation of recursions in the map-reduce environment and discuss several alternatives for supporting recovery from failures without restarting the entire job.

Implementations of map-reduce are being used to perform many operations on very large data. We examine strategies for joining several relations in the map-reduce environment. Our new approach begins by identifying the “map-key,” the set of attributes that identify the Reduce process to which a Map process must send a particular tuple. Each attribute of the map-key gets a “share,” which is the number of buckets into which its values are hashed, to form a component of the identifier of a Reduce process. Relations have their tuples replicated in limited fashion, the degree of replication depending on the shares for those map-key attributes that are missing from their schema. We study the problem of optimizing the shares, given a fixed number of Reduce processes. An algorithm for detecting and fixing problems where a variable is mistakenly included in the map-key is given. Then, we consider two important special cases: chain joins and star joins. In each case, we are able to determine the map-key and determine the shares that yield the least replication. While the method we propose is not always superior to the conventional way of using map-reduce to implement joins, there are some important cases involving large-scale data where our method wins, including: 1) analytic queries in which a very large fact table is joined with smaller dimension tables, and 2) queries involving paths through graphs with high out-degree, such as the Web or a social network.

We consider the problem of recommending the best set of k items when there is an inherent ordering between items, expressed as a set of prerequisites (e.g., the movie 'Godfather I' is a prerequisite of 'Godfather II'). Since this general problem is computationally intractable, we develop 3 approximation algorithms to solve this problem for various prerequisite structures (e.g., chain graphs, AND graphs, AND-OR graphs). We derive worst-case bounds for these algorithms for these structures, and experimentally evaluate these algorithms on synthetic data. We also develop an algorithm to combine solutions in order to generate even better solutions, and compare the performance of this algorithm with the other three.

Implementations of map-reduce are being used to perform many operations on very large data. We examine strategies for joining several relations in the map-reduce environment. Our new approach begins by identifying the "map-key," the set of attributes that identify the Reduce process to which a Map process must send a particular tuple. Each attribute of the map-key gets a "share," which is the number of buckets into which its values are hashed, to form a component of the identifier of a Reduce process. Relations have their tuples replicated in limited fashion, the degree of replication depending on the shares for those map-key attributes that are missing from their schema. We study the problem of optimizing the shares, given a fixed number of Reduce processes. An algorithm for detecting and fixing problems where an attribute is "mistakenly" included in the map-key is given. Then, we consider two important special cases: chain joins and star joins. In each case we are able to determine the map-key and determine the shares that yield the least replication. While the method we propose is not always superior to the conventional way of using map-reduce to implement joins, there are some important cases involving large-scale data where our method wins, including: (1) analytic queries in which a very large fact table is joined with smaller dimension tables, and (2) queries involving paths through graphs with high out-degree, such as the Web or a social network.

There has been considerable past work studying data integration and uncertain data in isolation. We develop the foundations for local-as-view (LAV) data integration when the sources being integrated are uncertain. We motivate two distinct settings for uncertain-data integration. We then define containment of uncertain databases in these settings, which allows us to express uncertain sources as views over a virtual mediated uncertain database. Next, we define consistency of a set of uncertain sources and show intractability of consistency-checking. We identify an interesting special case for which consistency-checking is polynomial. Finally, the notion of certain answers from traditional LAV data integration does not generalize to the uncertain setting, so we define a corresponding notion of correct answers .

Summary form only given, as follows. As database system research evolves, there are several enduring themes. One, of course, is how we deal with the largest possible amounts of data. A less obvious theme is optimization - it is an essential ingredient of all modern forms of database system. Because we deal with large volumes of data, we are often forced to process that data in regular ways. But when operations are uniform, there is an opportunity for the use of very-high-level languages, of which SQL is the primary example. However, to make a very-high-level language effective, we need to optimize it well, that is, produce effective query plans from all sorts of queries. In this talk, we shall review the principal directions in which modern database research is going, and in each case talk a bit about the optimization problems. Stream management systems are one very important new area. Another is peer-to-peer database systems. Integration of heterogeneous information, especially in virtual databases, is also a major challenge. XML, XQUERY, and semistructured data in general form yet another research opportunity.

No abstract available.

The education industry has a very poor record of productivity gains. In this brief article, I outline some of the ways the teaching of a college course in database systems could be made more efficient, and staff time used more productively. These ideas carry over to other programming-oriented courses, and many of them apply to any academic subject whatsoever. After proposing a number of things that could be done, I concentrate here on a system under development, called OTC (On-line Testing Center), and on its methodology of "root questions." These questions encourage students to do homework of the long-answer type, yet we can have their work checked and graded automatically by a simple multiple-choice-question grader. OTC also offers some improvement in the way we handle SQL homework, and could be used with other languages as well.

Several commercial applications, such as online comparison shopping and process automation, require integrating information that is scattered across multiple websites or XML documents. Much research has been devoted to this problem, resulting in several research prototypes and commercial implementations. Such systems rely on wrappers that provide relational or other structured interfaces to websites. Traditionally, wrappers have been constructed by hand on a per-website basis, constraining the scalability of the system.

We study the problem or generating efficient, equivalent rewritings using views to compute the answer to a query. We take the closed-world assumption, in which views are materialized from base relations, rather than views describing sources in terms of abstract predicates, as is common when the open-world assumption is used. In the closed-world model, there can be an infinite number of different rewritings that compute the same answer, yet have quite different performance. Query optimizers take a logical plan (a rewriting of the query) as an input, and generate efficient physical plans to compute the answer. Thus our goal is to generate a small subset of the possible logical plans without missing an optimal physical plan.

Association-rule mining has heretofore relied on the condition of high support to do its work efficiently. In particular, the well-known a priori algorithm is only effective when the only rules of interest are relationships that occur very frequently. However, there are a number of applications, such as data mining, identification of similar Web documents, clustering, and collaborative filtering, where the rules of interest have comparatively few instances in the data. In these cases, we must look for highly correlated items, or possibly even causal relationships between infrequent items. We develop a family of algorithms for solving this problem, employing a combination of random sampling and hashing techniques. We provide analysis of the algorithms developed and conduct experiments on real and synthetic data to obtain a comparative performance analysis.

Association rule mining has heretofore relied on the condition of high support to do its work efficiently. In particular, the well-known a-priori algorithm is only effective when the only rules of interest are relationships that occur very frequently. However, there are a number of applications, such as data mining, identification of similar Web documents, clustering and collaborative filtering, where the rules of interest have comparatively few instances in the data. In these cases, we must look for highly correlated items, or possibly even causal relationships between infrequent items. We develop a family of algorithms for solving this problem, employing a combination of random sampling and hashing techniques. We provide an analysis of the algorithms developed and conduct experiments on real and synthetic data to obtain a comparative performance analysis.

Dynamic miss-counting (DMC) algorithms are proposed which find all implication and similarity rules with confidence pruning but without support pruning. To handle data sets with a large number of columns, we propose dynamic pruning techniques that can be applied during data scanning. DMC counts the numbers of rows in which each pair of columns disagree instead of counting the number of hits. DMC deletes a candidate as soon as the number of misses exceeds the maximum number of misses allowed for that pair. We also propose several optimization techniques that reduce the required memory size significantly. We evaluated our algorithms by using four data sets, viz. Web access logs, a Web page-link graph, news documents and a dictionary. These data sets have between 74,000 and 700,000 items. Experiments show that DMC can find high-confidence rules for such large data sets efficiently.

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.

The article summarizes recent research into data-mining techniques that are in progress at Stanford: 1. The Google search engine: beating Yahoo et al. at their own game. 2. Query flocks: generalizing association rules/market baskets in a query precompiler that uses a relational DBMS effectively. 3. Synthesizing knowledge from the Web: exploiting the Web's redundancy to extract data automatically. 4. Detecting low-frequency events: unlike marketing, where you only care about items that lots of people buy, extracting intelligence from text usually requires looking for a small number of unexpected juxtapositions of terms.

Existing data-integration systems based on the mediation architecture employ a variety of mechanisms to describe the query-processing capabilities of sources. However, these systems do not compute the capabilities of the mediators based on the capabilities of the sources they integrate. In this paper, we proposed a framework to capture a rich variety of query-processing capabilities of data sources and mediators. We present algorithms to compute the set of supported queries of a mediator, based on the capability limitations of its sources. Our algorithms take into consideration a variety of query-processing techniques employed by mediators to enhance the set of supported queries.

Introduction The TSIMMIS system [1] integrates data from multiple heterogeneous sources and provides users with seamless integrated views of the data. It translates a user query on the integrated views into a set of source queries and postprocessing steps that compute the answer to the user query from the results of the source queries. TSIMMIS uses a mediation architecture [11] to accomplish this (Figure 1). User Source 1 Source 2 Source N Mediator Figure 1: The TSIMMIS Architecture Many other data integration systems like Garlic [2, 9] and Information Manifold [4] employ a similar architecture. One of the distinguishing features of TSIMMIS is its use of a semi-structured data model (called the Object Exchange Model or OEM [7]) for dealing with the heterogeneity of the data sources. In particular, it employs source wrappers [3] that provide a uniform OEM interface to the mediator. In SIGMO

Association-rule mining has proved a highly successful technique for extracting useful information from very large databases. This success is attributed not only to the appropriateness of the objectives, but to the fact that a number of new query-optimization ideas, such as the “a-priori” trick, make association-rule mining run much faster than might be expected. In this paper we see that the same tricks can be extended to a much more general context, allowing efficient mining of very large databases for many different kinds of patterns. The general idea, called “query flocks,” is a generate-and-test model for data-mining problems. We show how the idea can be used either in a general-purpose mining system or in a next generation of conventional query optimizers.

On-line analytical processing (OLAP) is a recent and important application of database systems. Typically, OLAP data is presented as a multidimensional "data cube." OLAP queries are complex and can take many hours or even days to run, if executed directly on the raw data. The most common method of reducing execution time is to precompute some of the queries into summary tables (subcubes of the data cube) and then to build indexes on these summary tables. In most commercial OLAP systems today, the summary tables that are to be precomputed are picked first, followed by the selection of the appropriate indexes on them. A trial-and-error approach is used to divide the space available between the summary tables and the indexes. This two-step process can perform very poorly. Since both summary tables and indexes consume the same resource-space-their selection should be done together for the most efficient use of space. The authors give algorithms that automate the selection of summary tables and indexes. In particular, they present a family of algorithms of increasing time complexities, and prove strong performance bounds for them. The algorithms with higher complexities have better performance bounds. However, the increase in the performance bound is diminishing, and they show that an algorithm of moderate complexity can perform fairly close to the optimal.

Introduces the concept of representative objects, which uncover the inherent schema(s) in semi-structured, hierarchical data sources and provide a concise description of the structure of the data. Semi-structured data, unlike data stored in typical relational or object-oriented databases, does not have a fixed schema that is known in advance and stored separately from the data. With the rapid growth of the World Wide Web, semi-structured hierarchical data sources are becoming widely available to the casual user. The lack of external schema information currently makes browsing and querying these data sources inefficient at best, and impossible at worst. We show how representative objects make schema discovery efficient and facilitate the generation of meaningful queries over the data.

We consider the problem of analyzing market-basket data and present several important contributions. First, we present a new algorithm for finding large itemsets which uses fewer passes over the data than classic algorithms, and yet uses fewer candidate itemsets than methods based on sampling. We investigate the idea of item reordering, which can improve the low-level efficiency of the algorithm. Second, we present a new way of generating "implication rules," which are normalized based on both the antecedent and the consequent and are truly implications (not simply a measure of co-occurrence), and we show how they produce more intuitive results than other methods. Finally, we show how different characteristics of real data, as opposed to synthetic data, can dramatically affect the performance of the system and the form of the results. 1 Introduction Within the area of data mining, the problem of deriving associations from data has recently received a great deal of attention. The prob...

Mediators are used for integration of heterogeneous information sources. We present a system for declaratively specifying mediators. It is targeted for integration of sources with unstructured or semi-structured data and/or sources with changing schemas. We illustrate the main features of the Mediator Specification Language (MSL), show how they facilitate integration, and describe the implementation of the system that interprets the MSL specifications.

When answering queries using external information sources, their contents can be described by views.To answer a query, we must rewrite it using the set of views presented by the

Our motivationis the piecing together of tidbits of information found on the "web" into a usable information structure.The problem is related to that of computing the natural outerjoin of many relations in a way that preserves all possible connections among facts.

Decision support applications involve complex queries on very large databases. Since response times should be small, query optimization is critical. Users typically view the data as multidimensional data cubes. Each cell of the data cube is a view consisting of an aggregation of interest, like total sales. The values of many of these cells are dependent on the values of other cells in the data cube..A common and powerful query optimization technique is to materialize some or all of these cells rather than compute them from raw data each time. Commercial systems differ mainly in their approach to materializing the data cube. In this paper, we investigate the issue of which cells (views) to materialize when it is too expensive to materialize all views. A lattice framework is used to express dependencies among views. We present greedy algorithms that work off this lattice and determine a good set of views to materialize. The greedy algorithm performs within a small constant factor of optimal under a variety of models. We then consider the most common case of the hypercube lattice and examine the choice of materialized views for hypercubes in detail, giving some good tradeoffs between the space used and the average time to answer a query. 1

No abstract available.

We describe a numbering scheme for versions with alternatives that has a useful lexicographical ordering. The version hierarchy is a tree. By inspection of the version numbers, we can easily determine whether one version is an ancestor of another. If so, we can determine the version sequence between these two versions. If not, we can determine the most recent common ancestor to these two versions (i.e., the least upper bound, lub). Sorting the version numbers lexicographically results in a version being followed by all descendants and preceded by all its ancestors. We use a representation of nonnegative integers that is self delimiting and whose lexicographical ordering matches the ordering by value.>

No abstract available.

Constraints are a valuable tool for managing information across multiple databases, as well as for general purposes of assuring data integrity. However, efficient implementation of constraint checking is difficult. In this paper we explore techniques for assuring constraint satisfaction without performing a complete evaluation of the constraints. We consider methods that use only constraint definitions, methods that use constraints and updates, and methods that use constraints, updates, and “local” data.

There is a straightforward algorithm for computing the transitive-closure of an n-node graph in $O(\log ^2 n)$ time on an EREW-PRAM, using $n^3 / \log n$ processors, or indeed with $M(n) / \log n$ processors if serial matrix multiplication in $M(n)$ time can be done. This algorithm is within a log factor of optimal in work (processor-time product), for solving the all-pairs transitive-closure problem for dense graphs. However, this algorithm is far from optimal when either (a) the graph is sparse, or (b) we want to solve the single-source transitive-closure problem. It would be ideal to have an $\mathcal{NC}$ algorithm for transitive-closure that took about e processors for the single-source problem on a graph with n nodes and $e \geqq n$ arcs, or about $en$ processors for the all-pairs problem on the same graph. While an algorithm that good cannot be offered, algorithms with the following performance can be offered. (1) For single-source, $\tilde{O}(n^\varepsilon )$ time with $\tilde O(en^{1 - 2\varepsilon } )$ processors, provided $e > n^{2 - 3\varepsilon } $, and (2) forall-pairs, $\tilde{O}(n^\varepsilon )$ time and $\tilde O(en^{1 - \varepsilon } )$ processors, provided $e \geqq n^{2 - 2\varepsilon } $. Each of these claims assumes that $0 < \varepsilon \leqq \frac{1}{2}$. Importantly, the algorithms are (only) high-probability algorithms; that is, if they find a path, then a path exists, but they may fail to find a path that exists with probability at most $2^{ - \alpha c} $, where $\alpha $ is some positive constant, and c is a multiplier for the time taken by the algorithm. However, it is shown that incorrect results can be detected, thus putting the algorithm in the “Las Vegas” class. Finally, it is shown how to do “breadth-first-search” with the same performance as can be achieved for single-source transitive closure.

Suppose a directed graph has its arcs stored in secondary memory, and we wish to compute its transitive closure, also storing the result in secondary memory. We assume that an amount of main memory capable of holding s “values” is available, and that s lies between n, the number of nodes of the graph, and e, the number of arcs. The cost measure we use for algorithms is the I/O complexity of Kung and Hong, where we count 1 every time a value is moved into main memory from secondary memory, or vice versa.

There is a straightforward algorithm for computing the transitive-closure of an n-node graph in $O(\log ^2 n)$ time on an EREW-PRAM, using $n^3 / \log n$ processors, or indeed with $M(n) / \log n$ processors if serial matrix multiplication in $M(n)$ time can be done. This algorithm is within a log factor of optimal in work (processor-time product), for solving the all-pairs transitive-closure problem for dense graphs. However, this algorithm is far from optimal when either (a) the graph is sparse, or (b) we want to solve the single-source transitive-closure problem. It would be ideal to have an $\mathcal{NC}$ algorithm for transitive-closure that took about e processors for the single-source problem on a graph with n nodes and $e \geqq n$ arcs, or about $en$ processors for the all-pairs problem on the same graph. While an algorithm that good cannot be offered, algorithms with the following performance can be offered. (1) For single-source, $\tilde{O}(n^\varepsilon )$ time with $\tilde O(en^{1 - 2\varepsil...

For certain sets of logical rules, one can demonstrate that for every proof tree there is another tree proving the same fact and having a special form. One technique for detecting such opportunities is to reduce the question to one of conjunctive-query containment. A more powerful technique is to test whether one conjunctive query is contained in the infinite union of conjunctive queries formed by expanding a set of recursive rules. We discuss two applications of these techniques. First, we give tests for commutativity of linear rules. When linear rules commute, we can reduce the complexity of “counting” methods for query evaluation from exponential to polynomial; commutativity also implies separability in the sense of Naughton. A second application is the discovery of linear rules that are equivalent to given nonlinear rules.

We show that for any safe datalog program P1 and any query Q (predicate of P1 with some bound arguments), there is another safe datalog program P2 that produces the answer to Q and takes no more time when evaluated by semi-naive evaluation than when P1 is evaluated topdown.

We present an algorithm for the efficient evaluation of a useful subset of recursive queries. Like the magic sets transformation, the algorithm consists of a rewriting phase followed by semi-naive bottom-up evaluation of the resulting rules. We prove that on a wide range of recursions, this algorithm achieves a factor of Ο(n) speedup over magic sets. Intuitively, the transformations in this algorithm achieve their performance by reducing the arity of the recursive predicates in the transformed rules.

The synchronizer is a simulation methodology introduced by Awerbuch [J. Assoc. Comput. Math., 32 (1985), pp. 804–823] for simulating a synchronous network by an asynchronous one, thus enabling the execution of a synchronous algorithm on an asynchronous network. In this paper a novel technique for constructing network synchronizers is presented. This technique is developed from some basic relationships between synchronizers and the structure of a t-spanning subgraph over the network. As a special result, a synchronizer for the hypercube with optimal time and communication complexities is obtained.

Selection of an appropriate order for the evaluation of subgoals in a logical rule frequently is essential for efficiency. We formulate the problem as one of feasible subgoal orders and show that the question is inherently exponential in time. The proof is by reduction from linear-space alternating Turing machine recognition, which appears to be far easier, in this case, than the more obvious reduction from exponential-time (ordinary) Turing machines

Considered is the question of whether top-down (Prolog-like) evaluation of a set of logical rules can be guaranteed to terminate. The NAIL! system is designed to process programs consisting of logical rules and to select, for each fragment of the program, the best from among many possible strategies for its evaluation. In the context of such a system, it is essential that termination tests be fast. Thus, the “uniqueness” property of logical rules is introduced. This property is satisfied by many of the common examples of rules and is easily recognized. For rules with this property, a set of inequalities, whose satisfaction is sufficient for termination of the rules, can be generated in polynomial time. Then a polynomial test for satisfaction of constraints generated by this process is given.

Article Free Access Share on An optimal synchronizer for the hypercube Authors: David Peleg Department of Computer Science, Stanford University, Stanford, California Department of Computer Science, Stanford University, Stanford, CaliforniaView Profile , Jeffrey D. Ullman Department of Computer Science, Stanford University, Stanford, California Department of Computer Science, Stanford University, Stanford, CaliforniaView Profile Authors Info & Claims PODC '87: Proceedings of the sixth annual ACM Symposium on Principles of distributed computingDecember 1987 Pages 77–85https://doi.org/10.1145/41840.41847Published:01 December 1987Publication History 61citation491DownloadsMetricsTotal Citations61Total Downloads491Last 12 Months42Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We briefly sketch the development of the various branches of database theory. One important branch is the theory of relational databases, including such areas as dependency theory, universal-relation theory, and hypergraph theory. A second important branch is the theory of concurrency control and distributed databases. Two other branches have not in the past been given the attention they deserve. One of these is “logic and databases,” and the second is “object-oriented database systems,” which to my thinking includes systems based on the network or hierarchical data models. Both these areas are going to be more influential in the future.

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 \times n$ grid among processors, the law $(c + n)t = \Omega (n^3 )$ must hold. Further, there must be a single path through the grid along which there are t communication steps, where $(d + 1)t = \Omega (n^2 )$. Depending on the machine organization, either law may be the more significant.

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.

Article Free Access Share on Convergence of sideways query evaluation Authors: Foto Afrati National Technical University of Athens National Technical University of AthensView Profile , Christos Papadimitriou Stanford University Stanford UniversityView Profile , George Papageorgiou National Technical University of Athens National Technical University of AthensView Profile , Athena Roussou National Technical University of Athens National Technical University of AthensView Profile , Yehoshua Sagiv Stanford University Stanford UniversityView Profile , Jeffrey D Ullman Stanford University Stanford UniversityView Profile Authors Info & Claims PODS '86: Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systemsJune 1985Pages 24–30https://doi.org/10.1145/6012.15400Published:01 June 1985Publication History 15citation220DownloadsMetricsTotal Citations15Total Downloads220Last 12 Months10Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Several methods for implementing database queries expressed as logical rules are given and they are compared for efficiency. One method, called “magic sets,” is a general algorithm for rewriting logical rules so that they may be implemented bottomUP (= forward chaining) in a way that cuts down on the irrelevant facts that are generated. The advantage of this scheme is that by working bottom-up, we can take advantage of efficient methods for doing massive joins. Two other methods are ad hoc ways of implementing “linear” rules, i.e., rules where at most one predicate in any body is recursive. These methods are

No abstract available.

We examine methods of implementing queries about relational databases in the case where these queries are expressed in first-order logic as a collection of Horn clauses. Because queries may be defined recursively, straightforward methods of query evaluation do not always work, and a variety of strategies have been proposed to handle subsets of recursive queries. We express such query evaluation techniques as “capture rules” on a graph representing clauses and predicates. One essential property of capture rules is that they can be applied independently, thus providing a clean interface for query-evaluation systems that use several different strategies in different situations. Another is that there be an efficient test for the applicability of a given rule. We define basic capture rules corresponding to application of operators from relational algebra, a top-down capture rule corresponding to “backward chaining,” that is, repeated resolution of goals, a bottom-up rule, corresponding to “forward chaining,” where we attempt to deduce all true facts in a given class, and a “sideways” rule that allows us to pass results from one goal to another.

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.

We suggest a new approach to database updates, in which a database is treated as a collection of theories. We investigate two issues: a) equivalence of databases under update operations, b) simultaneous multiple update operations.

We define the notion of independent views to indicate whether the range values of the two views may be achieved independently The concept of complementary views indicates when the domain element can be uniquely determined by the range values of the two complementary views We consider the relationship between independent and complementary views In unrestricted domains, a view (but not the identity or empty view) can have more than one complementary, independent view Databases, however, are more restricted domains They are finite power sets A view is monotonic if it preserves inclusion However, in finite power sets when all views are monotonic, if a given view has another view which is independent and complementary, then this view is unique.

Article Correcting faults in write-once memory Share on Authors: Danny Dolev View Profile , David Maier View Profile , Ilarry Mairson View Profile , Jeffrey Ullman View Profile Authors Info & Claims STOC '84: Proceedings of the sixteenth annual ACM symposium on Theory of computingDecember 1984 Pages 225–229https://doi.org/10.1145/800057.808685Online:01 December 1984Publication History 2citation230DownloadsMetricsTotal Citations2Total Downloads230Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

System/U is a universal relation database system under development at Standford University which uses the language C on UNIX. The system is intended to test the use of the universal view, in which the entire database is seen as one relation. This paper describes the theory behind System/U, in particular the theory of maximal objects and the connection between a set of attributes. We also describe the implementation of the DDL (Data Description Language) and the DML (Data Manipulation Language), and discuss in detail how the DDL finds maximal objects and how the DML determines the connection between the attributes that appear in a query.

The universal relation model aims at achieving complete access-path independence in relational databases by relieving the user of the need for logical navigation among relations. We clarify the assumptions underlying it and explore the approaches suggested for implementing it. The essential idea of the universal relation model is that access paths are embedded in attribute names. Thus attribute names must play unique “roles.” Furthermore, it assumes that for every set of attributes there is a basic relationship that the user has in mind. The user's queries refer to these basic relationships rather than to the underlying database. Two fundamentally different approaches to the universal relation model have been taken. According to the first approach, the user's view of the database is a universal relation or many universal relations, about which the user poses queries. The second approach sees the model as having query-processing capabilities that relieve the user of the need to specify the logical access path. Thus, while the first approach gives a denotational semantics to query answering, the second approach gives it an operational semantics. We investigate the relationship between these two approaches.

We suggest here a methodology for updating data bases with integrity constrain & and rules for deriving inex plicit information. First we consider the problem of updating arbitrary theories by inserting inu, them or delet

Manifestations of the "universal relation assumption" can be seen either as definitions of a one-relation user view of data, or as algorithms for answering queries about arbitrary sets of attributes. In this paper we explore equivalences between these two points of view. We show that if the user's view is the representative instance, then our ability to answer queries about the universal relation, by applying relational algebra to the actual database, is equivalent to a "boundedness" condition on the dependencies of the database scheme. Further, whenever this condition holds, there is a finite union of lossless tableau mappings that produces the desired relation.

We develop a theory of relations that are constructed by the union and selection operations from fragment relations. Algorithms for inserting and deleting from relations that are composed of physical fragments are discussed, and we show when such insertions and deletions are meaningful. We also show how to find an access set for a relation, that is, a set of fragments sufficient to produce the relation, and we apply the test to the question of how the fragmentation of relations interacts with a query on the relation, showing that a selection on the relation can be implemented by retrieving a set of physical fragments that forms an access set for another particular relation.

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.

Template dependencies (TD’s) are a class of data dependencies that include multivalued and join dependencies and embedded versions of these. A collection of techniques, examples and results about TD’s are presented. The principal results are: 1) Finite implication (implication over relations with a finite number of tuples) is distinct from unrestricted implication for TD’s. 2) There are, for TD’s over three or more attributes, infinite chains of increasingly weaker and increasingly stronger full TD’s. 3) However, there are weakest (nontrivial) and strongest full TD’s over any given set of attributes. 4) Over two attributes, there are only three distinct TD’s. 5) There is no weakest (not necessarily full) TD over any set of three or more attributes. 6) There is a finite relation that obeys every strictly partial TD but no full TD. 7) The conjunction of each finite set of full TD’s is equivalent to a single full TD. However, the conjunction of a finite set of (not necessarily full) TD’s is not necessarily equivalent to a single TD and the disjunction of a finite set of full TD’s is not necessarily equivalent to a single TD. 8) There is a finite set of TD’s with an infinite Armstrong relation but no finite Armstrong relation. 9) A necessary and sufficient condition for the existence of finite Armstrong relations for sets of TD’s can be formulated in terms of the implication structure of TD’s.

The universal relation concept is intended to provide the database user with a simplified model in which he can compose queries without regard to the underlying structure of the relations in the database. Frequently, the lossless join criterion provides the query interpreter with the clue needed to interpret the query as the user intended. However, some examples exist where interpretation by the lossless-join rule runs contrary to our intuition. To handle some of these cases, we propose a concept called maximal objects , which modifies the universal relation concept in exactly those situations where it appears to go awry—when the underlying relational structure has “cycles.” We offer examples of how the maximal object concept provides intuitively correct interpretations. We also consider how one might construct maximal objects mechanically from purely syntactic structural information—the relation schemes and functional dependencies—about the database.

article Free AccessOn Kent's “Consequences of assuming a universal relation” (Technical correspondance) Author: Jeffrey D. Ullman Dept. of Computer Science, Stanford University, Stanford, CA Dept. of Computer Science, Stanford University, Stanford, CAView Profile Authors Info & Claims ACM Transactions on Database SystemsVolume 8Issue 4Dec. 1983 pp 637–643https://doi.org/10.1145/319996.320017Published:01 December 1983Publication History 12citation441DownloadsMetricsTotal Citations12Total Downloads441Last 12 Months16Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

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 [6] of hypergraphs and the process of tableau reduction [1] that holds only for acyclic hypergraphs.

In this paper, we try to put to rest many of the objections to the relation concept that have appeared in the literature. First, we shall taxonomize the varieties of ideas that are sometimes called the universal relation assumption. Then, we consider some of the arguments pro and con. In some cases, the arguments against were expressed prematurely, and solutions to the problems they expose have since been found. In other cases, the arguments against are simply fallacious. In still other cases, the problems pointed out are real, but simply serve to point out that the advantages of the relation are not gotten for free. We shall conclude the paper with a description of the algorithm used to interpret queries in System/U, and the reasoning behind it.

The design of integrated cLrcuJts to Implement arbitrary regular expressions is considered In general, a regular expression with n operands may be converted into a nondetermmlstlc fimte automaton with at most n states and n trans~uons Instead of converting the nondetermtntsttc device to a determm~suc one, two ways of implementing the nondetermlnistlc dewce directly are proposed.One approach is to produce a PLA (programmable logic array) of approximate dimensions n rows and 2n columns by representing the states of the nondetermm~stlc fimte automaton directly by columns This approach, whde theoreucally suboptimal, makes use of carefully developed technology and, because of the care with which PLA implementation has been done, may be the preferred techmque m many real sttuatlons Another approach ~s to use the hierarchical structure of the automaton produced from the regular expression by the McNaughton-Yamada algorithm to grade a hierarchical layout of the ctrcmt.This method produces a clrcmt O(x/-~n) on a side and ~s, to w~thin a constant factor, the best that can be done m general Categories and Subject Descriptors: B 1 2 [Control Structures and Microprogramming]: Control Structure Performance Analysis and Design Aids--automatic synthesis, formal models; B.7 2 [Integrated Circuits]: Destgn Aids-

Relauonal database theory has d~scovered complete axlomauzations for functional and multivalued dependencies.However, a database design system based on dependencies must deal with some more general kinds of dependencies than these--at least with embedded multivalued dependencies Yet no axiomatizatton for embedded multivalued dependencies is known.A more general class of dependencies, called "template dependencies," is detrmed in this paper, and a complete ax~omatizat~on is given for them.

One problem concerning the universal relation assumption is the inability of known methods to obtain a database scheme design in the general case, where the real-world constraints are given by a set of dependencies that includes embedded multivalued dependencies. We propose a simpler method of describing the real world, where constraints are given by functional dependencies and a single join dependency. The relationship between this method of defining the real world and the classical methods is exposed. We characterize in terms of hypergraphs those multivalued dependencies that are the consequence of a given join dependency. Also characterized in terms of hypergraphs are those join dependencies that are equivalent to a set of multivalued dependencies.

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].

We consider the problem of wiring together two parallel rows of points under a variety of conditions. The options include whether we allow the rows to slide relative to one another, whether we use only rectilinear wires or arbitrary wires, and whether we can use wires in one layer or several layers. In almost all of these combinations of conditions, we can provide a polynomial-time algorithm to minimize the distance between the parallel rows of points. We also compare two fundamentally different wiring approaches, where one and two layers are used. We show that although the theoretical model implies that there can be great gains for the two-layer strategy, even in cases where no crossovers are required, when we consider typical design rules for laying out VLSI circuits there is no substantial advantage to the two-layer approach over the one-layer approach.

We present an algorithm for constructing a tree to satisfy a set of lineage constraints on common ancestors. We then apply this algorithm to synthesize a relational algebra expression from a simple tableau, a problem arising in the theory of relational databases.

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.

Deadlock states have been observed in existing computer networks, emphasizing the need for carefully designed flow control procedures (controllers) to avoid deadlocks. Such a deadlock-free controller is readily found if we allow it global information about the overall network state. Generally, this assumption is not realistic, and we must resort to deadlock-free local controllers using only packet and node information. We present here several types of such controllers, we study their relationship and give a proof of their optimality with respect to deadlock-free controllers using the same set of local parameters.

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.

A large class of dependencies, called template dependencies, was introduced in Sadri and Ullman [1979], and a complete set of inference rules (axioms) was given for it. In this paper, we investigate the interaction between template dependencies and functional dependencies. We develop techniques for partially deciding which template and functional dependencies are logically implied by a set of template and functional dependencies. Since template dependencies include all dependencies, besides functional dependencies, known to us (such as multivalued, join, mutual, generalized mutual, and subset dependencies, and their embedded versions), the results of this paper enable us to apply the techniques from Sadri and Ullman [1979] to any set of data dependencies.

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.

In this paper an algonthra for the determination of run-tune types m a programming language requiring no type declaratmns is presented It ~s demonstrated that this algorithm is superior to other pubhshed algortthms m the sense that it produces stronger assertions about the set of possible types for variables than do other known algorithms.In fact this algonthra is shown to be the best possible algorithm from among all those that use the same set of prumttve operators.

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.

We consider the question of how powerful a relational query language should be and state two principles that we feel any query language should satisfy. We show that although relational algebra and relational calculus satisfy these principles, there are certain queries involving least fixed points that cannot be expressed by these languages, yet that also satisfy the principles. We then consider various extensions of relational algebra to enable it to answer such queries. Finally, we discuss our extensions to relational algebra in terms of a new programming language oriented model for queries.

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.

Deadlock is one of the most serious system failures that can occur in a computer system or a network. Deadlock states have been observed in existing computer networks emphasizing the need for carefully designed flow control procedures (controllers) to avoid deadlocks. Such a deadlock-free controller is readily found if we allow it global information about the overall network state. Generally, this assumption is not realistic, and we must resort to deadlock free local controllers using only packet and node information. We present here several types of such controllers, we study their relationship and give a proof of their optimality with respect to deadlock free controllers using the same set of local parameters.

Many database queries can be formulated in terms of expressions whose operands represent tables of information (relations) and whose operators are the relational operations select, project, and join. This paper studies the equivalence problem for these relational expressions, with expression optimization in mind. A matrix, called a tableau, is proposed as a natural representative for the value of an expression. It is shown how tableaux can be made to reflect functional dependencies among attributes. A polynomial time algorithm is presented for the equivalence of tableaux that correspond to an important subset of expressions, although the equivalence problem is shown to be NP-complete under slightly more general circumstances.

Answering queries in a relational database often requires that the natural join of two or more relations be computed. However, the result of a join may not be what one expects. In this paper we give efficient algorithms to determine whether the join of several relations has the intuitively expected value (is lossless ) and to determine whether a set of relations has a subset with a lossy join. These algorithms assume that all data dependencies are functional. We then discuss the extension of our techniques to the case where data dependencies are multivalued.

The design of several database query languages has been influenced by Codd's relational algebra. This paper discusses the difficulty of optimizing queries based on the relational algebra operations select, project, and join. A matrix, called a tableau, is proposed as a useful device for representing the value of a query, and optimization of queries is couched in terms of finding a minimal tableau equivalent to a given one. Functional dependencies can be used to imply additional equivalences among tableaux. Although the optimization problem is NP-complete, a polynomial time algorithm exists to optimize tableaux that correspond to an important subclass of queries.

This paper considers the design of a system to answer partial-match queries from a file containing a collection of records, each record consisting of a sequence of fields. A partial-match query is a specification of values for zero or more fields of a record, and the answer to a query is a listing of all records in the file whose fields match the specified values. A design is considered in which the file is stored in a set of bins. A formula is derived for the optimal number of bits in a bin address to assign to each field, assuming the probability that a given field is specified in a query is independent of what other fields are specified. Implications of the optimality criterion on the size of bins are also discussed.

We present the best known algorithm for the determination of run-time types in a programming language requiring no type declarations. We demonstrate that it is superior to other published algorithms and that it is the best possible algorithm from among all those that use the same set of primitive operators.

Many useful database queries can be formulated in terms of expressions whose operands are relations and whose operators are the relational operations select, project, and join. This paper investigates the computational complexity of optimizing relational expressions of this form under a variety of cost measures. A matrix, called a tableau, is proposed as a conventient representative for the value of an expression. Functional dependencies can be used to imply additional equivalences among tableaux. The optimization problem is shown to be NP-complete, but we can give a polynomial time algorithm to optimize tableaux that correspond to an important subclass of expressions.

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.

Previous work on optimal code generation has usually assumed that the underlying machine has identical registers and that all operands fit in a single register or memory location. This paper considers the more realistic problem of generating optimal code for expressions involving single and double length operands, using several models of register-pair machines permitting both single and double word instructions. With register-pair machines a new phenomenom arises that is not present in optimal code generation for single register machines: In an optimal evaluation of an expression it may be necessary to oscillate back and forth between evaluating subexpressions of the expression.A linear-time optimal code generation algorithm is derived for a register-pair machine in which all registers are interchangeable. The algorithm is based on showing that for this model there is an optimal evaluation sequence with limited oscillation between the sub-trees dominated by the children of a given node. For other machine models including the familiar even-odd register-pair machine, optimal evaluation sequences can always require unlimited oscillation.

This paper shows the problem of generating optimal code for expressions containing common subexpressions is computationally difficult, even for simple expressions and simple machines. Some heuristics for code generation are given and their worst-case behavior is analyzed. For one register machines, an optimal code generation algorithm is given whose time complexity is linear in the size of an expression and exponential only in the amount of sharing.

We consider expressions whose arguments are relations and whose operators are chosen from among $\cup , \circ ,{}^*$, 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 finding connected components of an undirected graph.

Considered here, for a particular model of databases in which only information about relatively large sets of records can be obtained, is the question of whether one can from statistical information obtain information about individuals. Under the assumption that the data in the database is taken from arbitrary integers, it is shown that essentially nothing can be inferred. It is also shown that when the values are known to be imprecise in some fixed range, one can often deduce the values of individual records.

Easy as the task may seem, many compilers generate rather inefficient code. Some of the difficulty of generating good code may arise from the lack of realistic models for programming language and machine semantics. In this paper we show that the computational complexity of generating efficient code in realistic situations may also be a major cause of difficulty in the design of good compilers.

We explore the notion of an induction variable in the context of a set-theoretic programming langugage. An appropriate definition, we believe, involves both the necessity that changes in the variable around a loop be easily computable and that they be small. We attempt to justify these requirements and show why they are independent assumptions. Next the question of what operators on sets play the role of +, − and * for arithmetic languages is explored, and several theorems allowing us recursively to detect induction variables in a loop are given. It is shown that most of the usual set operations do fit nicely into the theory and help form induction variables. The reason most variables fail to be induction variables concerns the structure of control flow, more than it does the operators applied.

The depth of a flow graph is the maximum number of back edges in a cycle free path, where a back edge is defined by some depth-first spanning tree for the flow graph. In the case of a reducible graph, the depth is independent of the DFST chosen. We show that the computation of the depth of a reducible flow graph may be done in polynomial time. Our algorithm is 0(ne) on a flow graph of n nodes and e edges. Since e≤2n for normal flow graphs, our algorithm is really 0(n2). While even an 0(n2) algorithm is not likely to be acceptable, it is suggestive of the possibility of a more efficient algorithm. Finally, we show that the general problem of computing the depth of an arbitrary flow graph with respect to an arbitrary DFST is NP-complete.

The problem of finding a longest common subsequence of two strings is discussed. This problem arises in data processing applications such as comparing two files and in genetic applications such as studying molecular evolution. The difficulty of computing a longest common subsequence of two strings is examined using the decision tree model of computation, in which vertices represent “equal - unequal” comparisons. It is shown that unless a bound on the total number of distinct symbols is assumed, every solution to the problem can consume an amount of time that is proportional to the product of the lengths of the two strings. A general lower bound as a function of the ratio of alphabet size to string length is derived. The case where comparisons between symbols of the same string are forbidden is also considered and it is shown that this problem is of linear complexity for a two-symbol alphabet and quadratic for an alphabet of three or more symbols.

Kildall has developed data propagation algorithms for code optimization in a general lattice theoretic framework. In another direction, Hecht and Ullman gave a strong upper bound on the number of iterations required for propagation algorithms when the data is represented by bit vectors and depth-first ordering of the flow graph is used. The present paper combines the ideas of these two papers by considering conditions under which the bound of Hecht and Ullman applies to the depth-first version of Kildall's general data propagation algorithm. It is shown that the following condition is necessary and sufficient: Let ƒ and g be any two functions which could be associated with blocks of a flow graph, let x be an arbitrary lattice element, and let 0 be the lattice zero. Then (*) (∀ƒ ,g,x ) [ƒ g (0) ≥ g (0) ∧ ƒ( x ) ∧ x ]. Then it is shown that several of the particular instances of the techniques Kildall found useful do not meet condition (*).

Trees in an n-node forest are merged according to instructions in a given sequence, while other instructions in the sequence ask for the lowest common ancestor of pairs of nodes. We show that any sequence of $O(n)$ such instructions can be processed “on-line” in $O(n\log n)$ steps on a random access computer. If we can accept our answer “off-line”, that is, no answers need to be produced until the entire sequence of instructions has been seen, then we may perform the task in $O(n\alpha (n))$ steps, where $\alpha (n)$ is the very slowly growing inverse Ackermann function defined in [14]. A third algorithm solves a problem of intermediate complexity. We require the answers on-line, but we assume that all tree merging instructions precede the information requests. This algorithm requires $O(n \log \log n)$ time. We apply the first on-line algorithm to a problem in code optimization, that of computing immediate dominators in a reducible flow graph. We show how this computation can be performed in $O(n\log n)$ steps.

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.

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.

Article Free Access Share on Application of lattice algebra to loop optimization Authors: Amelia Fong Princeton University, Princeton N. J. Princeton University, Princeton N. J.View Profile , John Kam Princeton University, Princeton N. J. Princeton University, Princeton N. J.View Profile , Jeffrey Ullman Princeton University, Princeton N. J. Princeton University, Princeton N. J.View Profile Authors Info & Claims POPL '75: Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languagesJanuary 1975 Pages 1–9https://doi.org/10.1145/512976.512977Online:01 January 1975Publication History 13citation241DownloadsMetricsTotal Citations13Total Downloads241Last 12 Months8Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In this paper we derive upper bounds on the complexity of LR(k) testing both when k is considered to be a fixed integer and also when k is considered to be a parameter of the problem. In the latter case, we show that the lower bounds on the running time of such algorithms depend very strongly on the representation chosen for k. Thus LR(k) testing is NP-complete when k is expressed in unary and complete for nondeterministic exponential time when k is expressed in binary.These results carry over to many other parameterized classes of grammars, such as the LL(k), strong LL(k), SLR(k), LC(k), strong LC(k), BRC(l,k), BC(l,k) and extended precedence (l,k) grammars.

A model of protection mechanisms in computing systems is presented and its appropriateness is demonstrated. The “safety” problem for protection systems under our model is to determine in a given situation whether a subject can acquire a particular right to an object. In restricted cases, one can show that this problem is decidable, i.e., there is an algorithm to determine whether a system in a particular configuration is safe. In general, and under surprisingly weak assumptions, one cannot decide if a situation is safe. Various implications of this fact are discussed.

In [1], Kennedy conjectures that for every n node reducible flow graph, there is a sequence of nodes (with repetitions) of length O(nlogn) 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(nlogn) time.

We investigate the evaluation of an $(n - 1)$st degree polynomial at a sequence of n points. It is shown that such an evaluation reduces directly to a simple convolution if and only if the sequence of points is of the form $b, ba,ba^2 , \cdots ,ba^{n - 1} $ for complex numbers a and b (the so-called “chirp transform”). By more complex reductions we develop an $O(n\log n)$ evaluation algorithm for sequences of points of the form \[ b + c + d,\quad ba^2 + ca + d,\quad ba^4 + ca^2 + d, \cdots \] for complex numbers a, b, c and d. Finally we show that the evaluation of an $(n - 1)$st-degree polynomial and all its derivatives at a single point requires at most $O(n\log n)$ steps.

A simple, iterative bit propagation algorithm for solving global data flow analysis problems such as “available expressions” and “live variables” is presented and shown to be quite comparable in speed to the corresponding interval analysis algorithm. This comparison is facilitated by a result relating two parameters of a reducible flow graph (rfg). Namely, if G is an rfg, d is the largest number of back edges found in any cycle-free path in G, and k is the length of the interval derived sequence of G, then $k \geqq d$. (Intuitively, k is the maximum nesting depth of loops in a computer program, while d is a measure of the maximum loop-interconnectedness.) The node ordering employed by the simple algorithm is the reverse of the order in which a node is last visited while growing any depth-first spanning tree of the flow graph. In addition, a dominator algorithm for an rfg is presented which takes O(edges) bit vector steps.

It is established that if G is a reducible flow graph, then edge ( n, m ) is backward (a back latch) if and only if either n = m or m dominates n in G . Thus, the backward edges of a reducible flow graph are unique. Further characterizations of reducibility are presented. In particular, the following are equivalent: (a) G = ( N, E, n 0 ) is reducible. (b) The “dag” of G is unique. (A dag of a flow graph G is a maximal acyclic flow graph which is a subgraph of G .) (c) E can be partitioned into two sets E 1 and E 2 such that E 1 forms a dag D of G and each ( n, m ) in E 2 has n = m or m dominates n in G . (d) Same as (c), except each ( n, m ) in E 2 has n = m or m dominates n in D . (e) Same as (c), except E 2 is the back edge set of a depth-first spanning tree for G . (f) Every cycle of G has a node which dominates the other nodes of the cycle. Finally, it is shown that there is a “natural” single-entry loop associated with each backward edge of a reducible flow graph.

The following abstract problem models several practical problems in computer science and operations research: given a list L of real numbers between 0 and l, place the elements of L into a minimum number $L^ * $ of “bins” so that no bin contains numbers whose sum exceeds l. Motivated by the likelihood that an excessive amount of computation will be required by any algorithm which actually determines an optimal placement, we examine the performance of a number of simple algorithms which obtain “good” placements. The first-fit algorithm places each number, in succession, into the first bin in which it fits. The best-fit algorithm places each number, in succession, into the most nearly full bin in which it fits. We show that neither the first-fit nor the best-fit algorithm will ever use more than $\frac{17}{10}L^ * + 2$ bins. Furthermore, we outline a proof that, if L is in decreasing order, then neither algorithm will use more than $\frac{11}{9} L^ * + 4$ bins. Examples are given to show that both upper bounds are essentially the best possible. Similar results are obtained when the list L contains no numbers larger than $\alpha < 1$.

We propose a new architecture for dynamic memories in which the contents of any cell in memory can be accessed by applying a sequence of two primitive memory operations. The advantage of our memory over previous designs is its fast sequential access. Any word in an n cell memory can be accessed in 0(log n) steps. However, once two consecutive words have been accessed, following words can be accessed in one step per word.

We consider methods of describing the syntax of programming languages in ways that are more flexible and natural than conventional BNF descriptions. These methods involve the use of ambiguous context-free grammars together with rules to resolve syntactic ambiguities. We show how efficient LL and LR parsers can be constructed directly from certain classes of these specifications.

There is an ordering of the nodes of a flow graph G which topologically sorts the dominance relation and can be found in 0(edges) steps. This ordering is the reverse of the order in which a node is last visited while growing any depth-first spanning tree of G. Moreover, if G is reducible, then this ordering topologically sorts the dag of G. Thus, for a reducible flow graph (rfg) there is a simple algorithm to compute the dominators of each node in 0(edges) bit vector steps.The main result of this paper relates two parameters of an rfg. If G is reducible, d is the largest number of back edges found in any cycle-free path in G, and k is the length of the interval derived sequence of G, then k≥d. From this result it follows that there is a very simple bit propagation algorithm (indeed, the obvious one) which also uses the above ordering, and is at least as good as the interval algorithm for solving all known global data flow problems such as available expressions and live variables.

We show that the problem of finding an optimal schedule for a set of jobs is polynomial complete even in the following two restricted cases.

Trees in an n node forest are to be merged according to instructions in a given sequence, while other instructions in the sequence ask for the lowest common ancestor of pairs of nodes. We show that any sequence of O(n) instructions can be processed “on line” in O(n log n) steps on a random access computer.

We present a new transformation that reduces the size and increases the speed of ${\text{LR}}(k)$ parsers. This transformation can be applied to all ${\text{LR}}(k)$ parsers including those produced by Knuth’s and DeRemer’s techniques. The transformation causes the parser to avoid reductions by productions of the form $A \to B$, where A and B are nonterminals.

This paper considers the problem of merging sets formed from a total of n items in such a way that at any time, the name of a set containing a given item can be ascertained. Two algorithms using different data structures are discussed. The execution times of both algorithms are bounded by a constant times $nG(n)$, where $G(n)$ is a function whose asymptotic growth rate is less than that of any finite number of logarithms of n.

We present a new transformation that reduces the size and increases the speed of LR(k) parsers. This transformation can be applied to all LR(k) parsers including those produced by Knuth's and DeRemer's techniques. The transformation causes the parser to avoid reductions by productions of the form A → B where A and B are non-terminals.

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*.

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.

Two generalizations of the simple precedence grammars are considered.The first, the weak precedence grammars, are shown to generate exactly the simple precedence languages.The second, the "simple" mixed strategy precedence grammars, are shown to generate exactly the deterministic context-free languages.Algorithms for their implementation are given, and the complexity of these algorithms studied.

Hashing functions are considered which store data "randomly" in a fixed size hash table with no auxiliary storage.It is known that if k out of the N locations have been previously filled randomly, then the expected number of locations which must be looked at until an empty one is found is 1 qk/(N --k -b 1).It is shown that there exist nonrandom hashing functions which are more efficient for certain values of k and N.However, it is shown that the 1 + k/(N -k + 1) figure is a "lower bound" on hashing performance in the following sense.If h is any hashing function such that the expected number of trials to insert the (k -b 1)st item into a table of size N is C(k, N), and if for some k, C(k, N) < 1 + k/(N -k -b 1), then there exists k' < k such that C(k', N) > 1 -b k/(N --k 4-1).Finally, it is shown that randomness is a sufficient but not necessary condition for attainment of the 1 4k/(N --k -4-1) performance for all k, and a necessary and sufficient condition is given.

We consider economical representations for the path information in a directed graph. A directed graph $G^t $ is said to be a transitive reduction of the directed graph G provided that (i) $G^t $ has a directed path from vertex u to vertex v if and only if G has a directed path from vertex u to vertex v, and (ii) there is no graph with fewer arcs than $G^t $ satisfying condition (i). Though directed graphs with cycles may have more than one such representation, we select a natural canonical representative as the transitive reduction for such graphs. It is shown that the time complexity of the best algorithm for finding the transitive reduction of a graph is the same as the time to compute the transitive closure of a graph or to perform Boolean matrix multiplication.

We provide a set of transformations capable of transforming a straight line program into any other equivalent one assuming no algebraic laws hold. We then show that optimization of straight line code under “reasonable” cost criteria can always be accomplished by applying sequences of these transformations in a prescribed order.

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 transformations 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.

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].

ABSTP~CT.A formal model is presented for paging algorithms under /-order nonstationary assumptions about program behavior.When processing a program under paging in a given memory, a given paging policy generates a certain (expected) number of page calls, i.e., its "cost."Under usual assumptions about memory system organization, minimum cost is always achieved by a demand paging algorithm.The minimum cost for /-order program behavior assumptions is expressed as a dynamic programming problem whose solution yields an optimal replacement algorithm.Solutions are exhibited in several 0-order cases of interest.Paging algorithms that implement and approximate the minimum cost are discussed.

We consider a program schema that models straight line intermediate level code. A complete set of equivalence preserving transformations on programs is found for the case in which programs are equivalent if and only if their output functions are identical. This result is extended to the case in which programs are deemed equivalent if their output functions can be shown equivalent under a fixed set of algebraic laws.

The problem of evaluating arithmetic expressions on a machine with N ≥ 1 general purpose registers is considered. It is initially assumed that no algebraic laws apply to the operators and operands in the expression. An algorithm for evaluation of expressions under this assumption is proposed, and it is shown to take the shortest possible number of instructions. It is then assumed that certain operators are commutative or both commutative and associative. In this case a procedure is given for finding an expression equivalent to a given one and having the shortest possible evaluation sequence. It is then shown that the algorithms presented here also minimize the number of storage references in the evaluation.

Two schemes for the specification of translations on a context-free grammar are proposed. The first scheme, called a generalized syntax directed translation (GSDT), consists of a context free grammar with a set of semantic rules associated with each production of the grammar. In a GSDT an input word is parsed according to the underlying context free grammar, and at each node of the tree, a finite number of translation strings are computed in terms of the translation strings defined at the descendants of that node. The functional relationship between the length of input and length of output for translations defined by GSDT's is investigated.

Classes of tape-bounded Turing machines similar to the on-line and off-line Turing machines, but without the restrictions that each machine halt and be deterministic, are studied. It is shown that the lower bounds on tape complexity of [1] depend on neither the halting assumption nor determinism. The existence of a dense hierarchy of complexity classes likewise does not depend on the halting assumption, and it is shown that below log n tape complexity there exists a dense hierarchy of complexity classes for two-way nondeterministic devices. It is also shown that the complexity classes of one-way, nondeterministic machines below linear large complexity are not closed under complementation and are larger that the corresponding deterministic complexity class.

It is shown that every two-way (deterministic) stack automaton language is accepted by a two-way (deterministic) stack automaton which for each input has a bound on the length of a valid computation. As a consequence, two-way deterministic stack languages are closed under complementation.

In this paper we consider the problem of deriving upper bounds on the number of state variables required for an n-state universal asynchronous state assignment (i.e., a state assignment which is valid for any n-state asynchronous sequential function). We will consider a special class of state assignments called SST assignments which were first derived by Liu [1] and later extended by Tracey [2]. In these assignments all variables which must change in a given transition are allowed to change simultaneously without critical races. The best universal bound known so far has been developed by Liu and requires 2so-1 state variables, where S0 = [log2n], n being the number of states, and [x] being the least integer > x. We shall show how this bound can be substantially improved. We further show that, by generalizing the state assignment to allow multiple codings for states, the bounds can be still further improved.

Four types of balloon automata (defined by one- or two-way input and deterministic or nondeterministic finite control) and closed classes of balloon automata were previously defined by the authors. A set of closed classes, one for each of the four types, is called a family if the classes use their infinite storage in the same way. The recursiveness and solvability of the emptiness problem for closed classes are investigated in the present paper. It is shown that in many cases the solvability of one of these questions for one closed class in a family implies that some other question are solvable for the closed classes of that family.

It is shown that if a language L is recognized by a (nondeterministic) single-tape Turing machine of time complexity T ( n ), then L is recognized by a (nondeterministic) offline Turing machine of tape complexity T 1/2 ( n ). If T ( n ) ≥ n 2 ;, L is recognized by a (nondeterministic) single-tape Turing machine of tape complexity T 1/2 ( n ). If a language L is recognized by a (nondeterministic) offline Turing machine of time complexity ( T ( n ), then L is recognized by a (nondeterministic) offline Turing machine of tape complexity ( T ( n ) log n ) 1/2 and by a (nondeterministic) single-tape Turing machine of that tape complexity if T ( n ) ≥ n 2 /log n .

A synchronization error is said to occur when either a bit which does not belong appears, or is detected in a channel between bits which were transmitted; or a bit which was transmitted is lost or not detected. A model for such a channel will be proposed, and a lower and upper bound on the redundancy necessary to correct a given error rate will be derived. We will consider the case of single synchronization error correction in detail, and stronger bounds will be derived for that case. We will consider multiple adjacent synchronization errors as a special case, and show that the bounds can be tightened in this case as well.

A synchronization error is said to occur when either a bit which does not belong is detected in a channel between bits which were transmitted, or a bit which was transmitted is never detected at the output. A block code which corrects a single synchronization error per block is presented, and it is shown that this code has, at most, three bits more redundancy than that of an optimal code for this class of errors. The code has the beneficial property that it is possible to separate the information positions from the check positions, and an appropriate method of encoding is shown.