bluuebunny/crossref_metadata_2025 huggingface dataset:
Index structures for selective dissemination of information under the Boolean model
Authors: Yan Tak W. , García-Molina Héctor
Published: July 2002

The number, size, and user population of bibliographic and full-text document databases are rapidly growing. With a high document arrival rate, it becomes essential for users of such databases to have access to the very latest documents; yet the high document arrival rate also makes it difficult for users to keep themselves updated. It is desirable to allow users to submit profiles, i.e., queries that are constantly evaluated, so that they will be automatically informed of new additions that may be of interest. Such service is traditionally called Selective Dissemination of Information (SDI).

The high document arrival rate, the huge number of users, and the timeliness requirement of the service pose a challenge in achieving efficient SDL. In this article, we propose several index structures for indexing profiles and algorithms that efficiently match documents against large number of profiles. We also present analysis and simulation results to compare their performance under different scenarios.
Fast algorithms for universal quantification in large databases
Authors: Graefe Goetz , Cole Richard L.
Published: July 2002

Universal quantification is not supported directly in most database systems despite the fact that it adds significant power to a system's query processing and inference capabilities, in particular for the analysis of many-to-many relationships and of set-valued attributes. One of the main reasons for this omission has been that universal quantification algorithms and their performance have not been explored for large databases. In this article, we describe and compare three known algorithms and one recently proposed algorithm for relational division, the algebra operator that embodies universal quantification. For each algorithm, we investigate the performance effects of explicit duplicate removal and referential integrity enforcement, variants for inputs larger than memory, and parallel execution strategies. Analytical and experimental performance comparisons illustrate the substantial differences among the algorithms. Moreover, comparisons demonstrate that the recently proposed division algorithm evaluates a universal quantification predicate over two relations as fast as hash (semi-) join evaluates an existential quantification predicate over the same relations. Thus, existential and universal quantification can be supported with equal efficiency by adding the recently proposed algorithm to a query evaluation system. A second result of our study is that universal quantification should be expressed directly in a database query language, because most query optimizers do not recognize the rather indirect formulations available in SQL as relational division and therefore produce very poor evaluation plans for many universal quantification queries.
Polymorphism and type inference in database programming
Authors: Buneman Peter , Ohori Atsushi
Published: July 2002

In order to find a static type system that adequately supports database languages, we need to express the most general type of a program that involves database operations. This can be achieved through an extension to the type system of ML that captures the polymorphic nation of field selection, together with a techniques that generalizes relational operators to arbitrary data structures. The combination provides a statically typed language in which generalized relational databases may be cleanly represented as typed structures. As in ML types are inferred, which relieves the programmer of making the type assertions that may be required in a complex database environment.

These extensions may also be used to provide static polymorphic typechecking in object-oriented languages and databases. A problem that arises with object-oriented databases is the apparent need for dynamic typechecking when dealing queries on heterogeneous collections of objects. An extension of the type system needed for generalized relational operations can also be used for manipulating collections of dynamically typed values in a statically typed language. A prototype language based on these ideas has been implemented. While it lacks a proper treatment of persistent data, it demonstrates that a wide variety of database structures can be cleanly represented in a polymorphic programming language.
Foundations of multimedia database systems
Authors: Marcus Sherry , Subrahmanian V. S.
Published: July 2002

Though numerous multimedia systems exist in the commercial market today, relatively little work has been done on developing the mathematical foundation of multimedia technology. We attempt to take some initial steps towards the development of a theoretical basis for a multimedia information system. To do so, we develop the motion of a structured multimedia database system. We begin by defining a mathematical model of a media-instance. A media-instance may be thought of as “glue” residing on top of a specific physical media-representation (such as video, audio, documents, etc). Using this “glue”, it is possible to define a general purpose logical query language to query multimedia data. This glue consists of a set of “states” (e.g., video frames, audio tracks, etc.) and “features”, together with relationships between states and/or features. A structured multimedia database system imposes a certain mathematical structures on the set of features/states. Using this notion of a structure, we are able to define indexing structures for processing queries, methods to relax queries when answers do not exist to those queries, as well as sound, complete and terminating procedures to answer such queries (and their relaxations, when appropriate). We show how a media-presentation can be generated by processing a sequence of queries, and furthermore we show that when these queries are extended to include
constraints
, then these queries can not only generate presentations, but also generate temporal synchronization properties and spatial layout properties for such presentations. We describe the architecture of a prototype multimedia database system based on the principles described in this paper.
A framework for event-based software integration
Authors: Barrett Daniel J. , Clarke Lori A. , Tarr Peri L. , Wise Alexander E.
Published: July 2002

