bluuebunny/crossref_metadata_2025 huggingface dataset:
AN OPPORTUNITY-BASED AGE REPLACEMENT POLICY CONSIDERING WARRANTY
Authors: ISKANDAR BERMAWI P. , SANDOH HIROAKI
Published: July 2002

This study discusses an opportunity-based age replacement policy for a system which has a warranty period (0, S]. When the system fails at its age x≤S, a minimal repair is performed. If an opportunity occurs to the system at its age x for S<x<T, we take the opportunity with probability p to preventively replace the system, while we conduct a corrective replacement when it fails on (S, T). Finally if its age reaches T, we execute a preventive replacement. Under this replacement policy, the design variable is T. For the case where opportunities occur according to a Poisson process, a long-run average cost of this policy is formulated under a general failure time distribution. It is, then, shown that one of the sufficient conditions where a unique finite optimal T* exists is that the failure time distribution is IFR (Increasing Failure Rate). Numerical examples are also presented for the Weibull failure time distribution.
AN EMPIRICAL STUDY OF TWO CLASSES OF ESTIMATORS FOR PROCESS VARIATION TRANSMISSION
Authors: FONG DANIEL Y. T.
Published: July 2002

Manufacturing processes often consist of a number of sequential stages. Of interest is to control the variation in one or more quality characteristics of a production unit at the final stage. By understanding how variation is transmitted and added across the stages, remedial actions in reducing variation at the final stage can be properly planned. With one quality characteristic measured at each stage, a set of naive estimators is previously proposed and shown to perform indistinguishably well with maximum likelihood estimators. Thus naive estimators are more convenient than maximum likelihood estimators as the former exist in closed form while the latter do not. This article considers situations when more than one quality characteristic is measured throughout the stages. Methods of analyzing variation transmission are briefly reviewed and the finite sample properties of naive and maximum likelihood estimators for multivariate measurements are further examined. A broad conclusion is that for moderate number of production units, naive estimators have smaller bias and variability. Furthermore, "proper" naive estimates provide more accurate interval estimates at a given confidence level. Finally, a set of piston-machining data is used for illustration.
THEORETICAL STUDY OF Si and N ADSORPTION ON THE Si-TERMINATED SiC(001) SURFACE
Authors: PIZZAGALLI L. , CATELLANI A. , GALLI G. , GYGI F. , BARATOFF A.
Published: July 2002

We report the results of first principles molecular dynamics simulations of the adsorption of Si and N atoms on a Si-terminated p(2×1) SiC(001) surface. In particular, we discuss different structural models for the Si-rich (3×2) surface, and the adsorption of 1/8, 1/2 and 1 monolayer nitrogen on the p(2×1) surface. Our simulations show that a SiC(001)-p(2×1) surface covered by a nitrogen monolayer is an inert substrate which inhibits growth.
TRAUMATIC DISRUPTION OF A FIBROCARTILAGE LUNATE-TRIQUETRAL COALITION — A CASE REPORT AND REVIEW OF THE LITERATURE
Authors: van Schoonhoven J. , Prommersberger K.-J. , Schmitt R.
Published: July 2002

Whilst osseous coalitions of the lunate and the triquetrum are known to be asymptomatic, fibrocartilage lunate-triquetral coalitions can present an uncommon cause for ulnar-sided wrist pain. To diagnose this condition a high degree of suspicion is needed. We present a case with painful post-traumatic disruption of a fibrocartilage lunate-triquetral coalition that was primary misdiagnosed to be a disruption of the interosseous lunotriquetral ligament and was initially treated arthroscopically. Persistent symptoms lead to X-ray examination of the opposite wrist, revealing a complete osseous lunate-triquetral coalition. CT and MRI investigations demonstrated the fibrocartilage coalition of the affected wrist. Subsequently, lunotriquetral fusion using a cannulated Herbert screw was performed and settled the symptoms completely.
Introducing Cases in the Asian Classroom: Initiatives in Response to the Challenges
Authors: Delios Andrew , Makino Shige
Published: July 2002

This paper proposes several means to overcome typical challenges encountered when teaching cases in conventional Asian undergraduate classes. The principal challenges are: students' respect for the instructor, students' reticence in speaking, students' strong grade orientation, and students' difficulties in dealing with ambiguity. To address these challenges, this paper proposes four classroom-based initiatives that concern classroom activities or course design aspects of a case-based course. We propose that the incorporation of the four initiatives in the course design helps to address the four challenges. We hope that the paper will stimulate discussion on the means to address these four and other challenges, and promote the sharing of other classroom activities or course designs.
A DIFFUSION APPROACH TO ECONOMIC TIME SERIES
Authors: CIOGLI M. , ROTUNDO G. , TIROZZI B.
Published: July 2002

A diffusion equation for the price evolution of the Italian share "Olivetti" is found by investigating a series of its data. The coefficients of this equation are found by using the maximum likelihood method based on martingale theory. We evaluate pricing and hedging strategy by the Sornette and Bouchaud approach.
THE LIMITATIONS OF NO-ARBITRAGE ARGUMENTS FOR REAL OPTIONS
Authors: HUBALEK F. , SCHACHERMAYER W.
Published: July 2002

