bluuebunny/crossref_metadata_2025 huggingface dataset:
SEARCH FOR LOG-PERIODIC OSCILLATIONS IN STOCK MARKET SIMULATIONS
Authors: PANDEY RAS B. , STAUFFER DIETRICH
Published: July 2002

Using Chowdhury's simplification of the Cont–Bouchaud percolation algorithm, and including inertia (trading momentum) as well as a nonlinear restoring force (pricing pressure), we find spontaneous oscillations, which for suitable parameters have at first an exponentially increasing period. They seem to mimic the approximate log-periodic oscillations found by Johansen and Sornette in the Nikkei index after the burst of the Japanese bubble a decade ago.
FISH WARS ON THE HIGH SEAS: A STRADDLING STOCK COMPETITION MODEL
Authors: MCKELVEY ROBERT W. , SANDAL LEIF K. , STEINSHAMN STEIN I.
Published: July 2002

The post-World War II era saw the development of powerful self-contained fishing fleets, so-called distant-water fleets (DWFs), which roamed the world's oceans, seeking out rich harvesting targets and practicing pulse fishing. With the creation in the 1980s of coastal states' extended economic zones (EEZs), to manage fisheries out to 200 miles from the shore, it was hoped that the DWFs would close down. But the ranges of many important commercial fish stocks straddle the boundaries of several EEZs, and continue out into international waters. Thus, the consequence of creating the EEZs has been to encourage development of coastal countries' national fleets, while the DWFs continue to harvest in international waters.

Here, we model the fish war between a DWF and a regionally-based coalition of coastal states, operating out of their EEZs. The outcome is again a pulse fishery, but one which may be even more destructive than was the former situation, when the DWF was unopposed.

Finally we point out the relevance of the fish war model to the issue of creating effective multinational Regional Fisheries Management Organisations — a necessary step for achieving sustainable benefit from the harvest of the regional seas.
LEVEL OF DETAIL AND MULTI-RESOLUTION MODELING FOR VIRTUAL PROTOTYPING
Authors: PAN ZHIGENG , ZHANG MINGMIN , ZHOU KUN , CHENG CHIYI , SHI JIAOYING
Published: July 2002

Reconciling scene realism with interactivity has emerged as one of the most important areas in making virtual reality feasible for large-scale CAD data sets consisting of several millions of primitives. Level of detail (LoD) and multi-resolution modeling techniques in virtual reality can be used to speed up the process of virtual design and virtual prototyping. In this paper, we present an automatic LoD generation and rendering algorithm, which is suitable for CAD models and propose a new multi-resolution representation scheme called MRM (multi-resolution model), which can support efficient extraction of fixed resolution and variable resolution for multiple objects in the same scene. MRM scheme supports unified selective simplifications and selective refinements over the mesh. Furthermore, LoD and multi-resolution models may be used to support real-time geometric transmission in collaborative virtual design and prototyping.
TWO ALGORITHMS FOR COMPUTING THE EUCLIDEAN DISTANCE TRANSFORM
Authors: GAVRILOVA MARINA L. , ALSUWAIYEL MUHAMMAD H.
Published: July 2002

Given an n × n binary image of white and black pixels, we present two optimal algorithms for computing the distance transform and the nearest feature transform using the Euclidean metric. The first algorithm is a fast sequential algorithm that runs in linear time in the input size. The second is a parallel algorithm that runs in O(n2/p) time on a linear array of p processors, p, 1 ≤ p ≤ n.
NOISE REDUCTION IN TERAHERTZ THIN FILM MEASUREMENTS USING A DOUBLE MODULATED DIFFERENTIAL TECHNIQUE
Authors: MICKAN SAMUEL P. , ABBOTT DEREK , MUNCH JESPER , ZHANG X.-C.
Published: July 2002

Differential terahertz (THz) time-domain spectroscopy (TDS) is a technique for decreasing noise levels in THz thin film characterization experiments. Characterizing thin films in the GHz to THz range is critical for the development of fast integrated circuits and photonic systems, and is potentially applicable to biosensors and proteomics. This paper shows how the differential technique, combined with double modulation, enables the study of thin films with noise reduction over normal TDS that improves at the film gets thinner. Double modulated differential THz-TDS has enabled the characterization of films with less than 1-μm thickness.
STRESS CONCENTRATION DUE TO ADVANCING HEART PULSE THROUGH A BLOOD VESSEL JOINT
Authors: SELEZOV IGOR , AVRAMENKO OLGA , FRATAMICO GIUSEPPE , PALLOTTI GIOVANNI , PETTAZZONI PAOLO
Published: July 2002