Although event-based software integration is one of the most prevalent approaches to loose integration, no consistent model for describing it exists. As a result, there is no uniform way to discuss event-based integration, compare approaches and implementations, specify new event-based approaches, or match user requirements with the capabilities of event-based integration systems. We attempt to address these shortcomings by specifying a
generic framework for event-based integration
, the EBI framework, that provides a flexible, object-oriented model for discussing and comparing event-based integration approaches. The EBI framework can model dynamic and static specification, composition, and decomposition and can be instantiated to describe the features of most common event-based integration approaches. We demonstrate how to use the framework as a reference model by comparing and contrasting three well-known integration systems: FIELD, Polylith, and CORBA.
Functional design for testability of control-dominated architectures
Authors: Fummi F. , Rovati U. , Sciuto D.
Published: July 2002

Control-dominated architectures are usually described in a hardware description language (HDL) by means of interacting FSMs. A VHDL or Verilog specification can be translated into an interacting FSM (IFSM) representation as described here. The IFSM model allows us to approach the testable synthesis problem at the level of each FSM. The functionality is modified by the addition of transparency to data flow. The complete testability of the IFSM implementation is thus achieved by connecting fully testable implementations of each modified FSM. In this way, test sequences separately generated for each FSM are directly applied to the IFSM to achieve complete fault coverage. The addition of test functionality to each FSM description, and its simultaneous synthesis with the FSM functionality, produces a lower area overhead than that necessary for the application of a partial-scan technique. Moreover, the test generation problem is highly simplified since it is reduced to the test generation for each separate FSM.
The symmetric analogue of the polynomial power basis
Authors: Sánchez-Reyes J.
Published: July 2002

A new polynomial basis over the unit interval t∈[0,1] is proposed. The work is motivation by the fact that the monomial (power) form is not suitable in CAGD, as it suffers from serious numerical problems, and the monomial coefficients have no geometric meaning. The new form is the symmetric analogue of the power form, because it can be regarded as an “Hermite two-point expansion” instead of a Taylor expansion. This form enjoys good numerical properties and admits a Horner-like evaluation algorithm that is almost as fast as that of the power form. In a ddition, the symmetric power coeddicients convey a geometric meaning, and therefore they can be used as shape handles. A polynomial expressed in the symmetric power basis is decomposed into linear, cubic, quintic, and successive components. In consequence, this basis is better suited to handle polynomials of different degrees than the Bernstein basis, and those algorithms involving degree operations have extremely simple formulations. The minimum degree of a polynomial is immediately obtained by inspecting its coefficients. Degree reduction of a curve or surface reduces to drooping the desired high degree terms.
On the completeness of object-creating database transformation languages
Authors: Van Den Bussche Jan , Van Gucht Dirk , Andries Marc , Gyssens Marc
Published: July 2002

Object-oriented applications of database systems require database transformations involoving nonstandard functionalities such as set manipulation and object creation, that is, the introduction of new domain elements. To deal with thse functionalities, Abiteboul and Kanellakis [1989] introduced the “determinate” transformations as a generalization of the standard domain-preserving transformations. The obvious extensions of complete standard database programming languages, however, are not complete for the determinate transformations. To remedy this mismatch, the “constructive” transformations are proposed. It is shown that the constructive transformations are precisely the transformations that can be expressed in said extensions of complete standard languages. Thereto, a close correspondence between object creation and the construction of hereditarily finite sets is established.

A restricted version of the main completeness result for the case where only list manipulations are involved is also presented.
Relational expressive power of constraint query languages
Authors: Benedikt Michael , Dong Guozhu , Libkin Leonid , Wong Limsoon
Published: July 2002

The expressive power of first-order query languages with several classes of equality and inequality constraints is studied in this paper. We settle the conjecture that recursive queries such as parity test and transitive closure cannot be expressed in the relational calculus augmented with polynomial inequality constraints over the reals. Furthermore, noting that relational queries exhibit several forms of genericity, we establish a number of collapse results of the following form: The class of generic Boolean queries expressible in the relational calculus augmented with a given class of constraints coincides with the class of queries expressible in the relational calculus (with or without an order relation). We prove such results for both the natural and active-domain semantics. As a consequence, the relational calculus augmented with polynomial inequalities expresses the same classes of generic Boolean queries under both the natural and active-domain semantics.

In the course of proving these results for the active-domin semantics, we establish Ramsey-type theorems saying that any query involving certain kinds of constraints coincides with a constraint-free query on databases whose elements come from a certain infinite subset of the domain. To prove the collapse results for the natural semantics, we make use of techniques from nonstandard analysis and from the model theory of ordered structures.
Serializability with constraints
Authors: Ibaraki Toshihide , Kameda Tiko , Minoura Toshimi
Published: July 2002