We consider an option c which is contingent on an underlying [Formula: see text] that is not a traded asset. This situation typically arises in the context of real options. We investigate the situation when there is a "surrogate" traded asset S whose price process is highly correlated with that of [Formula: see text]. An illustration would be the cases where S and [Formula: see text] model two different brands of crude oil. The main result of the paper shows that in this case one cannot draw any non-trivial conclusions on the price of the option by only using no-arbitrage arguments.

In a second step we try to isolate hedging strategies on the traded asset S which minimize the variance of the hedging error. We show in particular, that the naive strategy of simply replacing [Formula: see text] by S fails to be optimal and we are able to quantify how far it is from being optimal.
STOCHASTIC DILATION OF A QUANTUM DYNAMICAL SEMIGROUP ON A SEPARABLE UNITAL C* ALGEBRA
Authors: GOSWAMI DEBASHISH , PAL ARUP KUMAR , SINHA KALYAN B.
Published: July 2002

Given a uniformly continuous quantum dynamical semigroup on a separable unital C* algebra, we construct a canonical Evans–Hudson (E-H) dilation. Such a result was already proved by Goswami and Sinha6 in the von Neumann algebra setup, which has been extended to the C* algebraic framework in this paper. The authors make use of the coordinate-free calculus and results of Ref. 6, but the proof of the existence of structure maps differs from that of Ref. 6.
CANONICAL BEHAVIOR OF BOREL FUNCTIONS ON SUPERPERFECT RECTANGLES
Authors: SPINAS OTMAR
Published: July 2002

We describe a list of canonical functions from (ωω)2 to ℝ such that every Borel measurable function from (ωω)2 to ℝ, on some superperfect rectangle, induces the same equivalence relation as some canonical function.
A WEAKENED FORM OF FICTITIOUS PLAY IN TWO-PERSON ZERO-SUM GAMES
Authors: VAN DER GENUGTEN BEN
Published: July 2002

Fictitious play can be seen as a numerical iteration procedure for determining the value of a game and corresponding optimal strategies. Although convergence is slow, it needs only a modest computer storage. Therefore it seems to be a good way for analysing large games. In this paper we introduce a weakened form of fictitious play, where players at each stage do not have to make the best choice against the total of past choices of the other player but only an increasingly better one. Theoretical bounds for convergence are derived. Furthermore, it is shown that this new form can speed up convergence considerably in practice. It is seen that weakened fictitious play can be extended to models in which the game matrix itself becomes better known as the number of stages increases.
DISCRETE CLOTHOID SPLINE SURFACES ON OPEN MESHES
Authors: LI GUIQING , LI XIANMIN , LI HUA
Published: July 2002

By introducing a discrete Frenet frame, this paper first proposes 3D discrete clothoid splines to extend the planar discrete clothoid splines of Schneider and Kobbelt. On the basis of 3D discrete clothoid spline curves, discrete clothoid spline surfaces for arbitrary meshes are defined as a generalization of their closed discrete clothoid spline surfaces. Moreover, a discrete mean curvature normal operator instead of the conic surface fitting method is employed to compute curvature values. This induces a new iteration algorithm for generating the discrete clothoid spline surfaces. Since the curvature at a vertex is an area average over a region around this vertex and no linear system needs to be settled, the algorithm works more steadily and efficiently. Besides being directly used to produce fair mesh surfaces, the approach can also be employed to smooth control nets of spline surfaces.
SLOW DENSE GRANULAR FLOWS AS A SELF-INDUCED PROCESS
Authors: POULIQUEN OLIVIER , FORTERRE YOËL , LE DIZES STÉPHANE
Published: July 2002

A simple model is presented for the description of steady uniform shear flow of granular material. The model is based on a stress fluctuation activated process. The basic idea is that shear between two particle layers induces fluctuations in the media that may trigger a shear at some other position. Based on this idea, a minimum model is derived and applied to different configurations of granular shear flow.
TEACHING MANIPULATION SKILLS TO A ROBOT THROUGH A HAPTIC RENDERED VIRTUAL ENVIRONMENT
Authors: CHEN Y. , NAGHDY F.
Published: July 2002

A new paradigm for programming of robotics manipulator to perform complex constrained motion tasks is being studied. The teaching of the manipulation skills to the machine starts by demonstrating those skills in a haptic-rendered virtual environment. Position and contact force and torque data generated in the virtual environment combined with a priori knowledge about the task is used to identify and learn the skills in the newly demonstrated tasks and then to reproduce them in the robotics system. The peg-in-hole insertion problem is used as a study case. The overall concept is described. The methodologies developed to build the virtual environment and to learn the basic skills are presented. Results obtained so far are provided.
THE ASPECT OF NATURAL RESOURCES IN ENVIRONMENTAL IMPACT STATEMENTS FOR SWEDISH BIOENERGY PLANTS
Authors: BRUHN-TYSK SARA , EKLUND MATS
Published: July 2002