The effect of a vessel joint of different properties on the heart pulse propagation and anastomosis junction is investigated. The system under consideration is modelled by an elastic piecewise-constant vessel consisting of two perfectly jointed vessels of different thicknesses and radii. A mathematical model is developed, to perform numerical calculations and to obtain some qualitative and quantitative estimations. The effect of different thicknesses and radii of jointed blood vessels on the concentrations of pressure, radial vessel wall displacement, bending moments and shear forces are analyzed in detail.
NEW RESULTS IN A SELF-ORGANIZED MODEL OF TECHNOLOGICAL EVOLUTION
Authors: ARENAS A. , DÍAZ-GUILERA A. , GUARDIOLA X. , LLAS M. , ORON G. , PÉREZ C. J. , VEGA-REDONDO F.
Published: July 2002

We present new results in a model of technological evolution which displays different macroscopic behaviors based on very simple microscopic rules of local interaction. The main features are criticality and self-organization. We give information about new scaling relation and study the roughness of the spatial technological profile. We verify that the performance is optimized in the critical region independently of the dynamical rules.
ACTION FOR SUSTAINABILITY: NORTHWEST ENGLAND'S TOOL FOR REGIONAL STRATEGIC SUSTAINABILITY APPRAISAL
Authors: JAMES PHILIP , DONALDSON STUART
Published: July 2002

A requirement of the UK Government's strategy for sustainable development, published in 1999, was that all English regions would produce a sustainability framework by the end of 2000. In the Northwest, the framework has been produced under the title Action for Sustainability.

The framework is addressed at a wide audience of strategists and key decision-makers, including elected members and those in the public, private and voluntary sectors. One of the framework's main uses is to be a tool for regional sustainability appraisal.

The work undertaken to produce the framework is described by one of those involved in the process. The published framework is evaluated using current concepts of sustainable development. The way in which the framework is already beginning to influence development in the Northwest is illustrated by two case studies involving appraisals of the Regional Planning Guidance and applications for funding from the Single Regeneration Budget.
NORN PREDICTOR — STOCK PREDICTION USING A NEURAL OSCILLATORY-BASED RECURRENT NETWORK
Authors: LEE RAYMOND S. T. , LIU JAMES N. K.
Published: July 2002

Financial prediction is one of the most typical applications in contemporary scientific study. In this paper, we present a fully integrated stock prediction system – NORN Predictor – a Neural Oscillatory-based Recurrent Network for finance prediction system to provide both a) long-term trend prediction, and b) short-term stock price prediction. One of the major characteristics of the proposed system is the automation of the conventional financial technical analysis technique such as market pattern analysis via the NOEGM (Neural Oscillatory-based Elastic Graph Matching) model and its integration with the Time-difference recurrent neural network models. This will provide a fully integrated and automated tool for analysis and investigation of stock investment. From the implementation point of view, the stock pricing information of 33 major Hong Kong stocks in the period from 1990 to 1999 is being adopted for system training and evaluation. As compared with the contemporary neural prediction model, the proposed system has achieved challenging results in terms of efficiency and accuracy.
Superimposing encrypted data
Authors: Yu K. W. , Yu Tong Lai
Published: July 2002

Much has been written about the necessity of processing data in the encrypted form. However, no satisfactory method of processing encrypted data has been published to date. Ahitub et al. [2] have analyzed the possibilities of using some special algorithms to add encrypted data. Rivest et al. [10] have suggested the use of an algorithm based on homomorphic functions for processing encrypted data. The main limitation of this algorithm is that such functions can be broken by solving a set of linear equations, as noted by [2]. The public-key crytosystem described in [11] can be used to multiply encrypted data but cannot be used to add encrypted data and is therefore not appropriate for some practical applications such as bank transactions. Abadi, Feigenbaum and Kilian [1] presented some general theorems concerning the problem of computing with encrypted data and formulated a framework to prove precise statements about what an encrypted instance hides and reveals; they also described encryption schemes for some well-known functions.
Computing perspectives
Authors: Wilkes Maurice V.
Published: July 2002

Engineering could not exist without mathematics and experimental science. Mathematics deals in pure thought and experimental science is concerned with the laws of nature. Within the same framework, it may be said that the aim of engineering is to secure control over nature. In some branches of engineering the dependence is very clear. Where, for example, would heat engines be without thermodynamics, radio antenna design without electromagnetic theory, or communications without Fourier analysis? It has long been accepted that the training of an engineer should include a serious study of mathematics and the relevant science, whatever use he or she may subsequently make of this learning.
On robust transaction routing and load sharing
Authors: Yu Philip S. , Leff Avraham , Lee Yann-Hang
Published: July 2002