This paper deals with the serializability theory for single-version and multiversion database systems. We first introduce the concept of
disjoint-interval topological sort
(
DITS
, for short) of an arc-labeled directed acyclic graph. It is shown that a history is serializable if and only if its
transaction IO graph
has a DITS. We then define several subclasses of serializable histories, based on the constraints imposed by write-write, write-read, read-write, or read-read conflicts, and investigate inclusion relationships among them. In terms of DITS, we give a sufficient condition for a class of serializable histories to be polynomially recognizable, which is then used to show that a new class of histories, named WRW, can be recognized in polynomial time. We also present NP-completeness results for the problem of testing membership in some other classes.

In the second half of this paper, we extend these results to multiversion database systems. The inclusion relationships among multiversion classes defined by constraints, such as write-write and write-read, are investigated. One such class coincides with class DMVSR, introduced by Papadimitriou and Kanellakis, and gives a simple characterization of this class. It is shown that for most constraints, multiversion classes properly contain the corresponding single-version classes. Complexity results for the membership testing are also discussed.
Extending a database system with procedures
Authors: Stonebraker Michael , Anton Jeff , Hanson Eric
Published: July 2002

This paper suggests that more powerful database systems (DBMS) can be built by supporting database procedures as full-fledged database objects. In particular, allowing fields of a database to be a collection of queries in the query language of the system is shown to allow the natural expression of complex data relationships. Moreover, many of the features present in object-oriented systems and semantic data models can be supported by this facility.

In order to implement this construct, extensions to a typical relational query language must be made, and considerable work on the execution engine of the underlying DBMS must be accomplished. This paper reports on the extensions for one particular query language and data manager and then gives performance figures for a prototype implementation. Even though the performance of the prototype is competitive with that of a conventional system, suggestions for improvement are presented.
Expressions for batched searching of sequential and hierarchical files
Authors: Palvia Prashant
Published: July 2002

Batching yields significant savings in access costs in sequential, tree structured, and random files. A direct and simple expression is developed for computing the average number of records/pages accessed to satisfy a batched query of a sequential tile. The advantages of batching for sequential and random files are discussed. A direct equation is provided for the number of nodes accessed in unhatched queries of hierarchical files. An exact recursive expression is developed for node accesses in batched queries of hierarchical files. In addition to the recursive relationship, good, closed-form upper- and lower-bound approximations are provided for the case of batched queries of hierarchical files.
Multidimensional search trees that provide new types of memory reductions
Authors: Willard Dan E.
Published: July 2002

An orthogonal query that asks to aggregate the set of records in
k
-dimensional box regions is studied, and it is shown that space
O
(
N
((log
N
)/(log log
N
))

k
-1

) makes possible a combined time complexity
O
(log

k
N

) for retrievals, insertions, and deletions.
On the design of relational database schemata
Authors: Zaniolo Carlo , Meklanoff Miachel A.
Published: July 2002

The purpose of this paper is to present a new approach to the conceptual design of relational databases based on the complete relatability conditions (CRCs).

It is shown that current database design methodology based upon the elimination of anomalies is not adequate. In contradistinction, the CRCs are shown to provide a powerful criticism for decomposition. A decomposition algorithm is presented which (1) permits decomposition of complex relations into simple, well-defined primitives, (2) preserves all the original information, and (3) minimizes redundancy.

The paper gives a complete derivation of the CRCs, beginning with a unified treatment of functional and multivalued dependencies, and introduces the concept of elementary functional dependencies and multiple elementary multivalued dependencies. Admissibility of covers and validation of results are also discussed, and it is shown how these concepts may be used to improve the design of 3NF schemata. Finally, a convenient graphical representation is proposed, and several examples are described in detail to illustrate the method.
Disk allocation for Cartesian product files on multiple-disk systems
Authors: Du H. C. , Sobolewski J. S.
Published: July 2002

Cartesian product files have recently been shown to exhibit attractive properties for partial match queries. This paper considers the file allocation problem for Cartesian product files, which can be stated as follows: Given a
k
-attribute Cartesian product file and an
m
-disk system, allocate buckets among the
m
disks in such a way that, for all possible partial match queries, the concurrency of disk accesses is maximized. The Disk Modulo (DM) allocation method is described first, and it is shown to be strict optimal under many conditions commonly occurring in practice, including all possible partial match queries when the number of disks is 2 or 3. It is also shown that although it has good performance, the DM allocation method is not strict optimal for all possible partial match queries when the number of disks is greater than 3. The General Disk Modulo (GDM) allocation method is then described, and a sufficient but not necessary condition for strict optimality of the GDM method for all partial match queries and any number of disks is then derived. Simulation studies comparing the DM and random allocation methods in terms of the average number of disk accesses, in response to various classes of partial match queries, show the former to be significantly more effective even when the number of disks is greater than 3, that is, even in cases where the DM method is not strict optimal. The results that have been derived formally and shown by simulation can be used for more effective design of optimal file systems for partial match queries. When considering multiple-disk systems with independent access paths, it is important to ensure that similar records are clustered into the same or similar buckets, while similar buckets should be dispersed uniformly among the disks.
Query optimization in star computer networks
Authors: Kerschberg Larry , Ting Peter D. , Yao S. Bing
Published: July 2002