According to Swedish environmental legislation, an environmental impact assessment (EIA) has to be made when planning energy plants. The EIA has to include the effects of the proposed project on natural resource management; however, a review of the environ-mental impact statements for proposed energy plants reveals that the scope of the assessment seldom includes this aspect. This may be due to several reasons, such as the scope of the legal requirements, which do not include sustainable resource extraction but focus on local issues linked to the energy plant. In order to widen the scope of EIAs to include the management of natural resources, it is suggested that other tools for environmental systems understanding such as life-cycle assessment (LCA) and material flow analysis (MFA) can improve the basis for decision-making by providing ways to map resource flows of proposed projects and by including environmental aspects not connected with the energy plant itself.
Maintenance of geometric extrema
Authors: Dobkin David , Suri Subhash
Published: July 2002

Let
S
be a set,
f
:
S
×
S
→
R
+
a bivariate function, and
f
(
x
,
S
) the
maximum
value of
f
(
x
,
y
) over all elements
y
∈
S
. We say that
f
is
decomposable
with respect with the maximum if
f
(
x
,
S
) = max {
f
(
x
,
S
1
),
f
(
x
,
S
2
),…,
f
(
x
,

S
k

)} for any decomposition
S
= ∪

i
=1

i
=
k

S
i

. Computing the maximum (minimum) value of a decomposable function is inherent in many problems of computational geometry and robotics. In this paper, a general technique is presented for updating the maximum (minimum) value of a decomposable function as elements are inserted into and deleted from the set
S
. Our result holds for a
semi-online
model of dynamization: When an element is inserted, we are told how long it will stay. Applications of this technique include efficient algorithms for
dynamically
computing the diameter or closest pair of a set of points, minimum separation among a set of rectangles, smallest distance between a set of points and a set of hyperplanes, and largest or smallest area (perimeter) retangles determined by a set of points. These problems are fundamental to application areas such as robotics, VLSI masking, and optimization.
Concurrency control in a dynamic search structure
Authors: Manbar Udi , Ladner Richard E.
Published: July 2002

A design of a data structure and efficient algorithms for concurrent manipulations of a dynamic search structure by independent user processes is presented in this paper. The algorithms include updating data, inserting new elements, and deleting elements. The algorithms support a high level of concurrency. Each of the operations listed above requires only constant amount of locking. In order to make the system even more efficient for the user processes, maintenance processes are introduced. The maintenance processes operate independently in the background to reorganize the data structure and “clean up” after the (more urgent) user processes. A proof of correctness of the algorithms is given and some experimental results and extensions are examined.
Nonlinear pattern matching in trees
Authors: Ramesh R. , Ramakrishnan I. V.
Published: July 2002

Tree pattern matching is a fundamental operation that is used in a number of programming tasks such as mechanical theorem proving, term rewriting, symbolic computation, and nonprocedural programming languages. In this paper, we present new sequential algorithms for nonlinear pattern matching in trees. Our algorithm improves upon know tree pattern matching algorithms in important aspects such as time performance, ease of integration with several reduction strategies and ability to avoid unnecessary computation steps on match attempts that fail. The expected time complexity of our algorithm is linear in the sum of the sizes of the two trees.
Reasoning about functional dependencies generalized for semantic data models
Authors: Weddell Grant E.
Published: July 2002

We propose a more general form of functional dependency for semantic data models that derives from their common feature in which the separate notions of
domain
and
relation
in the relational model are combined into a single notion of
class
. This usually results in a richer terminological component for their query languages, whereby terms may navigate through any number of properties, including none. We prove the richer expressiveness of this more general functional dependency, and exhibit a sound and complete set of inference axioms. Although the general problem of decidability of their logical implication remains open at this time, we present decision procedures for cases in which the dependencies included in a schema correspond to keys, or in which the schema itself is acyclic. The theory is then extended to include a form of conjunctive query. Of particular significance is that the query becomes an additional source of functional dependency. Finally, we outline several applications of the theory to various problems in physical design and in query optimization. The applications derive from an ability to predict when a query can have at most one solution.
Parallelism analyzers for parallel discrete event simulation
Authors: Lin Yi-Bing
Published: July 2002

Discrete event simulation is usually time consuming. Recently, there has been a great deal of interest in using parallel computers to speed up the simulation process. Before the parallel simulation approach is applied, it is important to understand the inherent parallelism of simulation applications. A simple technique called
critical path analysis
was proposed to study paralllelism of simulation applications. This paper describes three critical path analysis algorithms based on different event-scheduling (process scheduling) policies. These algorithms are much simpler than a previous approach, where the events must be recorded in a trace and an extra pass is required to process the event trace. In our approach, the critical path analysis algorithms are integrated with the sequential simulation. At the end of the sequential simulation, the optimal parallel execution time is also computed. Livny proposed an algorithm similar to our approach (His, however, was designed for a specific language). Our algorithms can be integrated with sequential simulation programs written by users or be integrated with simulation languages. Another advantage of our algorithms over previous approaches is that ours can be used to study load balancing under different event-scheduling policies. Since our algorithms can be easily inserted in sequential simulation programs, critical path analysis can be applied to existing sequential programs without difficulty. The results can then be used to predict the performance of parallel simulation on similar applications. An example is given to show how useful information can be obtained from our algorithms.
Learning via queries
Authors: Gasarch William I. , Smith Carl H.
Published: July 2002