In this paper we examine the issue of robust transaction routing in a locally distributed database environment where transaction characteristics such as reference locality imply that certain processing systems can be identified as being more suitable than others for a given transaction class. A response time based routing strategy can strike a balance between indiscriminate sharing of the load and routing based only on transaction affinity. Since response time estimates depend on workload and system parameters that may not be readily available, it is important to examine the robustness of routing decisions to information accuracy. We find that a strategy which strictly tries to minimize the response time of incoming transactions is sensitive to the accuracy of certain parameter values. On the other hand, naive strategies, that simply ignore the parameters in making routing decisions, have even worse performance. Three alternative strategies are therefore examined: threshold, discriminatory, and adaptive. Instead of just optimizing an incoming transaction's response time, the first two strategies pursue a strategy that is somewhat more oriented towards global optimization. This is achieved by being more restrictive on either the condition or the candidate for balancing the load. The third strategy, while trying to minimize the response time of individual incoming transactions, employs a feedback process to adaptively adjust future response time estimates. It monitors the discrepancy between the actual and estimated response times and introduces a correction factor based on regression analysis. All three strategies are shown to be robust with respect to the accuracy of workload and system parameters used in the response time estimation.
A software tool for modular database design
Authors: Casanova M. A. , Furtado A. L. , Tucherman L.
Published: July 2002

A modularization discipline for database schemas is first described. The dicipline incorporates both a strategy for enforcing integrity constraints and a tactic for organizing large sets of database structures, integrity constraints, and operations. A software tool that helps the development and maintenance of database schemas modularized according to the discipline is then presented. It offers a user-friendly interface that guides the designer through the various stages of the creation of a new module or through the process of changing objects of existing modules. The tool incorporates, in a declarative style, a description of the design and redesign rules behind the modularization discipline, hence facilitating the incremental addition of new expertise about database design.
The 21st ACM North American computer chess championship
Authors: Newborn Monty , Kopec Danny
Published: July 2002

After twenty years of traveling from city to city across the United States, the ACM North American Computer Chess Championship came back to the place of its birth, the New York Hilton Hotel, where the competitions began in 1970. This latest five-round event ended in a two-way tie for first place between MEPHISTO and DEEP THOUGHT/88. Finishing in a two-way tie for third place were HITECH and M CHESS. A total of 10 teams participated, and the level of play was at the low grandmaster level. A special three-round end-game championship was won by MEPHISTO, who also captured the prize for the best Small Computing System. A total of $8000 in prizes was divided up among the winners.
A Four Russians algorithm for regular expression pattern matching
Authors: Myers Gene
Published: July 2002

Given a regular expression
R
of length
P
and a word
A
of length
N
, the membership problem is to determine if
A
is in the language denoted by
R
. An
O
(
PN
/lg
N
) time algorithm is presented that is based on a lg
N
speedup of the standard
O
(
PN
) time simulation of
R
's nonderministic finite automaton on
A
using a combination of the node-listing and “Four-Russians” paradigms. This result places a new worst-case upper bound on regular expression pattern matching. Moreover, in practice the method provides an implementation that is faster than existing software for small regular expressions.
A portable code generator for CRAY FORTRAN
Authors: Weerawarana Sanjiva , Wang Paul S.
Published: July 2002

One way to combine the powers of symbolic computing with numeric computing is to automaticaly derive and produce numeric code. This approach has important applications in science and engineering. Once the desired formulas and procedures are derived in a symbolic manipulation system, they can be translated into a target numeric language by a
code generator
. GENCRAY is a code generator written in the C language for portability. GENCRAY defines a LISP-style input language that is translated into either FORTRAN 77 or CRAY FORTRAN. By defining its own input syntax, GENCRAY becomes a free-standing code translator that can be made to work with any symbolic manipulation system. GENCRAY is portable to any computer system with a standard C compiler. Input to GENCRAY can come from a file or directly from a symbolic system through a pipe. On UNIX systems with Berkeley networking, GENCRAY also runs as a network server. The input syntax is customizable to allow both Common and Franz LISP input styles. In addition to generating easily vectorizable CRAY FORTRAN code, GENCRAY also provides high-level, easy-to-use parallel programming macros to produce parallel code for the multiprocessor CRAY systems. The features, applications, usage, and implementation of GENCRAY are described. Techniques for producing parallel codes are discussed and illustrated by a substantial example contained in the Appendix.
An implementation of a divide and conquer algorithm for the unitary eigen problem
Authors: Ammar G. S. , Reichel L. , Sorensen D. C.
Published: July 2002

We present a FORTRAN implementation of a divide-and-conquer method for computing the spectral resolution of a unitary upper Hessenberg matrix
H
. Any such matrix
H
of order
n
, normalized so that its subdiagonal elements are nonnegative, can be written as a product of
n
-1* Givens matrices and a diagonal matrix. This representation, which we refer to as the
Schur parametric form of H
, arises naturally in applications such as in signal processing and in the computation of Gauss-Szego quadrature rules. Our programs utilize the Schur parametrization to compute the spectral decomposition of
H
without explicitly forming the elements of
H
. If only the eigenvalues and first components of the eigenvectors are desired, as in the applications mentioned above, the algorithm requires only