Query processing is investigated for relational databases distributed over several computers organized in a star network. Minimal response-time processing strategies are presented for queries involving the select, project, and join commands. These strategies depend on system parameters such as communication costs and different machine processing speeds; database parameters such as relation cardinality and file size; and query parameters such as estimates of the size and number of tuples in the result relation. The optimal strategies specify relation preparation processes, the shipping strategy, serial or parallel processing, and, where applicable, the site of join filtering and merging. Strategies for optimizing select and join queries have been implemented and tested.
A characterization of globally consistent databases and their correct access paths
Authors: Sagiv Yehoshua
Published: July 2002

The representative instance is proposed as a representation of the data stored in a database whose relations are not the projections of a universal instance. Database schemes are characterized for which local consistency implies global consistency. (Local consistency means that each relation satisfies its own functional dependencies; global consistency means that the representative instance satisfies all the functional dependencies.) A method of efficiently computing projections of the representative instance is given, provided that local consistency implies global consistency. Throughout, it is assumed that a cover of the functional dependencies is embodied in the database scheme in the form of keys.
Achieving robustness in distributed database systems
Authors: Eager Derek L. , Sevcik Kenneth C.
Published: July 2002

The problem of concurrency control in distributed database systems in which site and communication link failures may occur is considered. The possible range of failures is not restricted; in particular, failures may induce an arbitrary network partitioning. It is desirable to attain a high “level of robustness” in such a system; that is, these failures should have only a small impact on system operation.

A level of robustness termed
maximal partial operability
is identified. Under our models of concurrency control and robustness, this robustness level is the highest level attainable without significantly degrading performance.

A basis for the implementation of maximal partial operability is presented. To illustrate its use, it is applied to a distributed locking concurrency control method and to a method that utilizes timestamps. When no failures are present, the robustness modifications for these methods induce no significant additional overhead.
Optimal partial-match retrieval when fields are independently specified
Authors: Aho Alfred V. , Ullman Jeffrey D.
Published: July 2002

This paper considers the design of a system to answer partial-match queries from a file containing a collection of records, each record consisting of a sequence of fields. A partial-match query is a specification of values for zero or more fields of a record, and the answer to a query is a listing of all records in the file whose fields match the specified values.

A design is considered in which the file is stored in a set of bins. A formula is derived for the optimal number of bits in a bin address to assign to each field, assuming the probability that a given field is specified in a query is independent of what other fields are specified. Implications of the optimality criterion on the size of bins are also discussed.
The correctness of concurrency control mechanisms in a system for distributed databases (SDD-1)
Authors: Bernstein Philip A. , Shipman David W.
Published: July 2002

This paper presents a formal analysis of the concurrency control strategy of SDD-1. SDD-1, a System for Distributed Databases, is a prototype distributed database system being developed by Computer Corporation of America. In SDD-1, portions of data distributed throughout a network may be replicated at multiple sites. The SDD-1 concurrency control guarantees database consistency in the face of such distribution and replication.

This paper is one of a series of companion papers on SDD-1 [2, 8].
A fast procedure for finding a tracker in a statistical database
Authors: Denning Dorothy E. , Schlörer Jan
Published: July 2002

To avoid trivial compromises, most on-line statistical databases refuse to answer queries for statistics about small subgroups. Previous research discovered a powerful snooping tool, the tracker, with which the answers to these unanswerable queries are easily calculated. However, the extent of this threat was not clear, for no one had shown that finding a tracker is guaranteed to be easy.

This paper gives a simple algorithm for finding a tracker when the maximum number of identical records is not too large. The number of queries required to find a tracker is at most
Ο
(log
2
S
) queries, where
S
is the number of distinct records possible. Experimental results show that the procedure often finds a tracker with just a few queries. The threat posed by trackers is therefore considerable.
Process synchronization in database systems
Authors: Schlageter Gunter
Published: July 2002