Traditional work in inductive inference has been to model a learner receiving data about a function
f
and trying to learn the function. The data is usually just the values
f
(0),
f
(1),…. The scenario is modeled so that the learner is also allowed to ask questions about the data (e.g., (∀ χ) [χ> 17 →
f
(
χ
) = 0]?). An important parameter is the language that the lerner may use to formulate queries. We show that for most languages a learner can learn more by asking questions than by passively receiving data. Mathematical tools used include the solution to Hilbert's tenth problem, the decidability of Presuburger arithmetic, and ω-automata.
Automatic recognition of tractability in inference relations
Authors: McAllester David A.
Published: July 2002

A procedure is given for recognizing sets of inference rules that generate polynomial time decidable inference relations. The procedure can automatically recognize the tractability of the inference rules underlying congruence closure. The recognition of tractability for that particular rule set constitutes mechanical verification of a theorem originally proved independently by Kozen and Shostak. The procedure is algorithmic, rather than heuristic, and the class of automatically recognizable tractable rule sets can be precisely characterized. A series of examples of rule sets whose tractability is nontrivial, yet machine recognizable, is also given. The technical framework developed here is viewed as a first step toward a general theory of tractable inference relations.
Finite representation of infinite query answers
Authors: Chomicki Jan , Imieliński Tomasz
Published: July 2002

We define here a formal notion of finite representation of infinite query answers in logic programs. We apply this notion to Datalog
nS
programs may be infinite and consequently queries may have infinite answers.

We present a method to finitely represent infinite least Herbrand models of Datalog
nS
program (and its underlying computational engine) can be forgotten. Given a query to be evaluated, it is easy to obtain from the relational specification finitely many answer substitutions that represent infinitely many answer substitutions to the query. The method involved is a combination of a simple, unificationless, computational mechanism (graph traversal, congruence closure, or term rewriting) and standard relational query evaluation methods. Second, a relational specification is
effectively computable
and its computation is no harder, in the sense of the complexity class, than answering yes-no queries.

Our method is applicable to every range-restricted Datalog
nS
program. We also show that for some very simple non-Datalog
nS
logic programs, finite representations of query answers do not exist.
Smart telepointers
Authors: Rodham Kenneth J. , Olsen Dan R.
Published: July 2002

Conventional methods for maintaining telepointer consistency in shared windows do not work in the presence of per-user window customizations. This article presents the notion of a “smart telepointer,” which is a telepointer that works correctly in spite of such customizations. Methods for smart-telepointer implementation are discussed.
Reservoir-sampling algorithms of time complexity
O
(
n
(1 + log(
N
/
n
)))
Authors: Li Kim-Hung
Published: July 2002

One-pass algorithms for sampling
n
records without replacement from a population of unknown size
n
are known as reservoir-sampling algorithms. In this article, Vitter's reservoir-sampling algorithm, algorithm Z, is modified to give a more efficient algorithm, algorithm K. Additionally, two new algorithms, algorithm L and algorithm M, are proposed. If the time for scanning the population is ignored, all the four algorithms have expected CPU time
O
(
n
(1 + log(
N
/
n
))), which is optimum up to a constant factor. Expressions of the expected CPU time for the algorithms are presented. Among the four, algorithm L is the simplest, and algorithm M is the most efficient when
n
and
N
/
n
are large and
N
is
O
(
n
2
).
Performance analysis of recovery techniques
Authors: Reuter Andreas
Published: July 2002

Various logging and recovery techniques for centralized transaction-oriented database systems under performance aspects are described and discussed. The classification of functional principles that has been developed in a companion paper is used as a terminological basis. In the main sections, a set of analytic models is introduced and evaluated in order to compare the performance characteristics of nine different recovery techniques with respect to four key parameters and a set of other parameters with less influence. Finally, the results of model evaluation as well as the limitations of the models themselves are discussed.
Bounds on the speedup and efficiency of partial synchronization in parallel processing systems
Authors: Chang C. S. , Nelson R.
Published: July 2002

In this paper, we derive bounds on the speedup and efficiency of applications that schedule tasks on a set of parallel processors. We assume that the application runs an algorithm that consists of
N
iterations and before starting its
i
+1st iteration, a processor must wait for data (i.e., synchronize) calculated in the
i
th iteration by a subset of the other processors of the system. Processing times and interconnections between iterations are modeled by random variables with possibly deterministic distributions. Scientific applications consisting of iterations of recursive equations are examples of such applications that can be modeled within this formulation. We consider the efficiency of applications and show that, although efficiency decreases with an increase in the number of processors, it has a nonzero limit when the number of processors increases to infinity. We obtain a lower bound for the efficiency by solving an equation that depends on the distribution of task service times and the expected number of tasks needed to be synchronized. We also show that the lower bound is approached if the topology of the processor graph is ldquo;spread-out,” a notion we define in the paper.
Greed sort
Authors: Nodine Mark H. , Vitter Jeffrey Scott
Published: July 2002