O(n
2
)

arithmetic operations. Experimental results presented indicate that the algorithm is reliable and competitive with the general QR algorithm applied to this problem. Moreover, the algorithm can be easily adapted for parallel implementation.—
Authors' Abstract
LSNNO, a FORTRAN subroutine for solving large-scale nonlinear network optimization problems
Authors: Toint Ph. L. , Tuyttens D.
Published: July 2002

The implementation and testing of LSNNO, a new FORTRAN subroutine for solving large-scale nonlinear network optimization problems is described. The implemented algorithm applies the concepts of partial separability and partitioned quasi-Newton updating to high-dimensional nonlinear network optimization problems. Some numerical results on both academic and practical problems are reported.
Automatic generation of production rules for integrity maintenance
Authors: Ceri Stefano , Fraternali Piero , Paraboschi Stefano , Tanca Letizia
Published: July 2002

In this article we present an approach to integrity maintenance, consisting of automatically generating production rules for integrity enforcement. Constraints are expressed as particular formulas of Domain Relational Calculus; they are automatically translated into a set of repair actions, encoded as production rules of an active database system. Production rules may be redundant (they enforce the same constraint in different ways) and conflicting (because repairing one constraint may cause the violation of another constraint). Thus, it is necessary to develop techniques for analyzing the properties of the set of active rules and for ensuring that any computation of production rules after any incorrect transaction terminates and produces a consistent database state.

Along these guidelines, we describe a specific architecture for constraint definition and enforcement. The components of the architecture include a
Rule Generator
, for producing all possible repair actions, and a
Rule Analyzer and Selector
, for producing a collection of production rules such that their execution after an incorrect transaction always terminates in a consistent state (possibly by rolling back the transaction); moreover, the needs of applications are modeled, so that integrity-enforcing rules reach the final state that better represents the original intentions of the transaction's supplier. Specific input from the designer can also drive the process and integrate or modify the rules generated automatically by the method. Experimental results of a prototype implementation of the proposed architecture are also described.
Structure and chance
Authors: Burnell Lisa , Horvitz Eric
Published: July 2002

Software errors abound in the world of computing. Sophisticated computer programs rank high on the list of the most complex systems ever created by humankind. The complexity of a program or a set of interacting programs makes it extremely difficult to perform offline verification of run-time behavior. Thus, the creation and maintenance of program code is often linked to a process of incremental refinement and ongoing detection and correction of errors. To be sure, the detection and repair of program errors is an inescapable part of the process of software development. However, run-time software errors may be discovered in fielded applications days, months, or even years after the software was last modified—especially in applications composed of a plethora of separate programs created and updated by different people at different times. In such complex applications, software errors are revealed through the run-time interaction of hundreds of distinct processes competing for limited memory and CPU resources. Software developers and support engineers responsible for correcting software problems face difficult challenges in tracking down the source of run-time errors in complex applications. The information made available to engineers about the nature of a failure often leaves open a wide range of possibilities that must be sifted through carefully in searching for an underlying error.
Generating testing and analysis tools with Aria
Authors: Devanbu Premkumar T. , Rosenblum David S. , Wolf Alexander L.
Published: July 2002

Many software testing and analysis tools manipulate graph representations of programs, such as abstract syntax trees or abstract semantics graphs. Handcrafting such tools in conventional programming languages can be difficult, error prone, and time consuming. Our approach is to use application generators targeted for the domain of graph-representation-based testing and analysis tools. Moreover, we generate the generators themselves, so that the development of tools based on different languages and/or representations can also be supported better. In this article we report on our experiences in developing and using a system called Aria that generates testing and analysis tools based on an abstract semantics graph representation for C and C++ called Reprise. Aria itself was generated by the Genoa system. We demonstrate the utility of Aria and, thereby, the power of our approach, by showing Aria's use in the development of a number of useful testing and analysis tools.
Optimal reconfiguration strategy for a degradable multimodule computing system
Authors: Lee Yann-Hang , Shin Kang G.
Published: July 2002

A new quantitative approach to the problem of reconfiguring a degradable multimodule system is presented. The approach is concerned with both assigning some modules for computation and arranging others for reliability. Conventionally, a fault-tolerant system performs reconfiguration only upon a subsystem failure. Since there exists an inherent trade-off between the computation capacity and fault tolerance of a multimodule computing system, the conventional approach is a
passive
action and does not yield a configuration that provides an optimal compromise for the trade-off. By using the expected total reward as the optimal criterion, the need and existence of an
active
reconfiguration strategy, in which the system reconfigures itself on the basis of not only the
occurrence of a failure
but also the
progression of the mission
, are shown.