The problem of process synchronization in database systems is analyzed in a strictly systematic way, on a rather abstract level; the abstraction is chosen such that the essential characteristics of the problem can be distinctly modeled and investigated. Using a small set of concepts, a consistent description of the whole problem is developed; many widely used, but only vaguely defined, notions are defined exactly within this framework. The abstract treatment of the problem immediately leads to practically useful insights with respect to possible solutions, although implementational aspects are not discussed in detail.
On the menbership problem for functional and multivalued dependencies in relational databases
Authors: Beeri Catriel
Published: July 2002

The problem of whether a given dependency in a database relation can be derived from a given set of dependencies is investigated. We show that the problem can be decided in polynomial time when the given set consists of either multivalued dependencies only or of both functional and multivalued dependencies and the given dependency is also either a functional or a multivalued dependency. These results hold when the derivations are restricted not to use the complementation rule.
A security machanism for statistical database
Authors: Beck Leland L.
Published: July 2002

The problem of user inference in statistical databases is discussed and illustrated with several examples. It is assumed that the database allows “total,” “average,” “count,” and “percentile” queries; a query may refer to any arbitrary subset of the database. Methods for protecting the security of such a database are considered; it is shown that any scheme which gives “statistically correct” answers is vulnerable to penetration. A precise definition of compromisability (in a statistical sense) is given. A general model of user inference is proposed; two special cases of this model appear to contain all previously published strategies for compromising a statistical database. A method for protecting the security of such a statistical database against these types of user inference is presented and discussed. It is shown that the number of queries required to compromise the database can be made arbitrarily large by accepting moderate increases in the variance of responses to queries. A numerical example is presented to illustrate the application of the techniques discussed.
On the Approximate Solution of Free Boundary Problems Using Finite Differences
Authors: Cryer C. W.
Published: July 2002

Two algorithms for solving free boundary problems in two dimensions are described. The algorithms use the method of finite differences and are automated versions of methods due to Southwell. The algorithms have been implemented as a general program FREEBOUN, and the numerical results that were obtained using this program are discussed.
Algebras Having Linear Multiplicative Complexities
Authors: Fiduccia C. M. , Zalcstein Y.
Published: July 2002

The foundations are laid for a theory of multiplicative complexity of algebras and it is shown how “multiplication problems” such as multiplication of matrices, polynomials, quaternions, etc., are instances of this theory. The usefulness of the theory is then demonstrated by utilizing algebraic ideas and results to derive complexity bounds. In particular linear upper and lower bounds for the complexity of certain types of algebras are established.
An Algorithm for Inferring Multivalued Dependencies with an Application to Propositional Logic
Authors: Sagiv Yehoshua
Published: July 2002

An algorithm is given for deciding whether a functional or a multivalued dependency
σ
(with a right-hand side
Y
) is implied by a set of functional and multivalued dependencies Σ. The running time of the algorithm is
O
(|
Y
|‖Σ‖), where
Y
is the number of attributes in
Y
and ‖Σ‖ is the size of the description of Σ. The problem of constructing the dependency basis of a set of attributes
X
is also investigated. It is shown that the dependency basis can be found in
O
(
S
‖Σ‖) time, where
S
is the number of sets in the dependency basis. Since functional and multivalued dependencies correspond to a subclass of propositional logic (that can be viewed as a generalization of Horn clauses), the algorithm given is also an efficient inference procedure for this subclass of propositional logic.
Polylog-time and near-linear work approximation scheme for undirected shortest paths
Authors: Cohen Edith
Published: July 2002