We present an algorithm for sorting efficiently with parallel two-level memories. Our main result is an elegant, easy-to-implement, optimal,
deterministic
algorithm for external sorting with
D
disk drives. This result answers in the affirmative the open problem posed by Vitter and Shriver of whether an optimal algorithm exists that is deterministic. Our measure of performance is the number of parallel input/output (I/O) operations, in which each of the
D
disks can simultaneously transfer a block of
B
contiguous records. We assume that internal memory can hold
M
records. Our algorithm sorts
N
records in the optimal bound of θ((
N/BD
) log(
N/B
)/ log(
M/B
)) deterministically, and thus improves upon Vitter and Shriver's optimal randomized algorithm as well as the well-known deterministic but nonoptimal technique of disk striping. It is also practical to implement.
An optimal service policy for buffer systems
Authors: Birman Alexander , Gail H. Richard , Hantler Sidney L. , Rosberg Zvi , Sidi Moshe
Published: July 2002

Consider a switching component in a packet-switching network, where messages from several incoming channels arrive and are routed to appropriate outgoing ports according to a service policy. One requirement in the design of such a system is to determine the buffer storage necessary at the input of each channel and the policy for serving these buffers that will prevent buffer overflow and the corresponding loss of messages. In this paper, a class of buffer service policies, called Least Time to Reach Bound (LTRB), is introduced that guarantees no overflow, and for which the buffer size required at each input channel is independent of the number of channels and their relative speeds. Further, the storage requirement is only twice the maximal length of a message in all cases, and as a consequence the class is shown to be
optimal
in the sense that any nonoverflowing policy requires at least as much storage as LTRB.
Integrating an object server with other worlds
Authors: Purdy Alan , Schuchardt Bruce , Maier David
Published: July 2002

Object-oriented database servers are beginning to appear on the commercial market in response to a demand by application developers for increased modeling power in database systems. Before these new servers can enhance the productivity of application designers, systems designers must provide simple interfaces to them from both procedural and object-oriented languages. This paper first describes a successful interface between an object server and two procedural languages (C and Pascal). Because C and Pascal do not support the object-oriented paradigm application, designers using these languages must deal with database objects in less than natural ways. Fortunately, workstations supporting object-oriented languages have the potential for interacting with database objects in a much more integrated manner. To integrate these object-oriented workstations with an object server, we provide a design framework based on the notion of workstation
agent
objects representing
principal
objects in the database. We distinguish two types of agents:
proxies
, which forward most messages to the principal objects, and
deputies
, which can cache state for their principal and act with more autonomy. The interaction of cache, transaction, and message management strategies makes the implementation of deputies a nontrivial problem. The agent metaphor is being used currently to integrate an object server with a Smalltalk-8O™ workstation.
Dynamic quorum adjustment for partitioned data
Authors: Herlihy Maurice
Published: July 2002

A partition occurs when functioning sites in a distributed system are unable to communicate. This paper introduces a new method for managing replicated data objects in the presence of partitions. Each operation provided by a replicated object has a set. of quorums, which are sets of sites whose cooperation suffices to execute the operation. The method permits an object's quorums to be adjusted dynamically in response to failures and recoveries. A transaction that is unable to progress using one set of quorums may switch to another, more favorable set, and transactions in different. Partitions may progress using different sets. This method has three novel aspects: (1) it supports a wider range of quorums than earlier proposals, (2) it, scales up effectively to large systems because quorum adjustments do not require global reconfiguration, and (3) it, systematically exploits the semantics of typed objects to support more flexible quorum adjustment.
Solving satisfiability and implication problems in database systems
Authors: Guo Sha , Sun Wei , Weiss Mark A.
Published: July 2002

Satisfiability, implication, and equivalence problems involving conjunctive inequalities are important and widely encountered database problems that need to be efficiently and effectively processed. In this article we consider two popular types of arithmetic inequalities, (

X
op
Y

) and (
X
op
C
), where
X
and
Y
are attributes,
C
is a constant of the domain or
X
, and
op
∈{<, ≤, =, ≠, >, ≥). These inequalities are most frequently used in a database system, inasmuch as the former type of inequality represents a 0-join, and the latter is a selection. We study the satisfiability and implication problems under the integer domain and the real domain, as well as under two different operator sets ({<, ≤, =, ≥, >} and {<, ≤, =, ≠, ≥, >}). Our results show that solutions under different domains and/or different operator sets are quite different. Out of these eight cases, excluding two cases that had been shown to be NP-hard, we either report the first necessary and sufficient conditions for these problems as well as their efficient algorithms with complexity analysis (for four cases), or provide an improved algorithm (for two cases). These iff conditions and algorithms are essential to database designers, practitioners, and researchers. These algorithms have been implemented and an experimental study comparing the proposed algorithms and those previously known is conducted. Our experiments show that the proposed algorithms are more efficient than previously known algorithms even for small input. The C++ code can be obtained by an anonymous ftp from .
A probabilistic relational model and algebra
Authors: Dey Debabrata , Sarkar Sumit
Published: July 2002

