Abstracts from other ACM publications.
ACM Computing Surveys September 1988
Statistical Profile Estimation in Database Systems Michael V. Mannino, Paicheng Chu, and Thomas Sager A statistical profile summarizes the instances of a database. It describes aspects such as the number of tuples, the number of values, the distribution of values, the correlation between value sets, and the distribution of tuples among secondary storage units. Estimation of database profiles is critical in the problems of query optimization, physical database design, and database performance prediction. This paper describes a model of a database of profile, relates this model to estimating the cost of database operations, and surveys methods of estimating profiles. The operators and objects in the model include build profile, estimate profile, and update profile. The estimate operator is classified by the relational algebra operator (select, project, join), the property to be estimated (cardinality, distribution of values, and other parameters), and the underlying method (parametric, nonparametric, and ad-hoc). The accuracy, overhead, and assumptions of methods are discussed in detail. Relevant research in both the database and the statistics disciplines is incorporated in the detailed discussion.
For Correspondence: Michael V. Mannino and Thomas Sager, Department of Management Science and Information Systems, University of Texas of Austin, Austin, Texas 78712; Paicheng Chu, Department of Accounting and Management Information Systems, Ohio State University, Columbus, Ohio 43210.
Semantic Data Models Joan Peckham and Fred Maryanski
Semantic data models have emerged from a requirement for more expressive conceptual data models. Current generation data models lack direct support for relationships, data abstraction, inheritance, constraints, unstructured objects, and the dynamic properties of an application. Although the need for data models with richer semantics is widely recognized, no single approach has won general acceptance. This paper describes the generic properties of semantic data models and presents a representative selection of models that have been proposed since the mid-1970s. In addition to explaining the features of the individual models, guidelines are offered for the compriosn of models. The paper concludes with a discussion of future directions in the area of conceptual data modeling.
For Correspondence: Department of Computer Science and Engineering, University of Connecticut, Storrs, Connecticut 06268.
Transactions on Database Systems December 1988
Extended Algebra and Calculs for|1NF Relational Databases Mark A. Roth, Henry F. Korth, and Abraham Silberschatz
Relaxing the assumption that relations are always in First-Normal-Form (1NF) necessitates a reexamination of the fundamentals of relational database theory. In this paper we take a first step towards unifying the various theories of|1NF databases. We start by determining an appropriate model to couch our formalisms in. We then define an extended relational calculus as the theoretical basis for our|1NF database query language. We define a minimal extended relational algebra and prove its equivalence to the|1NF relational calculus. We define a class of|1NF relations with certain "good" properties and extend our algebra operators to work within this domain. We prove certain desirable equivalences that hold only if we restrict our language to this domain.
For Correspondence: Department of Computer Science, University of Texas at Austin, Austin, TX 78712-1188.
A Homogeneous Relational Model and Query Languages for
Temporal Databases Shashi K. Gadia
In a temporal database, time values are associated with data item to indicate their periods of validity. We propose a model for temporal databases within the framework of the classical database theory. Our model is realized as a temporal parameterization of static relations. We do not impose any restrictions upon the schemes of temporal relations. The classical concepts of normal forms and dependencies are easily extended to our model, allowing a suitable design for a database scheme. We present a relational algebra and a tuple calculus for our model and prove their equivalence. Our data model is homogeneous in the sense that the periods of validity of all the attributes in a given tuple of a temporal relation are identical. We discuss how to relax the homogeneity requirement to extend the application domain of our approach.
For Correspondence: Computer Science Department, Iowa State University, Ames, IA 50011.
Update and Retrieval in a Relational Database Through a
Universal Schema Interface Volkert Brosda and gottfried Vossen
A database system that is based on the universal relation (UR) model aims at freeing its users from specifying access paths on both the physical and on the logical levels. All information about the logical structure of the database (i.e., its conceptual scheme) is hidden from users; they need only to know the attribute names, which now carry all the semantics of the database.
Previous work on UR interfaces has concentrated on the design and implementation of query languages that serve to facilitate retrieval of data from a relational database. On the other hand, updates are always handled as before, which means that users still have to know the logical structure of the database in case they want to insert, delete, or modify tuples.
In this paper the concepts underlying a UR interface, which is really "universal," are presented; it is based on the UR model, and it permits not only queries but also updates: Combinations of attributes that may participate in an update-operation ("objects") have to be specified during the design phase of the database, and are then embodied into the database scheme by an extended synthesis algorithm. They form the basis for any insertion or deletion operation. A precise definition of "insertable" tuples, and of the insert- and delete-operation in this new context, is given. It is then shown that these operations modify a database state in such a way that a representative instance always exists. This is accomplished by providing a more detailed version of Sagiv's uniqueness condition and by exploring the structure of nonunique objects. Since the underlying database always has a representative instance, this instance can be used to define the window function for retrieval. It is shown that it is still possible to compute windows by a union of minimal extensions joins.
For Correspondence: V. Brosda, Institut fur Informatick, TU Clausthal, Erzstrasse 1, D-3392 Clausthal-Zellerfeld, West Germany; G. Vossen, Lehrstuhl fur angewandte Mathematik, insbesondere Informatik, RWTH Aachen, Templergraben 64, D-5100 Aachen, West Germany.
A Simple Bounded Disorder File Organization with Good
Performance David B. Lomet
A bounded-disorder (BD) file is one in which data are ogranized into nodes that are indexed, e.g., by means of a B-tree. The data nodes are multibucket nodes that are accessed by hashing. In this paper we present two important improvements to the BD organization as originally described. First, records in a data node that overflow their designated primary bucket are stored in a single overflow bucket which is itself a bucket of the data node. Second, when file space needs to be increased, partial expansions are used that employ elastic buckets. Analysis and simulation results demonstrate that this variant of the BD organization has utilization, random access performance, and file growth performance that can be competitive with good extendible hashing methods, while supporting high-performance sequential access. The simplicity of the organization results in simple algorithms for realizing the organization.
For Correspondence: Digital Equipment Corporation, 110 Spit Brook Road, Nashua, NH 03062.
Properties and Update Semantics of Consistent Views Georg Gottlob, Paolo Paolini, and Roberto Zicari
The problem of translating view updates to database updates is considered. Both databases and views are modeled as data abstractions. A data abstraction consists of a set of states and of a set of primitive update operators representing state transition functions. It is shown how complex update programs can be built from primitive update operators and how view update programs can be built from primitive update operators and attention is paid to a class of views that we call "consistent." Loosely speaking, a consistent view is a view with the following property: If the effect of a view update program on a view state is determined, then the effect of the corresponding database update is unambiguously determined. Thus, in order to know how to translate a given view update into a database update, it is sufficient to be aware of a functional specification of such a program. We show that consistent views have a number of interesting properties with respect to the concurrency of (high-level) update transactions. Moreover we show that the class of consistent views includes as a subset the class of views that translate updates under maintenance of a constant complement. However, we show that there exist consistent views tht do not translate under constant complement. The results of Bancilhon and Spyratos are generalized in order to capture the update semantics of the entire class of consistent views. In particular we show that the class of consistent views is obtained if we relax the requirement of a constant complement by allowing the complement to decrease according to a suitable partial order.
For Correspondence: G. Gottlob, Institut for Applied Mathematics, C.N.R., Genoa, Italy and Department of Computer Science, Stanford University, Stanford, CA 94305; P. Paolini, Department of Electronics, Politecnico di Milano, Milan, Italy and A.R.G., Milan, Italy; and R. Zicari, Department of Electronics, Politecnico di Milano, Milan, Italy and Electrical Engineering and Computer Science Departments, University of California at Berkeley, CA 94720.
Transactions on Mathematical Software December 1988
MACHAR: A Subroutine to Dynamically Determine Machine
Parameters W.J. Cody
Numerical software written in high-level languages often relies on machine-dependent parameters to improve portability. MACHAR is an evolving FORTRAN subroutine for dynamically determining thirteen fundamental parameters associated with a floating-point arithmetic system. The version presented here operates correctly on a large number of different floating-point systems, including those implementing the new IEEE Floating-Point Standard.
For Correspondence: W. J. Cody, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL 60439-4844.
Solving Systems of Nonlinear Equations Using the Nonzero Value
of the Topological Degree Michael N. Vrahatis
Two algorithms are described here for the numerical solution of a system of nonlinear equations F(X) = [theta], where [theta] = (0, 0,..., 0) [epsilon]R.sup.n., and F is a given continuous mapping of a region D in R.sup.n into R.sup.n. The first algorithm locates at least one root of the system within an n-dimensional polyhedron, using the nonzero value of the topological degree of F at [theta] relative to the polyhedron; the second algorithm applies a new generalized bisection mthod in order to compute an approximate solution of the system. The size of the original n-dimension polyhedron is arbitrary, and the method is globally convergent in a residual sense.
These algorithms, in the various function evaluations, only make use of the algebraic sign of F and do not require computations of the totpological degree. Morevoer, they can be applied to nondifferetiable continuous functions F and do not involve derivatives of F or approximations of such derivatives.
For Correspondence: Department of Mathematics, White Hall, Cornell University, Ithaca, NY 14853.
CHABIS: A Mathematical Software Package for Locating and
Evaluating Roots of Systems of Nonlinear Equations Michael N. Vrahatis
CHABIS is a mathematical software package for the numerical solution of a system of n nonlinear equations in n variables. First, CHABIS locates at least one solution of the system within an n-dimensional polyhedron. Then, it applies a new generalized method of bisection to this n-polyhedron in order to obtain an approximate solution of the system according to a predetermined accuracy. In this paper we briefly describe the user interface to CHABIS and present several details of its implementation, as well as an example of its usage.
For Correspondence: Department of Mathematics, White Hall, Cornell Universtiy, ithaca, NY 14853.
An Algorithm for the Multiplication of Symmetric Polynomials John S. Garavelli
Although the cycle index polynomial for a permutation group can often be easily determined, expansion of the figure counting series in a Polya enumeration presents computational difficulties for object sets with higher degrees of symmetry and more than modest size. An algorithm that does not require algebraic symbol manipulation is derived for multiplying symmetric polynomials represented by partitions. Because the repetitive identification and collection of common terms are eliminated and storage requirements reduced, this algorithm is useful in rapidly expanding the figure counting series in such Polya enumeration problems as the counting of chemical isomers.
For Correspondence: Biomolecular Analysis Facility, College of Pharmacy (M/C 781), University of Illinois at Chicago, Box 6998, Chicago, IL 60680.
A Global Optimization Algorithm Using Stochastic Differential
Equations Filippo Aluffi-Pentini, Valerio Parisi, and Francesco Zirilli
SIGMA is a set of FORTRAN subprograms for solving the global optimization problem, which implements a method founded on the numerical solution of a Cauchy problem for a stochastic differential equation inspired by statistical mechanics.
This paper gives a detailed description of the method as implemented in SIGMA and reports the results obtained by SIGMA attacking, on two different computers, a set of 37 test problems which were proposed elsewhere by the present authors to test global optimization software.
The main conclusion is that SIGMA performs very well, solving 35 of the problems, including some very hard ones.
Unfortunately, the limited results available to us at present do not appear sufficient to enable a conclusive comparison with other global optimization methods.
For Correspondence: F. Aluffi-Pentini, Dipartimento di Metodi e Modelli Matematici per le Scienze Applicate, Universita di Roma, "La Sapienza," Via A. Scarpa 10, 00161, Roma, Italy; V. Parisi, Dipartimento di Fisica, 2.sup.a Universita di Roma, "Tor Vergata," Via Orazio Raimondo, La Romanina, 00173 Roma, Italy; F. Zirilli, Dipartimento di Matematica, Universita di Roma, "La Sapienza," Piazzale Aldo Moro, 2, 00185 Roma, Italy.
FORTRAN Codes for Estimating the One-Norm of a Real or
Complex Matrix, with Applications to Condition Estimation Nicholas J. Higham
FORTRAN 77 codes SONEST and CONEST are presented for estimating the 1-norm (or the [infinity]-norm) of a real or complex matrix, respectively. The codes are of wide applicability in condition estimation since explicit access to the matrix, A, is not required; instead, matrix-vector products Ax and A.sup.T.x are computed by the calling program via a reverse communication interface. The algorithms are based on a convex optimization method for estimating the 1-norm of a real matrix devised by Hager [Condition estimates. SIAM J. Sci. Stat. Comput. 5 (1984), 311-316]. We derive new results concerning the behavior of Hager's method, extend it to complex matrices, and make several algorithmic modifications in order to improve the reliability and efficiency.
For Correspondence: Department of Mathematics, University of Manchester, Manchester, M13 9PL, England.