Shortest paths computations constitute one of the most fundamental network problems. Nonetheless, known parallel shortest-paths algorithms are generally inefficient: they perform significantly more work (product of time and processors) than their sequential counterparts. This gap, known in the literature as the “transitive closure bottleneck,” poses a long-standing open problem. Our main result is an O(mn

ϵ
0

+s( m+n

1+ϵ
0

)) work polylog-time randomized algorithm that computes paths within (1 +
O
(1/polylog
n
) of shortest from
s
source nodes to all other nodesin weighted undirected networks with
n
nodes and
m
edges (for any fixed ϵ
0
>0). This work bound nearly matches the Õ(sm) sequential time. In contrast, previous polylog-time algorithms required min {Õ(n
3
), Õ(m
2
)} work (even when
s
=1), and previous near-linear work algorithms required near-
O
(
n
) time. We also present faster sequential algorithms that provide good approximate distances only between “distant” vertices: We obtain an

O((m + sn)n
ϵ0

time algorithm that computes paths of weight (1+
O
(1/polylog
n
) dist +
O
(
w
max
polylog
n
), where dist is the corresponding distance and
w
max
is the maximum edge weight. Our chief instrument, which is of independent interest, are efficient constructions of sparse
hop sets
. A (
d
,ϵ)-hop set of a network
G
=(
V,E
) is a set
E
* of new weighted edges such that mimimum-weight
d
-edge paths in (
V, E,
∪
E*
) have weight within (1+ϵ) of the respective distances in
G
. We construct hop sets of size
O
(n
1+ϵ0
) where ϵ=
O
(1/polylog
n
) and
d
=
O
(polylog
n
).
Relational queries over interpreted structures
Authors: Benedikt Michael , Libkin Leonid
Published: July 2002

We rework parts of the classical relational theory when the underlying domain is a structure with some interpreted operations that can be used in queries. We identify parts of the classical theory that go through 'as before' when interpreted structure is present, parts that go through only for classes of nicely behaved structures, and parts that only arise in the interpreted case. The first category include a number of results on language equivalence and expressive power characterizations for the active-domain semantics for a variety of logics. Under this semantics, quantifiers range over elements of a relational database. The main kind of results we prove here are
generic collapse
results: for generic queries, adding operations beyond order, does not give us extra power.

The second category includes results on the natural semantics, under which quantifiers range over the entire interpreted structure. We prove, for a variety of structures,
natural-active collapse
results, showing that using unrestricted quantification does not give us any extra power. Moreover, for a variety of structures, including the real field, we give a set of algorithms for eliminating unbounded quantifications in favor of bounded ones. Furthermore, we extend these collapse results to a new class of higher-order logics that mix unbounded and bounded quantification. We give a set of normal forms for these logics, under special conditions on the interpreted structures. As a by-product, we obtain an elementary proof of the fact that parity test is not definable in the relational calculus with polynomial inequality constraints. We also give examples of structures with nice model-theoretic properties over which the natural-active collapse fails.
Cryptographic sealing for information secrecy and authentication
Authors: Gifford David K.
Published: July 2002

A new protection mechanism is described that provides general primitives for protection and authentication. The mechanism is based on the idea of sealing an object with a key. Sealed objects are self-authenticating, and in the absence of an appropriate set of keys, only provide information about the size of their contents. New keys can be freely created at any time, and keys can also be derived from existing keys with operators that include
Key-And
and
Key-Or
. This flexibility allows the protection mechanism to implement common protection mechanisms such as capabilities, access control lists, and information flow control. The mechanism is enforced with a synthesis of conventional cryptography, public-key cryptography, and a threshold scheme.
Reciprocal hashing
Authors: Jaeschke G.
Published: July 2002

A method is presented for building minimal perfect hash functions, i.e., functions which allow single probe retrieval from minimally sized tables of identifier sets. A proof of existence for minimal perfect hash functions of a special type (reciprocal type) is given. Two algorithms for determining hash functions of reciprocal type are presented and their practical limitations are discussed. Further, some application results are given and compared with those of earlier approaches for perfect hashing.
A model of shared DASD and multipathing
Authors: Bard Yonathan
Published: July 2002

This paper presents a model of an I/O subsystem in which devices can be accessed from multiple CPUs and/or via alternative channel and control unit paths. The model estimates access response times, given access rates for all CPU-device combinations. Central to the model's algorithm is the estimation of the rotational position sensing (RPS) miss probabilities by means of the maximum entropy principle.

Performance differences strongly favored the English-based editor.
A syntactic algorithm for peak detection in waveforms with applications to cardiography
Authors: Horowitz Steven L.
Published: July 2002

Peaks in a digitized waveform are detected by an algorithm incorporating piecewise linear approximation and tabular parsing techniques. Several parameters serve to identify the waveform context enabling accurate measurement of peak amplitude, duration, and shape. The algorithm is of sufficient speed to allow on-line real-time processing. An example of its application is demonstrated on an electrocardiogram.
Fixpoint approach to the theory of computation
Authors: Manna Zohar , Vuillemin Jean
Published: July 2002

Following the fixpoint theory of Scott, the semantics of computer programs are defined in terms of the least fixpoints of recursive programs. This allows not only the justification of all existing verification techniques, but also their extension to the handling, in a uniform manner of various properties of computer programs, including correctness, termination, and equivalence.
Complete answer aggregates for treelike databases
Authors: Meuss Holger , Schulz Klaus U.
Published: July 2002

The use of markup languages like SGML, HTML or XML for encoding the strucutre of documents or linguistic data has lead to many databases where entries are adequately described as trees. In this context querying formalisms are interesting that offer the possiblity to refer both to textual content and logical structure. We consider models where the strucutre specified in a query is not only used as a filter, but also for selecting and presenting different parts of the data. If answers are formalized as mapping from query nodes to the database, a simple enumeration of all mappings in the answer set will often suffer from the effect that many answers have common subparts. From a theoretical point of view this may lead to an exponential time complexity of the computation and presentation of all answers. Concentration on the language of so called tree queries—a variant and extension of Kilpeläinen's Tree Matching formalism—we introduce the notion of a “complete answer aggregate” for a given query. This new data strucutre offers a compact view of the set of all answer and supports active exploration of the ansewer space. Since complete answer aggregates use a powerful structure-sharing mechanism their maximal size is of order 𝒪(d•h•q) wheredandqrespectively denote the size of the database and the query, andhis the maximal depth of a path of the database. An algorithm is given that computes a complete answer aggregate for a given treee query in time 𝒪(d•log(d)•h•). For the sublanguage of so-called rigid tree queries, as well as for so-called “nonrecursive” databases, an improved bound of 𝒪(d•log(d)•q) is obtained. The algorithm is based on a specific index structure that supports practical efficiency.
Equivalence and optimization of relational transactions
Authors: Abiteboul Serge , Vianu Victor
Published: July 2002

A large class of relational database update transactions is investigated with respect to equivalence and optimization. The transactions are straight-line programs with inserts, deletes, and modifications using simple selection conditions. Several basic results are obtained. It is shown that transaction equivalence can be decided in polynomial time. A number of optimality criteria for transactions are then proposed, as well as two normal forms. Polynomial-time algorithms for transaction optimization and normalization are exhibited. Also, an intuitively appealing system of axioms for proving transaction equivalence is introduced. Finally, a simple, natural subclass of transactions, called strongly acyclic, is shown to have particularly desirable properties.
Notions of dependency satisfaction
Authors: Graham Marc H. , Mendelzon Alberto O. , Vardi Moshe Y.
Published: July 2002

Two notions of dependency satisfaction,
consistency
and
completeness
, are introduced. Consistency is the natural generalization of weak-instance satisfaction and seems appropriate when only equality-generating dependencies are given, but disagrees with the standard notion in the presence of tuple-generating dependencies. Completeness is based on the intuitive semantics of tuple-generating dependencies but differs from the standard notion for equality-generating dependencies. It is argued that neither approach is the
correct
one, but rather that they correspond to different policies on constraint enforcement, and each one is appropriate in different circumstances. Consistency and completeness of a state are characterized in terms of the tableau associated with the state and in terms of logical properties of a set of first-order sentences associated with the state. A close relation between the problems of testing for consistency and completeness and of testing implication of dependencies is established, leading to lower and upper bounds for the complexity of consistency and completeness. The possibility of formalizing dependency satisfaction without using a universal relation scheme is examined.
Static analysis in datalog extensions
Authors: Halevy Alon Y. , Mumick Inderpal Singh , Sagiv Yehoshua , Shmueli Oded
Published: July 2002

We consider the problems of containment, equivalence, satisfiability and query-reachability for datalog programs with negation. These problems are important for optimizing datalog programs. We show that both query-reachability and satisfiability are decidable for programs with stratified negation provided that negation is applied only to EDB predicates or that all EDB predicates are unary. In the latter case, we show that equivalence is also decidable. The algorithms we present can also be used to push constraints from a given query to the EDB predicates. In showing our decidability results we describe a powerful tool, the query-tree, which is used for several optimization problems for datalog programs. Finally, we show that satisfiability is undecidable for datalog programs with unary IDB predicates, stratified negation and the interpreted predicate ≠.
Optimization of join operations in horizontally partitioned database systems
Authors: Segev Arie
Published: July 2002

This paper analyzes the problem of joining two horizontally partitioned relations in a distributed database system. Two types of semijoin strategies are introduced, local and remote. Local semijoins are performed at the site of the restricted relation (or fragment), and remote semijoins can be performed at an arbitrary site. A mathematical model of a semijoin strategy for the case of remote semijoins is developed, and lower bounding and heuristic procedures are proposed. The results of computational experiments are reported. The experiments include an analysis of the heuristics' performance relative to the lower bounds, sensitivity analysis, and error analysis. These results reveal a good performance of the heuristic procedures, and demonstrate the benefit of using semijoin operations to reduce the size of fragments prior to their transmission. The algorithms for the case of remote semijoins were found to be superior to the algorithms for the case of local semijoins. In addition, we found that the estimation accuracy of the selectivity factors has a significant effect on the incurred communication cost.
Maintaining availability in partitioned replicated databases
Authors: Abbadi A. El , Toueg S.
Published: July 2002

In a replicated database, a data item may have copies residing on several sites. A replica control protocol is necessary to ensure that data items with several copies behave as if they consist of a single copy, as far as users can tell. We describe a new replica control protocol that allows the accessing of data in spite of site failures and network partitioning. This protocol provides the database designer with a large degree of flexibility in deciding the degree of data availability, as well as the cost of accessing data.
Query optimization in a memory-resident domain relational calculus database system
Authors: Whang Kyu-Young , Krishnamurthy Ravi
Published: July 2002

We present techniques for optimizing queries in memory-resident database systems. Optimization techniques in memory-resident database systems differ significantly from those in conventional disk-resident database systems. In this paper we address the following aspects of query optimization in such systems and present specific solutions for them: (1) a new approach to developing a CPU-intensive cost model; (2) new optimization strategies for main-memory query processing; (3) new insight into join algorithms and access structures that take advantage of memory residency of data; and (4) the effect of the operating system's scheduling algorithm on the memory-residency assumption. We present an interesting result that a major cost of processing queries in memory-resident database systems is incurred by evaluation of predicates. We discuss optimization techniques using the Office-by-Example (OBE) that has been under development at IBM Research. We also present the results of performance measurements, which prove to be excellent in the current state of the art. Despite recent work on memory-resident database systems, query optimization aspects in these systems have not been well studied. We believe this paper opens the issues of query optimization in memory-resident database systems and presents practical solutions to them.
NUCLEAR CONTROL OF PLASTID AND MITOCHONDRIAL DEVELOPMENT IN HIGHER PLANTS
Authors: Leon P. , Arroyo A. , Mackenzie S.
Published: July 2002

▪ Abstract  The nucleus must coordinate organelle biogenesis and function on a cell and tissue-specific basis throughout plant development. The vast majority of plastid and mitochondrial proteins and components involved in organelle biogenesis are encoded by nuclear genes. Molecular characterization of nuclear mutants has illuminated chloroplast development and function. Fewer mutants exist that affect mitochondria, but molecular and biochemical approaches have contributed to a greater understanding of this organelle. Similarities between organelles and prokaryotic regulatory molecules have been found, supporting the prokaryotic origin of chloroplasts and mitochondria. A striking characteristic for both mitochondria and chloroplast is that most regulation is posttranscriptional.
Uses of Evolutionary Theory in the Human Genome Project
Authors: Templeton Alan R.
Published: July 2002

▪ Abstract  The Human Genome Project (HGP) originally sought to sequence the human genome but excluded studies on genetic diversity. Now genetic diversity is a major focus, and evolutionary theory provides needed analytical tools. One type of diversity research focuses on complex traits. This is often done by screening genetic variation at candidate loci functionally related to a trait followed by gene/phenotype association tests. Linkage disequilibrium creates difficulties for association tests, but evolutionary analyses using haplotype trees can circumvent these problems and result in greater statistical power, better disease risk prediction, the elimination of some polymorphisms as causative, and physical localization of causative variation when combined with an analysis of recombination. The HGP also now proposes to map over 100,000 single nucleotide polymorphisms to test for gene/phenotype associations through linkage disequilibrium in isolated human populations affected by past founder or bottleneck events. This strategy requires prior knowledge of recent human evolutionary history and current population structure, but other evolutionary considerations dealing with disequilibrium and nonrandom mutation pose difficulties for this approach. Studies on population structure also focus upon traits of medical relevance, and an understanding of the evolutionary ultimate cause for the predisposition of some populations to certain diseases is a useful predictor for shaping public health policies. Studies on the genetic architecture of common traits reveal much epistasis and variation in norms of reaction, including drug response. Because of these interactions, context dependency and sampling bias exist in disease association studies that require population information for effective use. Overall, the population thinking of evolutionary biology is an important counterweight to naive genetic determinism in applying the results of the HGP to issues of human health and well-being.
METABOLIC INTERACTIONS OF DIABETES AND PREGNANCY
Authors: Buchanan, M.D Thomas A. , Kitzmiller, M.D John L.
Published: July 2002

▪ Abstract  Many of the embryonic and fetal abnormalities that occur in pregnancies complicated by maternal diabetes are the result of development in a metabolically abnormal environment. Diabetic embryopathy (birth defects and spontaneous abortions) results from maternal metabolic abnormalities during the first 6–7 weeks of gestation. The embryopathy appears to be multifactorial in origin, and the resulting defects remain important causes of morbidity and mortality in diabetic pregnancies. Diabetic fetopathy (predominantly macrosomia and neonatal hypoglycemia) results from fetal overnutrition and hyper-insulinemia during the second and third trimesters. Fetopathy may cause significant morbidity not only in the perinatal period, but also in later life as overweight infants grow up to be overweight children and young adults. Careful regulation of maternal metabolism from the preconceptional period onward can reduce greatly or even eliminate the excess risks that have been incurred by infants of diabetic mothers in the past. Successful management of maternal diabetes requires knowledge of the alterations in intermediary metabolism that normally occur during pregnancy, as discussed in this chapter.