Although the relational model for databases provides a great range of advantages over other data models, it lacks a comprehensive way to handle incomplete and uncertain data. Uncertainty in data values, however, is pervasive in all real-world environments and has received much attention in the literature. Several methods have been proposed for incorporating uncertain data into relational databases. However, the current approaches have many shortcomings and have not established an acceptable extension of the relational model. In this paper, we propose a consistent extension of the relational model. We present a revised relational structure and extend the relational algebra. The extended algebra is shown to be closed, a consistent extension of the conventional relational algebra, and reducible to the latter.
Heraclitus
Authors: Ghandeharizadeh Shahram , Hull Richard , Jacobs Dean
Published: July 2002

Traditional database systems provide a user with the ability to query and manipulate one database state, namely the current database state. However, in several emerging applications, the ability to analyze “what-if” scenarios in order to reason about the impact of an update (before committing that update) is of paramount importance. Example applications include hypothetical database access, active database management systems, and version management, to name a few. The central thesis of the Heraclitus paradigm is to provide flexible support for applications such as these by elevating
deltas
, which represent updates proposed against the current database state, to be first-class citizens. Heraclitus[Alg,C] is a database programming language that extends C to incorporate the relational algebra and deltas. Operators are provided that enable the programmer to explicitly construct, combine, and access deltas. Most interesting is the when operator, that supports hypothetical access to a delta: the expression
E
when σ yields the value that side effect free expression E would have if the value of delta expression σ were applied to the current database state. This article presents a broad overview of the philosophy underlying the Heraclitus paradigm, and describes the design and prototype implementation of Heraclitus[Alg, C]. A model-independent formalism for the Heraclitus paradigm is also presented. To illustrate the utility of Heraclitus, the article presents an in-depth discussion of how Heraclitus[Alg, C] can be used to specify, and thereby implement, a wide range of execution models for rule application in active databases; this includes both prominent execution models presented in the literature, and more recent “customized” execution models with novel features.
Access control for large collections
Authors: Gladney H. M.
Published: July 2002

Efforts to place vast information resources at the fingertips of each individual in large user populations must be balanced by commensurate attention to information protection. For distributed systems with less-structured tasks, more-diversified information, and a heterogeneous user set, the computing system must administer enterprise-chosen access control policies. One kind of resource is a digital library that emulates massive collections of paper and other physical media for clerical, engineering, and cultural applications. This article considers the security requirements for such libraries and proposes an access control method that mimics organizational practice by combining a subject tree with ad hoc role granting that controls privileges for many operations independently, that treats (all but one) privileged roles (e.g., auditor, security officer) like every other individual authorization, and that binds access control information to objects indirectly for scaling, flexibility, and reflexive protection. We sketch a realization and show that it will perform well, generalizes many deployed proposed access control policies, and permits individual data centers to implement other models economically and without disruption.
A case study of verification, validation, and accreditation for advanced distributed simulation
Authors: Page Ernest H. , Canova Bradford S. , Tufarolo John A.
Published: July 2002

The techniques and methodologies for verification and validation of software-based systems have arguably realized their greatest utility within the context of simulation. Advanced Distributed Simulation (ADS), a major initiative within the defense modeling and simulation community, presents a variety of challenges to the classical approaches. A case study of the development process and concomitant verification and validation activities for the Joint Training Confederation (JTC) is presented. The JTC is one of the largest current ADS efforts, and the primary application of the Aggregate Level Simulation Protocol. A dichotomy between classical verification and validation approaches and the requirements of a prototypical ADS environment is illustrated. Mechanisms and research directions to resolve these differences are briefly discussed.
Multiplicative, congruential random-number generators with multiplier ± 2

k
1

± 2

k
2

and modulus 2

p

- 1
Authors: Wu Pei-Chi
Published: July 2002

The demand for random numbers in scientific applications is increasing. However, the most widely used multiplicative, congruential random-number generators with modulus 2
31
- 1 have a cycle length of about 2.1 × 10
9
. Moreover, developing portable and efficient generators with a larger modulus such as 2
61
- 1 is more difficult than those with modulus 2
31
- 1. This article presents the development of multiplicative, congruential generators with modulus
m
= 2

p

- 1 and four forms of multipliers: 2

k
1

- 2

k
2

, 2

k
1

+ 2

k
2

,
m
- 2

k
1

+ 2

k
2

, and
m
- 2

k
1

- 2

k
2

,
k
1 >
k
2. The multipliers for modulus 2
31
- 1 and 2
61
- 1 are measured by spectral tests, and the best ones are presented. The generators with these multipliers are portable and vary fast. They have also passed several empirical tests, including the frequency test, the run test, and the maximum-of-t test.
Reduced MVDs and minimal covers
Authors: Özsoyoğlu Z. Meral , Yuan Li-Yan
Published: July 2002