Following the problem formulation, some important properties of an optimal reconfiguration strategy, which specify (i) the times at which the system should undergo reconfiguration and (ii) the configurations to which the system should change, are investigated. Then, the optimal reconfiguration problem is converted to integer nonlinear knapsack and fractional programming problems. The algorithms for solving these problems and a demonstrative example are given. Extensions of the optimal reconfiguration problem are also discussed.
Linear probing with a nonuniform address distribution
Authors: Pflug Georg Ch. , Kessler Hans W.
Published: July 2002

This paper presents a new approach to the analysis of hashing with linear probing for nonuniformly distributed hashed keys. The use of urn models is avoided. Instead, some facts about empirical processes, which are well known in statistics are used. In particular, an asymptotic formula for the expected probe length for both a successful and an unsuccessful search is obtained. The accuracy of the approximation is confirmed by simulation.
Transistor reordering for power minimization under delay constraint
Authors: Prasad S. C. , Roy K.
Published: July 2002

In this article we address the problem of optimization of VLSI circuits to minimize power consumption while meeting performance goals. We present a method of estimating power consumption of a basic or complex CMOS gate which takes the internal capacitances of the gate into account. This method is used to select an ordering of series-connected transistors found in CMOS gates to achieve lower power consumption. The method is very efficient when used by library-based design styles. We describe a multipass algorithm that makes use of transistor reordering to optimize performance and power consumption of circuits, has a linear time complexity per pass, and converges to a solution in a small number of passes. Transformations in addition to transistor reordering can be used by the algorithm. The algorithm has been benchmarked on several large examples and the results are presented.
The partial-occlusion effect
Authors: Zhai Shumin , Buxton William , Milgram Paul
Published: July 2002

This study investigates human performance when using semitransparent tools in interactive 3D computer graphics environments. The article briefly reviews techniques for presenting depth information and examples of applying semitransparency in computer interface design. We hypothesize that when the user moves a semitransparent surface in a 3D environment, the “partial-occlusion” effect introduced through semitransparency acts as an effective cue in target localization—an essential component in many 3D interaction tasks. This hypothesis was tested in an experiment in which subjects were asked to capture dynamic targets (virtual fish) with two versions of a 3D box cursor, one with and one without semitransparent surfaces. Results showed that the partial-occlusion effect through semitransparency significantly improved users' performance in terms of trial completion time, error rate, and error magnitude in both monoscopic and stereoscopic displays. Subjective evaluations supported the conclusions drawn from performance measures. The experimental results and their implications are discussed, with emphasis on the relative, discrete nature of the partial-occlusion effect and on interactions between different depth cues. The article concludes with proposals of a few future research issues and applications of semitransparency in human-computer interaction.
A fast algorithm for minimizing FPGA combinational and sequential modules
Authors: Kagaris Dimitrios , Tragoudas Spyros
Published: July 2002

We present a quadratic-time algorithm for minimizing the number of modules in an FPGA with combinational and sequential modules (like the C-modules and S-modules of the ACT2 and ACT3 architectures). The constraint is that a combinational module can be combined with one flip-flop in a single sequential module, only if the combinational module drives no other combinational modules. Our algorithm uses a minimum-cost flow formulation to solve the problem with a significant time improvement over a previous approach that used a general linear program.
The model-assisted global query system for multiple databases in distributed enterprises
Authors: Cheung Waiman , Hsu Cheng
Published: July 2002

Today's enterprises typically employ multiple information systems, which are independently developed, locally administered, and different in logical or physical designs. Therefore, a fundamental challenge in enterprise information management is the sharing of information for enterprise users across organizational boundaries; this requires a global query system capable of providing on-line intelligent assistance to users. Conventional technologies, such as schema-based query languages and hard-coded schema integration, are not sufficient to solve this problem. This article develops a new approach, a “model-assisted global query system,” that utilizes an on-line repository of enterprise metadata—the Metadatabase—to facilitate global query formulation and processing with certain desirable properties such as adaptiveness and open-systems architecture. A definitional model characterizing the various classes and roles of the required metadata as knowledge for the system is presented. The significance of possessing this knowledge (via a Metadatabase) toward improving the global query capabilities available previously is analyzed. On this basis, a direct method using model traversal and a query language using global model constructs are developed along with other new methods required for this approach. It is then tested through a prototype system in a computer-integrated manufacturing (CIM) setting.
Boundary-valued shape-preserving interpolating splines
Authors: Costantini P.
Published: July 2002

