This paper describes the concepts used in the implementation of DBDSGN, an experimental physical design tool for relational databases developed at the IBM San Jose Research Laboratory. Given a workload for System R (consisting of a set of SQL statements and their execution frequencies), DBDSGN suggests physical configurations for efficient performance. Each configuration consists of a set of indices and an ordering for each table. Workload statements are evaluated only for atomic configurations of indices, which have only one index per table. Costs for any configuration can be obtained from those of the atomic configurations. DBDSGN uses information supplied by the System R optimizer both to determine which columns might be worth indexing and to obtain estimates of the cost of executing statements in different configurations. The tool finds efficient solutions to the index-selection problem; if we assume the cost estimates supplied by the optimizer are the actual execution costs, it finds the optimal solution. Optionally, heuristics can be used to reduce execution time. The approach taken by DBDSGN in solving the index-selection problem for multiple-table statements significantly reduces the complexity of the problem. DBDSGN's principles were used in the Relational Design Tool (RDT), an IBM product based on DBDSGN, which performs design for SQL/DS, a relational system based on System R. System R actually uses DBDSGN's suggested solutions as the tool expects because cost estimates and other necessary information can be obtained from System R using a new SQL statement, the EXPLAIN statement. This illustrates how a system can export a model of its internal assumptions and behavior so that other systems (such as tools) can share this model.

The hot-set model, characterizing the buffer requirements of relational queries, is presented. This model allows the system to determine the optimal buffer space to be allocated to a query; it can also be used by the query optimizer to derive efficient execution plans accounting for the available buffer space, and by a query scheduler to prevent thrashing. The hot-set model is compared with the working-set model. A simulation study is presented.

In this paper, cost formulas are derived for the updates of data and indexes in a relational database. The costs depend on the data scan type and the predicates involved in the update statements. We show that update costs have a considerable influence, both in the context of the physical database design problem and in access path selection in query optimization for relational DBMSs.

System R supports a high-level relational user language called SQL which may be used by ad hoc users at terminals or as an embedded data sublanguage in PL/I or COBOL. Host-language programs with embedded SQL statements are processed by the System R precompiler which replaces the SQL statements by calls to a machine-language access module. The precompilation approach removes much of the work of parsing, name binding, and access path selection from the path of a running program, enabling highly efficient support for repetitive transactions. Ad hoc queries are processed by a similar approach of name binding and access path selection which takes place on-line when the query is specified. By providing a flexible spectrum of binding times, System R permits transaction-oriented programs and ad hoc query users to share a database without loss of efficiency. System R is an experimental database management system designed and built by members of the IBM San Jose Research Laboratory as part of a research program on the relational model of data. This paper describes the architecture of System R, and gives some preliminary measurements of system performance in both the ad hoc query and the “canned program” environments.

The process of logical database design consists of four phases: view modeling, view integration, schema optimization and schema mapping. View modeling is defined as the modeling of the usage and information structure perspectives of the real world from the point of view of different users and/or applications. The view integration phase combines these views into a single community view which is subjected to further optimization and mapping. As a result, instances of users' model may be altered and application programs transformed.This paper proposes a scheme for view representation which will facilitate the process of view integration. This is done by enhancing the data abstraction framework proposed by Smith and Smith. It takes into account the instance-level interrelationships among data and the identification of instances via these interrelationships. The usage perspective is incorporated as rules and assertions about schema- and instance-level insertion and deletion.The problem of view integration is briefly addressed. Valid transformations of views are indicated as a part of the integration process.

A maximal vector of a set ~s one which is not less than any other vector m all components We derive a recurrence relation for computing the average number of maxunal vectors m a set of n vectors m d-space under the assumpUon that all (nl) a relative ordermgs are equally probable.Solving the recurrence shows that the average number of maxmaa is O((ln n) a-~) for fixed d We use this result to construct an algorithm for finding all the maxima that have expected running tmae hnear m n (for sets of vectors drawn under our assumptions) We then use the result to find an upper bound on the expected number of convex hull points m a random point set KE~ WORDS AND eHRASES maxtma of a set of vectors, average number of maxtma, expected-tsme algorithms, analysts of algorithms, convex hulls, dynamtc programming CR CATEGORIES" 5 25, 5.39, 5.42 Permtsston to copy without fee all or part of this material ts granted provtded that the copies are not made or distributed for direct commercial advantage, the ACM copyrtght notice and the tRle of the pubhcatlon and its date appear, and notice ts gtven that copying ts by permission of the Assoctatton for Computmg Machinery To copy otherwtse, or to repubhsh, reqmres a fee and/or specific permtsslon This research was supported m part by the Nattonal Soence Foundation under Grant MCS 75-222-55 and the Office of Naval Research under

article Free Access Share on A clustering algorithm for hierarchical structuresACM Transactions on Database SystemsVolume 2Issue 1March 1977 pp 27–44https://doi.org/10.1145/320521.320531Published:01 March 1977Publication History 61citation787DownloadsMetricsTotal Citations61Total Downloads787Last 12 Months21Last 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

A major problem to be considered in the design of a data base is that of index selection. In this paper we present a model of a data base together with a probabilistic model for the transactions conducted with the data base: queries and updates. We obtain characterizations of the optimal solution to the best choice of indices. An algorithm is shown to solve this problem, which, in a number of cases, has a running time of O(m log m), where m is the number of attributes of the file.

We consider the problem of finding the minimum number K(n,c) of total switching functions of n variables necessary to cover the set of all switching functions which are specified in at most c positions. We find an exact solution for K(n,2) and an upper bound for K(n,c) which is better than a previously known upper bound by an exponential factor.

Precendece techniques have been widely used in the past in the construction of parsers. However, the restrictions imposed by them on the grammars were hard to meet. Thus, alteration of the rules of the grammar was necessary in order to make them acceptable to the parser. We have shown that, by keeping track of the possible set of rules that could be applied at any one time, one can enlarge the class of grammars considered. The possible set of rules to be considered is obtained directly from the information given by a labelled set of precedence relations. Thus, the parsers are easily obtained. Compared to the precedence parsers, this new method gives a considerable increase in the class of parsable grammars, as well as an improvement in error detection. An interesting consequence of this approach is a new decomposition technique for LR parsers.

A new family of grammars is introduced.A grammatical characterization of the one-way nondeterministic stack languages is obtained.Characterizations of the languages accepted by nonerasing stack automata and by checking automata are also derived.