Multivalued dependencies (MVDs) are data dependencies that appear frequently in the “real world” and play an important role in designing relational database schemes. Given a set of MVDs to constrain a database scheme, it is desirable to obtain an equivalent set of MVDs that do not have any redundancies. In this paper we define such a set of MVDs, called reduced MVDs, and present an algorithm to obtain reduced MVDs. We also define a minimal cover of a set of MVDs, which is a set of reduced MVDs, and give an efficient method to find such a minimal cover. The significance and properties of reduced MVDs are also discussed in the context of database design (e.g., 4NF decomposition) and conflict-free MVDs.
Primitives for the manipulation of general subdivisions and the computation of Voronoi
Authors: Guibas Leonidas , Stolfi Jorge
Published: July 2002

The following problem is discussed: given
n
points in the plane (the sites) and an arbitrary query point
q
, find the site that is closest to
q
. This problem can be solved by constructing the Voronoi diagram of the griven sites and then locating the query point inone of its regions. Two algorithms are given, one that constructs the Voronoi diagram in
O
(
n
log
n
) time, and another that inserts a new sit on
O(n)
time. Both are based on the use of the Voronoi dual, or Delaunay triangulation, and are simple enough to be of practical value. the simplicity of both algorithms can be attributed to the separation of the geometrical and topological aspects of the problem and to the use of two simple but powerful primitives, a geometric predicate and an operator for manipulating the topology of the diagram. The topology is represented by a new data structure for generalized diagrams, that is, embeddings of graphs in two-dimensional manifolds. This structure represents simultaneously an embedding, its dual, and its mirror image. Furthermore, just two operators are sufficients for building and modifying arbitrary diagrams.
On the space complexity of randomized synchronization
Authors: Fich Faith , Herlihy Maurice , Shavit Nir
Published: July 2002

The “waite-free hierarchy” provides a classification of multiprocessor synchronization primitives based on the values ofnfor which there are deterministic wait-free implementations ofn-process consensus using instances of these objects andread-writeregisters. In a randomized wait-free setting, this classification is degenerate, sincen-process consensus can be solved using onlyO(n) read-writeregisters.

In this paper, we propose a classification of synchronization primitives based on thespace complexityof randomized solutions ton-process consensus. Ahistoryless object,such as aread-writeregister, aswapregister, or atest&setregister, is an object whose state depends only on the lost nontrivial operation thate was applied to it. We show that, usinghistorylessobjects, Ω(√n) object instances are necessary to solven-process consensus. This lower bound holds even if the objects have unbounded size and the termination requirement isnondeterministic solo termination, a property strictly weaker than randomized wait-freedom.

We then use this result to related the randomized space complexity of basic multiprocessor synchronization primitives such asshared counters, fetch&addregisters, andcompare&swapregisters. Viewed collectively, our results imply that there is a separation based on space complexity for synchronization primitives in randomized computation, and that this separation differs from that implied by the deterministic “wait-free hierarchy.”
Algorithm 783
Authors: Peters Jörg
Published: July 2002

Unrestricted control polyhedra facilitate modeling free-form surfaces of arbitrary topology and local patch-layout by allowing
n
-sided, possibly nonplanar, facets and
m
-valent vertices. By cutting off edges and corners, the smoothing of an unrestricted control polyhedron can be reduced to the smoothing of a
planar-cut polyhedron
. A planar-cut polyhedron is a generalization of the well-known tensor-product control structure. The routine Pcp2Nurb in turn translates planar-cut polyhedra to a collection of four-sided linearly trimmed bicubic B-splines and untrimmed biquadratic B-splines. The routine can thus serve as central building block for overcoming topological constraints in the mathematical modeling of smooth surfaces that are stored, transmitted, and rendered using only the standard representation in industry. Specifically, on input of a nine-point subnet of a planar-cut polyhedron, the routine outputs a trimmed bicubic NURBS patch. If the subnet does not have geometrically redundant edges, this patch joins smoothly with patches from adjacent subnets as a four-sided piece of a regular

C
1

surface. The patch integrates smoothly with untrimmed biquadratic tensor-product surfaces derived from subnets with tensor-product structure. Sharp features can be retained in this representation by using geometrically redundant edges in the planar-cut polyhedron. The resulting surface follows the outlines of the planar-cut polyhedron in the manner traditional tensor-product splines follow the outline of their rectilinear control polyhedron. In particular, it stays in the local convex hull of the planar-cut polyhedron.
Limitations of concurrency in transaction processing
Authors: Franaszek Peter , Robinson John T.
Published: July 2002