This article describes a general-purpose method for computing interpolating polynomial splines with arbitrary constraints on their shape and satisfying separable or nonseparable boundary conditions. Examples of applications of the related Fortran code are periodic shape-preserving spline intepolation and the construction of visually pleasing closed curves.
Statistical independence properties of inversive pseudorandom vectors over parts of the period
Authors: Emmerich Frank
Published: July 2002

This article deals with the inversive method for generating uniform pseudorandom vectors. Statistical independence properties of the generated pseudorandom vector sequences over parts of the period are considered based on the discrete discrepancy of corresponding point sets. An upper bound for the average value of these discrete discrepancies is established.
Managing inconsistent specifications
Authors: Hunter Anthony , Nuseibeh Bashar
Published: July 2002

In previous work, we advocated continued development of specifications in the presence of inconsistency. To support this, we used classical logic to represent partial specifications and to identify inconsistencies between them. We now present an adaptation of classical logic, which we term quasi-classical (QC) logic, that allows continued reasoning in the presence of inconsistency. The adaptation is a weakening of classical logic that prohibits all trivial derivations, but still allows all resolvants of the assumptions to be derived. Furthermore, the connectives behave in a classical manner. We then present a development called labeled QC logic that records and tracks assumptions used in reasoning. This facilitates a logical analysis of inconsistent information. We discuss that application of labeled QC logic in the analysis of multiperspective specifications. Such specifications are developed by multiple particpants who hold overlapping, often inconsistent, views of the systems they are developing.
A metamodel of information flow: a tool to support information systems theory
Authors: Ahituv Niv
Published: July 2002

In this paper an axiomatic, fundamental metamodel of data flow is constructed. The components of the metamodel are the states along the flow of data: physical events, language (data), stored data, human data processing, and decision making. Transfers from one state to another are performed by functions: coding, keying, processing, perceptions, and human acting. The entire flow is evaluated by a value function. Each of the states and functions is rigorously described by means of definitions, axioms, and theorems. The main purpose of the metamodel is to provide a common framework for various models in MIS and consequently to remedy the "Tower of Babel" syndrome prevailing in this area. The way the metamodel can be used to develop other models in MIS is explained in the last part of the paper.
A normal form for relational databases that is based on domains and keys
Authors: Fagin Ronald
Published: July 2002

A new normal form for relational databases, called domain-key normal form (DK/NF), is defined. Also, formal definitions of insertion anomaly and deletion anomaly are presented. It is shown that a schema is in DK/NF if and only if it has no insertion or deletion anomalies. Unlike previously defined normal forms, DK/NF is not defined in terms of traditional dependencies (functional, multivalued, or join). Instead, it is defined in terms of the more primitive concepts of domain and key, along with the general concept of a “constraint.” We also consider how the definitions of traditional normal forms might be modified by taking into consideration, for the first time, the combinatorial consequences of bounded domain sizes. It is shown that after this modification, these traditional normal forms are all implied by DK/NF. In particular, if all domains are infinite, then these traditional normal forms are all implied by DK/NF.
View indexing in relational databases
Authors: Roussopoulos Nicholas
Published: July 2002

The design and maintenance of a useful database system require efficient optimization of the logical access paths which demonstrate repetitive usage patterns. Views (classes of queries given by a query model) are an appropriate intermediate logical representation for database. Frequently accessed views of databases need to be supported by indexing to enhance retrieval. This paper investigates the problem of selecting an optimal index set of views and describes an efficient algorithm for this selection.
On optimizing an SQL-like nested query
Authors: Kim Won
Published: July 2002

SQL is a high-level nonprocedural data language which has received wide recognition in relational databases. One of the most interesting features of SQL is the nesting of query blocks to an arbitrary depth. An SQL-like query nested to an arbitrary depth is shown to be composed of five basic types of nesting. Four of them have not been well understood and more work needs to be done to improve their execution efficiency. Algorithms are developed that transform queries involving these basic types of nesting into semantically equivalent queries that are amenable to efficient processing by existing query-processing subsystems. These algorithms are then combined into a coherent strategy for processing a general nested query of arbitrary complexity.
Efficient optimization of a class of relational expressions
Authors: Aho A. V. , Sagiv Y. , Ullman J. D.
Published: July 2002

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.
A locking protocol for resource coordination in distributed databases
Authors: Menasce Daniel A. , Popek Gerald J. , Muntz Richard R.
Published: July 2002

A locking protocol to coordinate access to a distributed database and to maintain system consistency throughout normal and abnormal conditions is presented. The proposed protocol is robust in the face of crashes of any participating site, as well as communication failures. Recovery from any number of failures during normal operation or any of the recovery stages is supported. Recovery is done in such a way that maximum forward progress is achieved by the recovery procedures. Integration of virtually any locking discipline including predicate lock methods is permitted by this protocol. The locking algorithm operates, and operates correctly, when the network is partitioned, either intentionally or by failure of communication lines. Each partition is able to continue with work local to it, and operation merges gracefully when the partitions are reconnected.

A subroutine of the protocol, that assures reliable communication among sites, is shown to have better performance than two-phase commit methods. For many topologies of interest, the delay introduced by the overall protocol is not a direct function of the size of the network. The communications cost is shown to grow in a relatively slow, linear fashion with the number of sites participating in the transaction. An informal proof of the correctness of the algorithm is also presented in this paper.

The algorithm has as its core a centralized locking protocol with distributed recovery procedures. A centralized controller with local appendages at each site coordinates all resource control, with requests initiated by application programs at any site. However, no site experiences undue load. Recovery is broken down into three disjoint mechanisms: for single node recovery, merge of partitions, and reconstruction of the centralized controller and tables. The disjointness of the mechanisms contributes to comprehensibility and ease of proof.

The paper concludes with a proposal for an extension aimed at optimizing operation of the algorithm to adapt to highly skewed distributions of activity. The extension applies nicely to interconnected computer networks.
Implementing a generalized access path structure for a relational database system
Authors: Haerder Theo
Published: July 2002

A new kind of implementation technique for access paths connecting sets of tuples qualified by attribute values is described. It combines the advantages of pointer chain and multilevel index implementation techniques. Compared to these structures the generalized access path structure is at least competitive in performing retrieval and update operations, while a considerable storage space saving is gained. Some additional features of this structure support
m
-way joins and the evaluation of multirelation queries, and allow efficient checks of integrity assertions and simple reorganization schemes.
Synthesizing third normal form relations from functional dependencies
Authors: Bernstein Philip A.
Published: July 2002

It has been proposed that the description of a relational database can be formulated as a set of functional relationships among database attributes. These functional relationships can then be used to synthesize algorithmically a relational scheme. It is the purpose of this paper to present an effective procedure for performing such a synthesis. The schema that results from this procedure is proved to be in Codd's third normal form and to contain the fewest possible number of relations. Problems with earlier attempts to construct such a procedure are also discussed.
An attribute based model for database access cost analysis
Authors: Yao S. B.
Published: July 2002

A generalized model for physical database organizations is presented. Existing database organizations are shown to fit easily into the model as special cases. Generalized access algorithms and cost equations associated with the model are developed and analyzed. The model provides a general design framework in which the distinguishing properties of database organizations are made explicit and their performances can be compared.
The determination of efficient record segmentations and blocking factors for shared data files
Authors: March Salvatore T. , Serverance Dennis G.
Published: July 2002

It is generally believed that 80 percent of all retrieval from a commercial database is directed at only 20 percent of the stored data items. By partitioning data items into primary and secondary record segments, storing them in physically separate files, and judiciously allocating available buffer space to the two files, it is possible to significantly reduce the average cost of information retrieval from a shared database. An analytic model, based upon knowledge of data item lengths, data access costs, and user retrieval patterns, is developed to assist an analyst with this assignment problem. A computationally tractable design algorithm is presented and results of its application are described.
A Note on Yen's Algorithm for Finding the Length of All Shortest Paths in
N
-Node Nonnegative-Distance Networks
Authors: Williams Thomas A. , White Gregory P.
Published: July 2002

An error in Yen's algorithm is pointed out, and an alternative is offered which will produce correct results.
Simulating Stable Stochastic Systems, II: Markov Chains
Authors: Crane Michael A. , Iglehart Donald L.
Published: July 2002

A technique for simulating GI/G/s queues is shown to apply to simulations of discrete and continuous-time Markov chains. It is possible to address questions of simulation run duration and of starting and stopping simulations because of the existence of a random grouping of observations which produces independent identically distributed blocks from the start of the simulation. This grouping allows confidence intervals to be obtained for a general function of the steady-state distribution of the Markov chain. The technique is illustrated with simulation of an (
s, S
) inventory model in discrete time and the classical repairman problem in continuous time. Consideration is also given to determining system sensitivity to errors and uncertainty in the input parameters.
Verifying Program Performance
Authors: Wegbreit Ben
Published: July 2002

It is shown that specifications of program performance can be formally verified. Formal verification techniques, in particular, the method of inductive assertions, can be adapted to show that a program's maximum or mean execution time is correctly described by specifications supplied with the program. To formally establish the mean execution time, branching probabilities are expressed using inductive assertions which involve probability distributions. Verification conditions are formed and proved which establish that if the input distribution is correctly described by the input specifications, then the inductive assertions correctly describe the probability distributions of the data during execution. Once the inductive assertions are shown to be correct, branching probabilities are obtained and mean computation time is computed.
Indexing large metric spaces for similarity search queries
Authors: Bozkaya Tolga , Ozsoyoglu Meral
Published: July 2002