Given the pairwise probability of conflict p among transactions in a transaction processing system, together with the total number of concurrent transactions n, the effective level of concurrency E(n,p) is defined as the expected number of the n transactions that can run concurrently and actually do useful work. Using a random graph model of concurrency, we show for three general classes of concurrency control methods, examples of which are (1) standard locking, (2) strict priority scheduling, and (3) optimistic methods, that (1) E(n, p) ⩽ n(1 - p/2)
n-1
, (2) E(n, p) ⩽ (1 - (1 - p)
n
)/p, and (3) 1 + ((1 - p)/p)ln(p(n - 1) + 1) ⩽ E(n, p) ⩽ 1 + (1/p)ln(p(n - 1) + 1). Thus, for fixed p, as n ↣ ∞), (1) E ↣ 0 for standard locking methods, (2) E ⩽ 1/p for strict priority scheduling methods, and (3) E ↣ ∞ for optimistic methods. Also found are bounds on E in the case where conflicts are analyzed so as to maximize E.

The predictions of the random graph model are confirmed by simulations of an abstract transaction processing system. In practice, though, there is a price to pay for the increased effective level of concurrency of methods (2) and (3): using these methods there is more wasted work (i.e., more steps executed by transactions that are later aborted). In response to this problem, three new concurrency control methods suggested by the random graph model analysis are developed. Two of these, called (a) running priority and (b) older or running priority, are shown by the simulation results to perform better than the previously known methods (l)-(3) for relatively large n or large p, in terms of achieving a high effective level of concurrency at a comparatively small cost in wasted work.
On the efficiency of subsumption algorithms
Authors: Gottlob G. , Leitsch A.
Published: July 2002

The costs of subsumption algorithms are analyzed by an estimation of the maximal number of unification attempts (worst-case unification complexity) made for deciding whether a clause
C
subsumes a clause
D
. For this purpose the clauses
C
and
D
are characterized by the following parameters: number of variables in
C
, number of literals in
C
, number of literals in
D
, and maximal length of the literals. The worst-case unification complexity immediately yields a lower bound for the worst-case time complexity.

First, two well-known algorithms (Chang-Lee, Stillman) are investigated. Both algorithms are shown to have a very high worst-case time complexity. Then, a new subsumption algorithm is defined, which is based on an analysis of the connection between variables and predicates in
C
. An upper bound for the worst-case unification complexity of this algorithm, which is much lower than the lower bounds for the two other algorithms, is derived. Examples in which exponential costs are reduced to polynomial costs are discussed. Finally, the asymptotic growth of the worst-case complexity for all discussed algorithms is shown in a table (for several combinations of the parameters).
Algorithm 793
Authors: Gautschi Walter
Published: July 2002

The concern here is with Gauss-type quadrature rules that are exact for a mixture of polynomials and rational functions, the latter being selected so as to simulate poles that may be present in the integrand. The underlying theory is presented as well as methods for constructing such rational Gauss formulae. Relevant computer routines are provided and applied to a number examples, including Fermi-Dirac and Bose-Einstein integrals of interest in solid state physics.
Parallel algorithms for minimum cuts and maximum flows in planar networks
Authors: Johnson Donald B.
Published: July 2002

Algorithms are given that compute maximum flows in planar directed networks either in
O
((log
n
)
3
) parallel time using
O
(
n
4
) processors or
O
((log
n
)
2
) parallel time using
O
(
n
6
) processors. The resource consumption of these algorithms is dominated by the cost of finding the value of a maximum flow. When such a value is given, or when the computation is on an undirected network, the bound is
O
((log
n
)
2
) time using
O
(
n
3
) processors. No efficient parallel algorithm is known for the maximum flow problem in general networks.
Correction to “An equivalence between relational database dependencies and a fragment of propositional logic”
Authors: Sagiv Y. , Delobel C. , Parker D. S. , Fagin Ronald
Published: July 2002

According to the definition of satisfaction of Boolean dependencies, Theorem 15 is not true for Boolean dependencies with negation. (A
positive
Boolean dependency is built using the Boolean connectives ⋏, ⋎, and ↛; a general Boolean dependency (with negation) may use also the Boolean connective ¬.) Actually, the definition of satisfaction is not meaningful for Boolean dependencies with negation, since many are never satisfied. We show how the definition of satisfaction should be changed in order to make Boolean dependencies with negation meaningful and correct the error.

We associate with each relation
r
a set α(
r
) of
truth assignments
, as follows. For each pair of distinct tuples of
r
, the set α(
r
) contains the truth assignment that maps an attribute
A
to true if the two tuples are equal on
A
, and to false if the two tuples have different values for
A
. A Boolean dependency σ is satisfied by a relation
r
if σ (i.e., the corresponding Boolean formula) satisfies every truth assignment of α(
r
).

The original definition given in the paper is equivalent to having α(
r
) also include the truth assignment that is generated by pairs in which both tuples are really the same tuple of
r
, that is, to having α(
r
) also always include the truth assignment τ mapping all attributes to true. Under that definition, however, many Boolean dependencies with negation are never satisfied and, hence, are meaningless. More precisely, according to the original definition, a Boolean dependency is satisfied by
Consequences of assuming a universal relation
Authors: Kent W.
Published: July 2002

Although central to the current direction of dependency theory, the assumption of a universal relation is incompatible with some aspects of relational database theory and practice. Furthermore, the universal relation is itself ill defined in some important ways. And, under the universal relation assumption, the decomposition approach to database design becomes virtually indistinguishable from the synthetic approach.