One of the common queries in many database applications is finding approximate matches to a given query item from a collection of data items. For example, given an image database, one may want to retrieve all images that are similar to a given query image. Distance-based index structures are proposed for applications where the distance computations between objects of the data domain are expensive (such as high-dimensional data) and the distance function is metric. In this paper we consider using distance-based index structures for similarity queries on large metric spaces. We elaborate on the approach that uses reference points (vantage points) to partition the data space into spherical shell-like regions in a hierarchical manner. We introduce the multivantage point tree structure (mvp-tree) that uses more than one vantage point to partiton the space into spherical cuts at each level. In answering similarity-based queries, the mvp-tree also utilizes the precomputed (at construction time) distances between the data points and the vantage points.

We summarize the experiments comparing mvp-trees to vp-trees that have a similar partitioning strategy, but use only one vantage point at each level and do not make use of the precomputed distances. Empirical studies show that the mvp-tree outperforms the vp-tree by 20% to 80% for varying query ranges and different distance distributions. Next, we generalize the idea of using multiple vantage points and discuss the results of experiments we have made to see how varying the number of vantage points in a node affects affects performance and how much is gained in performance by making use of precomputed distances. The results show that, after all, it may be best to use a large number of vantage points in an internal node in order to end up with a single directory node and keep as many of the precomputed distances as possible to provide more efficient filtering during search operations. Finally, we provide some experimental results that compare mvp-trees with M-trees, which is a dynamic distance-based index structure for metric domains.
Timing-driven routing for symmetrical array-based FPGAs
Authors: Chang Yao-Wen , Zhu Kai , Wong D. F.
Published: July 2002

In this paper we present a timing-driven router for symmetrical array-based FPGAs. The routing resources in the FPGAs consist of segments of various lengths. Researchers have shown that the number of segments, instead of wirelength, used by a net is the most critical factor in controlling routing delay in an FPGA. Thus, the traditional measure of routing delay on the basis of geometric distance of a signal is not accurate. To consider wirelength and delay simultaneously, we study a model of timing-driven routing rees, arising from the special properties of FPGA routing architectures. Based on the solutions to the routing-tree problem, we present a routing algorithm that is able to utilize various routing segments with global considerations to meet timing constraints. Experimental results show that our approach is very effective in reducing timing violations.
Using a coordination language to specify and analyze systems containing mobile components
Authors: Ciancarini P. , Franzé F. , Mascolo C.
Published: July 2002

New computing paradigms for network-aware applications need specification languages able to deal with the features of mobile code-based systems. A coordination language provides a formal framework in which the interaction of active entities can be expressed. A coordination language deals with the creation and destruction of code or complex agents, their communication activites, as well as their distribution and mobility in space. We show how the coordination language PoliS offers a flexible basis for the description and the automatic analysis of architectures of systems including mobile entities. Polis is based on multiple tuple spaces and offers a basis for defining, studying, and controlling mobility as it allows decoupling mobile entities from their environments both in space and in time. The pattern-matching mechanism adopted for communication helps in abstracting from addressing issues. We have developed a model-checking technique for the automatic analysis of PoliS specifications. In the article we show how this technique can be applied to mobile code-based systems
Programmed error correction on a decimal computer
Authors: Weinberg G. M.
Published: July 2002

In a previous paper [1], B. Dimsdale and I reported on the use of programmed Hamming codes for error correction on a 7090. The paper generated much interest, but several readers remarked that they could not use the technique on their decimal machines since they could not manipulate the bit structure of the characters. This paper presents a modification of Hamming's technique to adapt it to such machines. It generalizes to any number base for which addition is built into the machine, and so could be used for alphabetic error correction on a machine where such operations as (
A
+
B
, literally) or (
R
+2, literally) or (
H
+ $, literally) are unequivocally defined. The technique will be described for single strings of characters, but may be generalized to parallel techniques if parallel, no-carry addition is available on the machine in question.
Mechanization of tedious algebra—the
e
coefficients of theoretical chemistry
Authors: Wactlar H. D. , Barnett M. P.
Published: July 2002

A table of formulas for certain integrals involving Legendre functions has been constructed mechanically by a program which performed algebraic operations. The formulas are all rational algebraic expressions in a single variable and were constructed by a recurrence procedure. They are of interest in molecular quantum chemistry. Trivial coding techniques were used to write the relevant programs in FORTRAN. The results were photocomposed on a Photon S-560 system, that was controlled by tapes which were punched directly from the computer output, so avoiding manual keyboarding, transcription errors and keyboarded correction.