bluuebunny/crossref_metadata_2025 huggingface dataset:
An implementation technique for database query languages
Authors: Buneman Peter , Frankel Robert E. , Nikhil Rishiyur
Published: July 2002

Structured query languages, such as those available for relational databases, are becoming increasingly desirable for all database management systems. Such languages are applicative: there is no need for an assignment or update statement. A new technique is described that allows for the implementation of applicative query languages against most commonly used database systems. The technique involves “lazy” evaluation and has a number of advantages over existing methods: it allows queries and functions of arbitrary complexity to be constructed; it reduces the use of secondary storage; it provides a simple control structure through which interfaces to other programs may be constructed; and the implementation, including the database interface, is quite compact. Although the technique is presented for a specific functional programming system and for a CODASYL DBMS, it is general and may be used for other query languages and database systems.
On the complexity of designing optimal partial-match retrieval systems
Authors: Moran Shlomo
Published: July 2002

We consider the problem of designing an information retrieval system on which partial match queries have to be answered. Each record in the system consists of a list of
attributes
, and a partial match query specifies the values of some of the attributes. The records are stored in
buckets
in a secondary memory, and in order to answer a partial match query all the buckets that may contain a record satisfying the specifications of that query must be retrieved. The bucket in which a given record is stored is found by a multiple key hashing function, which maps each attribute to a string of a fixed number of bits. The address of that bucket is then represented by the string obtained by concatenating the strings on which the various attributes were mapped. A partial match query may specify only part of the bits in the string representing the address, and the larger the number of bits specified, the smaller the number of buckets that have to be retrieved in order to answer the query.

The optimization problem considered in this paper is that of deciding to how many bits each attribute should be mapped by the bashing function above, so that the expected number of buckets retrieved per query is minimized. Efficient solutions for special cases of this problem have been obtained in [1], [12], and [14]. It is shown that in general the problem is NP-hard, and that if
P
≠ NP, it is also not fully approximable. Two heuristic algorithms for the problem are also given and compared.
Secure databases
Authors: Dobkin David , Jones Anita K. , Lipton Richard J.
Published: July 2002

Users may be able to compromise databases by asking a series of questions and then inferring new information from the answers. The complexity of protecting a database against this technique is discussed here.
EXPRESS
Authors: Shu N. C. , Housel B. C. , Taylor R. W. , Ghosh S. P. , Lum V. Y.
Published: July 2002

EXPRESS is an experimental prototype data translation system which can access a wide variety of data and restructure it for new uses. The system is driven by two very high level nonprocedural languages: DEFINE for data description and CONVERT for data restructuring. Program generation and cooperating process techniques are used to achieve efficient operation.

This paper describes the design and implementation of EXPRESS. DEFINE and CONVERT are summarized and the implementation architecture presented.

The DEFINE description is compiled into a customized PL/1 program for accessing source data. The restructuring specified in CONVERT is compiled into a set of customized PL/1 procedures to derive multiple target files from multiple input files. Job steps and job control statements are generated automatically. During execution, the generated procedures run under control of a process supervisor, which coordinates buffer management and handles file allocation, deallocation, and all input/output requests.

The architecture of EXPRESS allows efficiency in execution by avoiding unnecessary secondary storage references while at the same time allowing the individual procedures to be independent of each other. Its modular structure permits the system to be extended or transferred to another environment easily.
Secure statistical databases with random sample queries
Authors: Denning Dorothy E.
Published: July 2002

A new inference control, called random sample queries, is proposed for safeguarding confidential data in on-line statistical databases. The random sample queries control deals directly with the basic principle of compromise by making it impossible for a questioner to control precisely the formation of query sets. Queries for relative frequencies and averages are computed using random samples drawn from the query sets. The sampling strategy permits the release of accurate and timely statistics and can be implemented at very low cost. Analysis shows the relative error in the statistics decreases as the query set size increases; in contrast, the effort required to compromise increases with the query set size due to large absolute errors. Experiments performed on a simulated database support the analysis.
Fast Multiple-Precision Evaluation of Elementary Functions
Authors: Brent Richard P.
Published: July 2002

Let ƒ(
x
) be one of the usual elementary functions (exp, log, artan, sin, cosh, etc.), and let
M
(
n
) be the number of single-precision operations required to multiply
n
-bit integers. It is shown that ƒ(
x
) can be evaluated, with relative error
Ο
(2

-
n

), in
Ο
(
M
(
n
)log (
n
)) operations as
n
→ ∞, for any floating-point number
x
(with an
n
-bit fraction) in a suitable finite interval. From the Schönhage-Strassen bound on
M
(
n
), it follows that an
n
-bit approximation to ƒ(
x
) may be evaluated in
Ο
(
n
log
2
(
n
) log log(
n
)) operations. Special cases include the evaluation of constants such as π,
e
, and
e
π
. The algorithms depend on the theory of elliptic integrals, using the arithmetic-geometric mean iteration and ascending Landen transformations.
A Statistical Model for Relevance Feedback in Information Retrieval
Authors: Yu C. T. , Luk W. S. , Cheung T. Y.
Published: July 2002

A statistical model is presented for the investigation of a practical method used in relevance feedback. A necessary and sufficient condition for the two parameters used in this method to define a better query than the original query is given. A region in the plane of the parameters is shown to satisfy the sufficient condition. While the points for producing optimal queries are not exactly located, they are shown to be lying on a finite portion of a hyperbola. Experimental results support some of the theoretical findings.
A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Matrices
Authors: Schmidt Douglas C. , Druffel Larry E.
Published: July 2002

A backtracking algorithm for testing a pair of digraphs for isomorphism is presented. The information contained in the distance matrix representation of a graph is used to establish an initial partition of the graph's vertices. This distance matrix information is then applied in a backtracking procedure to reduce the search tree of possible mappings. While the algorithm is not guaranteed to run in polynomial time, it performs efficiently for a large class of graphs.
Corrigenda: a hierarchy-aware approach to faceted classification of object-oriented components
Authors: Damiani E. , Fugini M. G. , Bellettini C.
Published: July 2002

This article presents a hierarchy-aware classification schema for object-oriented code, where software components are classified according to their
behavioral characteristics
, such as provided services, employed algorithms, and needed data. In the case of reusable application frameworks, these characteristics are constructed from their
model
, i.e., from the description of the abstract classes specifying both the framework structure and purpose. In conventional object libraries, the characteristics are extracted semiautomatically from class interfaces. Characteristics are term pairs, weighted to represent "how well" they describe component behavior. The set of characteristics associated with a given component forms its
software descriptor
. A descriptor base is presented where descriptors are organized on the basis of structured relationships, such as similarity and composition. The classification is supported by a thesaurus acting as a language-independent unified lexicon. The descriptor base is conceived for developers who, besides conventionally browsing the descriptors hierarchy, can query the system, specifying a set of desired functionalities and getting a ranked set of adaptable candidates. User feedback is taken into account in order to progressively ameliorate the quality of the descriptors according to the views of the user community. Feedback is made dependent of the user typology through a
user profile
. Experimental results in terms of recall and precision of the retrieval mechanism against a sample code base are reported.
DISCIPLE
Authors: Marsic Ivan
Published: July 2002

This paper presents a framework for sharing JavaBeans applications in real-time synchronous collaboration. A generic collaboration bus provides a plug-and-play environment that enables collaboration with applications that may or may not be collaboration aware. Research on knowledge-based quality-of-service management and multimodel human/machine interface is described.
Balanced sequences and optimal routing
Authors: Altman Eitan , Gaujal Bruno , Hordijk Arie
Published: July 2002

The objective pursued in this paper is two-fold. The first part addresses the following combinatorial problem: is it possible to construct an infinite sequence over
n
letters where each letter is distributed as “evenly” as possible and appears with a given rate? The second objective of the paper is to use this construction in the framework of optimal routing in queuing networks. We show under rather general assumptions that the optimal deterministic routing in stochastic event graphs is such a sequence.
Synthesis of low-power selectively-clocked systems from high-level specification
Authors: Benini L. , De Micheli G.
Published: July 2002

We propose a technique for synthesizing low-power systems from behavioral specifications. We analyze the control flow of the specification model to detect mutually exclusive sections of the computation. A
selectively-clocked
interconnection of interacting FSMs is automatically generated and optimized, where each FSM controls the execution of one section of computation. Only one of the interacting FSMs is active for a high fraction of the operation time, while the others are idle and their clocks are stopped. Periodically, the active machine releases the control of the system to another FSM and stops. Our interacting FSM implementation achieves consistently lower power dissipation than the functionally equivalent monolithic implementation. On average, 37% power savings and 12% speedup are obtained, despite a 30% area overhead.
Recovery management in QuickSilver
Authors: Haskin Rober , Malachi Yoni , Chan Gregory
Published: July 2002

This paper describes QuickSilver, developed at the IBM Almaden Research Center, which usesatomic transactionsas a unified failure recovery mechanism for a client-server structured distributed system. Transactions allow failure atomicity for related activities at a single server or at a number of independent servers. Rather than bundling transaction management into a dedicated language or recoverable object manager, Quicksilver exposes the basic commit protocol and log recovery primitives, allowing clients and servers to tailor their recovery techniques to their specific needs. Servers can implement their own log recovery protocols rather than being required to use a system-defined protocol. These decisions allow servers to make their own choices to balance simplicity, efficiency, and recoverability.
An enhanced treatment of hidden lines
Authors: Kamada Tomihisa , Kawai Satoru
Published: July 2002

A new display scheme is presented in which three-dimensional objects are represented with a much higher degree of user control of the line-drawing format than those in conventional schemes. In this scheme, the attribute of a line is determined not at the time of definition but after the viewing transformation has been applied, taking the shielding environment of the line into consideration. The essential difference between our scheme and conventional hidden-line removal/indication lies in the treatment of the shielding environment. In conventional hidden-line removal/indication, only the visible/invisible information is available for the selection of the attribute of a line. In our scheme, the entire set of surfaces that hide a line can be used to determine the attribute of the line. A much higher degree of freedom in generating pictures is achieved owing to the treatment of the shielding environment. We also describe a system called GRIP, which implements the new scheme.
File organization
Authors: Larson Per-Åke , Kajla Ajay
Published: July 2002

A new file organization method that guarantees retrieval of any record in one access is tested on two existing files, producing empirical results that compare favorably with theoretical predictions. The description of the method includes the algorithms used for implementing the required hashing and signature functions.
Faster methods for random sampling
Authors: Vitter Jeffrey Scott
Published: July 2002

Several new methods are presented for selecting n records at random without replacement from a file containing N records. Each algorithm selects the records for the sample in a sequential manner—in the same order the records appear in the file. The algorithms are online in that the records for the sample are selected iteratively with no preprocessing. The algorithms require a constant amount of space and are short and easy to implement. The main result of this paper is the design and analysis of Algorithm D, which does the sampling in O
(
n
)

time, on the average; roughly n uniform random variates are generated, and approximately n exponentiation operations (of the form a
b
, for real numbers a and b) are performed during the sampling. This solves an open problem in the literature. CPU timings on a large mainframe computer indicate that Algorithm D is significantly faster than the sampling algorithms in use today.
Operations on sparse relations
Authors: Hunt H. B. , Ullman J. D. , Szymanski T. G.
Published: July 2002

Various computations on relations, Boolean matrices, or directed graphs, such as the computation of precedence relations for a context-free grammar, can be done by a practical algorithm that is asymptotically faster than those in common use. For example, how to compute operator precedence or Wirth-Weber precedence relations in O(n
2
) steps is shown, as well as how to compute linear precedence functions in O(n) steps, where n is the size of a grammar. The heart of the algorithms is a general theorem giving sufficient conditions under which an expression whose operands are sparse relations and whose operators are composition, transitive closure, union, and inverse, can be computed efficiently.
Some basic determinants of computer programming productivity
Authors: Chrysler Earl
Published: July 2002

The purpose of this research was to examine the relationship between processing characteristics of programs and experience characteristics of programmers and program development time. The ultimate objective was to develop a technique for predicting the amount of time necessary to create a computer program. The fifteen program characteristics hypothesized as being associated with an increase in programming time required are objectively measurable from preprogramming specifications. The five programmer characteristics are experience-related and are also measurable before a programming task is begun. Nine program characteristics emerged as major influences on program development time, each associated with increased program development time. All five programmer characteristics were found to be related to reduced program development time. A multiple regression equation which contained one programmer characteristic and four program characteristics gave evidence of good predictive power for forecasting program development time.
Implementing Quicksort programs
Authors: Sedgewick Robert
Published: July 2002

This paper is a practical study of how to implement the Quicksort sorting algorithm and its best variants on real computers, including how to apply various code optimization techniques. A detailed implementation combining the most effective improvements to Quicksort is given, along with a discussion of how to implement it in assembly language. Analytic results describing the performance of the programs are summarized. A variety of special situations are considered from a practical standpoint to illustrate Quicksort's wide applicability as an internal sorting method which requires negligible extra storage.
Pagination of B*-trees with variable-length records
Authors: McCreight Edward M.
Published: July 2002

A strategy is presented for pagination of B
*
-trees with variable-length records. If records of each length are uniformly distributed within the file, and if a wide distribution of record lengths exists within the file, then this strategy results in shallow trees with fast access times. The performance of this strategy in an application is presented, compared with that of another strategy, and analyzed.
Permutation enumeration
Authors: Ives F. M.
Published: July 2002

Classical permutation enumeration algorithms encounter special cases requiring additional computation every nth permutation when generating the n! permutations on n marks. Four new algorithms have the attribute that special cases occur every n(n—1) permutations. Two of the algorithms produce the next permutation with a single exchange of two marks. The other two algorithms infrequently exchange more than two marks, but the rules for generating the next permutation are very simple. Performance tests which have counted execution of assignment statements, comparisons, arithmetic operations, and subscripted array references have shown superiority of the new algorithms compared to Boothroyd's implementation of M.B. Well's algorithm and Ehrlich's implementation of the Johnson-Trotter algorithm.
A comparative evaluation of versions of BASIC
Authors: Lientz Bennet P.
Published: July 2002

From its inception, The BASIC language has grown in terms of its usage, scope of usage, and its features. This article compares ten of the current versions of BASIC with each other, with two earlier versions, and with the proposed standard for minimal BASIC. The comparison is arranged by the features of the versions and by computational comparison of computation and times and processing costs.
Computer-assigned codes from verbal responses
Authors: O'Reagan Robert T.
Published: July 2002

It is often desirable to convert verbal responses to multidigit codes. This conversion is generally accomplished by clerk-coders. A study was conducted to test the feasibility of translating verbal descriptions to numerical codes in a computer program. Primary emphasis was placed on computerized construction of a reference file of verbal descriptions for use by the program. The results of the study clearly show that such procedures are feasible.
An array grammar programming system
Authors: Mercer Andrew , Rosenfeld Azriel
Published: July 2002

A package of Fortran programs has been developed that permits a user to interactively design and test array grammars. The user can control the rule selection procedure in a derivation or parse, using weighted programming matrices; he also has a choice of instance selection schemes (raster, random, parallel). Examples are given involving array languages consisting of simple geometrical patterns, as well as a language of “neuron pictures.”
Generation of Rosary permutations expressed in Hamiltonian circuits
Authors: Harada Kazuaki
Published: July 2002

Systematic generation of a specific class of permutations fundamental to scheduling problems is described.

In a nonoriented complete graph with
n
vertices, Hamiltonian circuits equivalent to 1/2(
n
- 1)! specific permutations of
n
elements, termed rosary permutations, can be defined. Each of them corresponds to two circular permutations which mirror-image each other, and is generated successively by a number system covering 3·4· ··· ·(
n
- 1) sets of edges. Every set of edges {

e
k

}, 1 ≤

e
k

≤
k
, 3 ≤
k
≤
n
- 1 is determined recursively by constructing a Hamiltonian circuit with
k
vertices from a Hamiltonian circuit with
k
- 1 vertices, starting with the Hamiltonian circuit of 3 vertices. The basic operation consists of transposition of a pair of adjacent vertices where the position of the pair in the permutation is determined by {

e
k

}. Two algorithms treating the same example for five vertices are presented.

It is very easy to derive all possible
n
! permutations from the 1/2(
n
- 1)! rosary permutations by cycling the permutations and by taking them in the reverse order—procedures which can be performed fairly efficiently by computer.
Adversarial queuing theory
Authors: Borodin Allan , Kleinberg Jon , Raghavan Prabhakar , Sudan Madhu , Williamson David P.
Published: July 2002

We consider packet routing when packets are injected continuously into a network. We develop an adversarial theory of queuing aimed at addressing some of the restrictions inherent in probabilistic analysis and queuing theory based on time-invariant stochastic generation. We examine the stability of queuing networks and policies when the arrival process is adversarial, and provide some preliminary results in this direction. Our approach sheds light on various queuing policies in simple networks, and paves the way for a systematic study of queuing with few or no probabilistic assumptions.
Symbolic analysis methods for information systems
Authors: Chapin Ned
Published: July 2002

The purpose of this research in the area of information systems is basically twofold: (1) to produce new techniques of systems analysis and systems design that will be free of many of the defects of present techniques, and (2) to program a general purpose computer to enable it to apply at least major parts of these new techniques, in a way that will enable a linkage with automatic coding techniques. The major defects of the present techniques are high cost, low validity, low reliability, heavy reliance upon intuition and experience, and slow speed of effective application.
The state of digital computer technology in Europe
Authors: Blachman Nelson M.
Published: July 2002

This report indicates the level of computer development and application in each of the thirty countries of Europe, most of which were recently visited by the author
An exponential method of numerical integration of ordinary differential equations
Authors: Pope David A.
Published: July 2002

A formula for numerical integration is prepared, which involves an exponential term. This formula is compared to two standard integration methods, and it is shown that for a large class of differential equations, the exponential formula has superior stability properties for large step sizes. Thus this formula may be used with a large step size to decrease the total computing time for a solution significantly, particularly in those engineering problems where high accuracy is not needed.
Least squares fitting of a great circle through points on a sphere
Authors: De Witte Leendert
Published: July 2002

version of itself which, running as a COUNTESS program, generated machine code for the Control Data Corporation CDC-1604 computer. This second compiler was then used to generate a version of NELIAC for the CDC-1604. All three versions of NELIAC accepted essentially identical input language.
Pei matrix eigenvectors
Authors: Newbery A. C. R.
Published: July 2002

M. L. Pei [
Comm. ACM 5
, 10 (Oct. 1962)] gave an explicit inverse for a matrix of the form
M
+
δI
, where
M
is an
n
-square matrix of ones and
δ
is a nonzero parameter. The eigenvalues of the Pei matrix were given by W. S. LaSor [
Comm. ACM 6
, 3 (Mar. 1963)]. The eigenvectors may be obtained by considering the system (
M
+
δI
)
x
= λ
x
, the
j
th equation of which is
S
+

δx
j

= λ

x
j

, (1) where
S
denotes Σ

n

i
=1

x
i

. On summing the equations for
j
= 1, 2, … ,
n
, we obtain
nS
+
δS
= λ
S
. From this we conclude that (a)
S
= 0 or (b) λ =
n
+
δ
.
Applying an update method to a set of receivers
Authors: Andries Marc , Cabibbo Luca , Paredaens Jan , van den Bussche Jan
Published: July 2002

In the context of object databases, we study the application of an update method to a collection of receivers rather than to a single one. The obvious strategy of applying the update to the receivers one after the other, in some arbitrary order, brings up the problem of order independence. On a very general level, we investigate how update behavior can be analyzed in terms of certain schema annotations, called colorings. We are able to characterize those colorings that always describe order-independedent updates. We also consider a more specific model of update methods implemented in the relational algebra. Order-independence of such algebraic methods is undecidable in general, but decidable if the expressions used are positive. Finally, we consider an alternative parallel strategy for set-oriented applications of algebraic update methods and compare and relate it to the sequential strategy.
Enhanced operational semantics
Authors: Degano Pierpaolo , Priami Corrado
Published: July 2002

This article surveys the definition and application of an enhancement of structural operational semantics in the field of concurrent systems, and also addresses issues of distribution and mobility of code. The focus is on how enriching the labels of transitions with encodings of their deduction trees is sufficient to derive qualitative and quantitative information on the systems in hand simply by relabeling the transitions of a unique concrete model.
External hashing with limited internal storage
Authors: Gonnet Gaston H. , Larson Per-Åke
Published: July 2002

The following problem is studied: How, and to what extent, can the retrieval speed of external hashing be improved by storing a small amount of extra information in internal storage? Several algorithms that guarantee retrieval in one access are developed and analyzed. In the first part of the paper, a restricted class of algorithms is studied, and a lower bound on the amount of extra storage is derived. An algorithm that achieves this bound, up to a constant difference, is also given. In the second part of the paper a number of restrictions are relaxed and several more practical algorithms are developed and analyzed. The last one, in particular, is very simple and efficient, allowing retrieval in one access using only a fixed number of bits of extra internal storage per bucket. The amount of extra internal storage depends on several factors, but it is typically very small: only a fraction of a bit per record stored. The cost of inserting a record is also analyzed and found to be low. Taking all factors into account, this algorithm is highly competitive for applications requiring very fast retrieval.
Linear hashing with separators—a dynamic hashing scheme achieving one-access
Authors: Larson Per-Ake
Published: July 2002

A new dynamic hashing scheme is presented. Its most outstanding feature is that any record can be retrieved in exactly one disk access. This is achieved by using a small amount of supplemental internal storage that stores enough information to uniquely determine the current location of any record. The amount of internal storage required is small: typically one byte for each page of the file. The necessary address computation, insertion, and expansion algorithms are presented and the performance is studied by means of simulation. The new method is the first practical method offering one-access retrieval for large dynamic files.
An application of number theory to the organization of raster-graphics memory
Authors: Chor Benny , Leiserson Charles E. , Rivest Ronald L. , Shearer James B.
Published: July 2002

A high-resolution raster-graphics display is usually combined with processing power and a memory organization that facilitates basic graphics operations. For many applications, including interactive text processing, the ability to quickly move or copy small rectangles of pixels is essential. This paper proposes a novel organization of raster-graphics memory that permits all small rectangles to be moved efficiently. The memory organization is based on a doubly periodic assignment of pixels to
M
memory chips according to a “Fibonacci” lattice. The memory organization guarantees that, if a rectilinearly oriented rectangle contains fewer than
M
/ @@@@5 pixels, then all pixels will reside in different memory chips and thus can be accessed simultaneously. Moreover, any
M
consecutive pixels, arranged either horizontally or vertically, can be accessed simultaneously.

We also define a continuous analog of the problem, which can be posed as: “What is the maximum density of a set of points in the plane such that no two points are contained in the interior of a rectilinearly oriented rectangle of unit area?” We show the existence of such a set with density 1/ @@@@5, and prove this is optimal by giving a matching upper bound.
Special relations in automated deduction
Authors: Manna Zohar , Waldinger Richard
Published: July 2002

Two deduction rules are introduced to give streamlined treatment to relations of special importance in an automated theorem-proving system. These rules, the
relation replacement
and
relation matching
rules, generalize to an arbitrary binary relation the paramodulation and E-resolution rules, respectively, for equality, and may operate within a nonclausal or clausal system. The new rules depend on an extension of the notion of
polarity
to apply to subterms as well as to subsentences, with respect to a given binary relation. The rules allow us to eliminate troublesome axioms, such as transitivity and monotonicity, from the system; proofs are shorter and more comprehensible, and the search space is correspondingly deflated.
A simple bounded disorder file organization with good performance
Authors: Lomet David B.
Published: July 2002

A bounded-disorder (BD) file is one in which data are organized into nodes that are indexed, e.g., by means of a B-tree. The data nodes are multibucket nodes that are accessed by hashing. In this paper we present two important improvements to the BD organization as originally described. First, records in a data node that overflow their designated primary bucket are stored in a single overflow bucket which is itself a bucket of the data node. Second, when file space needs to be increased, partial expansions are used that employ elastic buckets. Analysis and simulation results demonstrate that this variant of the BD organization has utilization, random access performance, and file growth performance that can be competitive with good extendible hashing methods, while supporting high-performance sequential access. The simplicity of the organization results in simple algorithms for realizing the organization.
Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation
Authors: Driscoll James R. , Gabow Harold N. , Shrairman Ruth , Tarjan Robert E.
Published: July 2002

The relaxed heap is a priority queue data structure that achieves the same amortized time bounds as the Fibonacci heap—a sequence of m decrease_key and n delete_min operations takes time O(m + n log n). A variant of relaxed heaps achieves similar bounds in the worst case—O(1) time for decrease_key and O(log n) for delete_min. Relaxed heaps give a processor-efficient parallel implementation of Dijkstra's shortest path algorithm, and hence other algorithms in network optimization. A relaxed heap is a type of binomial queue that allows heap order to be violated.
Answering queries with useful bindings
Authors: Li Chen , Chang Edward
Published: July 2002

In information-integration systems, sources may have diverse and limited query capabilities. To obtain maximum information from these restrictive sources to answer a query, one can access sources that are not specified in the query (i.e., off-query sources). In this article, we propose a query-planning framework to answer queries in the presence of limited access patterns. In the framework, a query and source descriptions are translated to a recursive datalog program. We then solve optimization problems in this framework, including how to decide whether accessing off-query sources is necessary, how to choose useful sources for a query, and how to test query containment. We develop algorithms to solve these problems, and thus construct an efficient program to answer a query.
Interval arithmetic
Authors: Hickey T. , Ju Q. , Van Emden M. H.
Published: July 2002

We start with a mathematical definition of a real interval as a closed, connected set of reals. Interval arithmetic operations (addition, subtraction, multiplication, and division) are likewise defined mathematically and we provide algorithms for computing these operations assuming exact real arithmetic. Next, we define interval arithmetic operations on intervals with IEEE 754 floating point endpoints to be sound and optimal approximations of the real interval operations and we show that the IEEE standard's specification of operations involving the signed infinities, signed zeros, and the exact/inexact flag are such as to make a correct and optimal implementation more efficient. From the resulting theorems, we derive data that are sufficiently detailed to convert directly to a program for efficiently implementing the interval operations. Finally, we extend these results to the case of general intervals, which are defined as connected sets of reals that are not necessarily closed.
Uncovering the new wireless interaction paradigm
Authors: Sacher Heiko , Loudon Gareth
Published: July 2002

The always connected, mobile consumer is closer to reality than ever before. Ericsson expects the world-wide number of mobile phones to exceed landline phones by 2002 and that there will be more mobile Internet subscribers than fixed Internet subscribers by 2003 (Ericsson Annual Report, 2000). The potential of advanced wireless networks far surpasses today's mobile extensions of PC and Internet applications. But these new applications are not yet clear. Leveraging competence in customer research and interaction design, the human-computer interaction (HCI) community is, therefore, in the perfect position to address a key need of this industry: new application discovery.
On a model of indexability and its bounds for range queries
Authors: Hellerstein Joseph M. , Koutsoupias Elias , Miranker Daniel P. , Papadimitriou Christos H. , Samoladas Vasilis
Published: July 2002

We develop a theoretical framework to characterize the hardness of indexing data sets on block-access memory devices like hard disks. We define an indexing workload by a data set and a set of potential queries. For a workload, we can construct an indexing scheme, which is a collection of fixed-sized subsets of the data. We identify two measures of efficiency for an indexing scheme on a workload:
storage redundancy, r
(how many times each item in the data set is stored), and
access overhead, A
(how many times more blocks than necessary does a query retrieve).For many interesting families of workloads, there exists a trade-off between storage redundancy and access overhead. Given a desired access overhead
A
, there is a minimum redundancy that any indexing scheme must exhibit. We prove a lower-bound theorem for deriving the minimum redundancy. By applying this theorem, we show interesting upper and lower bounds and trade-offs between
A
and
r
in the case of multidimensional range queries and set queries.
Expressiveness of structured document query languages based on attribute grammars
Authors: Neven Frank , Van Den Bussche Jan
Published: July 2002

Structured document databases can be naturally viewed as derivation trees of a context-free grammar. Under this view, the classical formalism of attribute grammars becomes a formalism for structured document query languages. From this perspective, we study the expressive power of BAGs: Boolean-valued attribute grammars with propositional logic formulas as semantic rules, and RAGs: relation-valued attribute grammars with first-order logic formulas as semantic rules. BAGs can express only unary queries; RAGs can express queries of any arity. We first show that the (unary) queries expressible by BAGs are precisely those definable in monadic second-order logic. We then show that the queries expressible by RAGs are precisely those definable by first-order inductions of linear depth, or, equivalently, those computable in linear time on a parallel machine with polynomially many processors. Further, we show that RAGs that only use synthesized attributes are strictly weaker than RAGs that use both synthesized and inherited attributes. We show that RAGs are more expressive than monadic second-order logic for queries of any arity. Finally, we discuss relational attribute grammars in the context of BAGs and RAGs. We show that in the case of BAGs this does not increase the expressive power, while different semantics for relational RAGs capture the complexity classes NP, coNP and UP ∩ coUP.
Maintaining state constraints in relational databases: a proof theoretic basis
Authors: McCune William W. , Henschen Lawrence J.
Published: July 2002

If a relational database is required to satisfy a set of integrity constraints, then when the database is updated, one must ensure that it continues to satisfy the constraints. It is desirable not to have to evaluate each constraint after each update. A method is described that takes a constraint
C
and a class of updates, and either proves that an update in the class cannot violate
C
, or produces a formula
C'
(a complete test) that is satisfied before the update if and only if
C
would continue to be satisfied were the update to occur.
C'
is frequently much easier to evaluate than
C
. In addition, a formula
D
(a sufficient test) is sometimes produced such that if
D
is satisfied before the update, then
C
would continue to be satisfied were the update to occur. The method is proved correct. The method is substantially more general than other reported techniques for this problem. The method has been implemented, and a number of experiments with the implementation are presented.
Security problems on inference control for SUM, MAX, and MIN queries
Authors: Chin Francis
Published: July 2002

The basic inference problem is defined as follows: For a finite set
X
= {
x
i
, … ,

x
n

}, we wish to infer properties of elements of
X
on the basis of sets of "queries" regarding subsets of
X
. By restricting these queries to statistical queries, the statistical database (SDB) security problem is obtained. The security problem for the SDB is to limit the use of the SDB so that only statistical information is available and no sequence of queries is sufficient to infer protected information about any individual. When such information is obtained the SDB is said to be compromised. In this paper, two applications concerning the security of the SDB are considered:

On-line application
. The queries are answered one by one in sequence and it is necessary to determine whether the SDB is compromised if a new query is answered.

Off-line application
. All queries are available at the same time and it is necessary to determine the maximum subset of queries to be answered without compromising the SDB.

The complexity of these two applications, when the set of queries consists of (a) a single type of SUM query, (b) a single type of MAX/MIN query, (c) mixed types of MAX and MIN queries, (d) mixed types of SUM and MAX/MIN queries, and (e) mixed types of SUM, MAX, and MIN queries, is studied. Efficient algorithms are designed for some of these situations while others are shown to be NP-hard.
Predicting fill for sparse orthogonal factorization
Authors: Coleman Thomas F. , Edenbrandt Anders , Gilbert John R.
Published: July 2002

In solving large sparse linear least squares problems
A
x ≃ b, several different numeric methods involve computing the same upper triangular factor
R
of
A
. It is of interest to be able to compute the nonzero structure of
R
, given only the structure of
A
. The solution to this problem comes from the theory of matchings in bipartite graphs. The structure of
A
is modeled with a bipartite graph, and it is shown how the rows and columns of
A
can be rearranged into a structure from which the structure of its upper triangular factor can be correctly computed. Also, a new method for solving sparse least squares problems, called block back-substitution, is presented. This method assures that no unnecessary space is allocated for fill, and that no unnecessary space is needed for intermediate fill.
Asymptotic expansions for closed Markovian networks with state-dependent service rates
Authors: Mitra Debasis , McKenna J.
Published: July 2002

A method is presented for calculating the partition function, and from it, performance measures, for closed Markovian stochastic networks with queuing centers in which the service or processing rate depends on the center's state or load. The analysis on which this method is based is new and a major extension of our earlier work on load-independent queuing networks. The method gives asymptotic expansions for the partition function in powers of 1/
N
, where
N
is a parameter that reflects the size of the network. The expansions are particularly useful for large networks with many classes, each class having many customers. The end result is a decomposition by which expansion coefficients are obtained exactly by linear combinations of partition function values of small network constructs called pseudonetworks. Effectively computable bounds are given for errors arising from the use of a finite number of expansion terms. This method is important because load dependence is at once an essential element of sophisticated network models of computers, computer communications, and switching, teletraffic, and manufacturing systems, and the cause of very intensive computations in conventional techniques. With this method, very large load-dependent networks can be analyzed, whereas previously only small networks were computationally tractable.
Normalization of relations and PROLOG
Authors: Ceri S. , Gottlob G.
Published: July 2002

A program for the normalization of relations that is written in Prolog has several advantages relative to programs written in conventional programming languages: notably, conciseness and clarity. The program presented here implements several normalization algorithms and is suitable for the interactive design of small database applications and as a teaching aid.
Low cost management of replicated data in fault-tolerant distributed systems
Authors: Joseph Thomas A. , Birman Kenneth P.
Published: July 2002

Many distributed systems replicate data for fault tolerance or availability. In such systems, a logical update on a data item results in a physical update on a number of copies. The synchronization and communication required to keep the copies of replicated data consistent introduce a delay when operations are performed. In this paper, we describe a technique that relaxes the usual degree of synchronization, permitting replicated data items to be updated concurrently with other operations, while at the same time ensuring that correctness is not violated. The additional concurrency thus obtained results in better response time when performing operations on replicated data. We also discuss how this technique performs in conjunction with a roll-back and a roll-forward failure recovery mechanism.
Tree rebalancing in optimal time and space
Authors: Stout Q. F , Warren B. L
Published: July 2002

A simple algorithm is given which takes an arbitrary binary search tree and rebalances it to form another of optimal shape, using time linear in the number of nodes and only a constant amount of space (beyond that used to store the initial tree). This algorithm is therefore optimal in its use of both time and space. Previous algorithms were optimal in at most one of these two measures, or were not applicable to all binary search trees. When the nodes of the tree are stored in an array, a simple addition to this algorithm results in the nodes being stored in sorted order in the initial portion of the array, again using linear time and constant space.
Online help systems
Authors: Houghton Raymond C.
Published: July 2002

Users of computer systems are now accustomed to the convenience of online help systems and generally demand these amenities in the computers they buy. However, recent studies as to the efficacy of certain types of assistance for certain classes of users raise important questions for designers.
Modeling for text compression
Authors: Bell Timothy , Witten Ian H. , Cleary John G.
Published: July 2002

The best schemes for text compression use large models to help them predict which characters will come next. The actual next characters are coded with respect to the prediction, resulting in compression of information. Models are best formed adaptively, based on the text seen so far. This paper surveys successful strategies for adaptive modeling that are suitable for use in practical text compression systems.

The strategies fall into three main classes: finite-context modeling, in which the last few characters are used to condition the probability distribution for the next one; finite-state modeling, in which the distribution is conditioned by the current state (and which subsumes finite-context modeling as an important special case); and dictionary modeling, in which strings of characters are replaced by pointers into an evolving dictionary. A comparison of different methods on the same sample texts is included, along with an analysis of future research directions.
Dynamic voting algorithms for maintaining the consistency of a replicated database
Authors: Jajodia S. , Mutchler David
Published: July 2002

There are several replica control algorithms for managing replicated files in the face of network partitioning due to site or communication link failures. Pessimistic algorithms ensure consistency at the price of reduced availability; they permit at most one (distinguished) partition to process updates at any given time. The best known pessimistic algorithm,
voting
, is a “static” algorithm, meaning that all potential distinguished partitions can be listed in advance. We present a dynamic extension of voting called
dynamic voting
. This algorithm permits updates in a partition provided it contains more than half of the
up-to-date
copies of the replicated file. We also present an extension of dynamic voting called
dynamic voting with linearly ordered copies
(abbreviated as
dynamic-linear
). These algorithms are dynamic because the order in which past distinguished partitions were created plays a role in the selection of the next distinguished partition. Our algorithms have all the virtues of ordinary voting, including its simplicity, and provide improved availability as well. We provide two stochastic models to support the latter claim. In the first (site) model, sites may fail but communication links are infallible; in the second (link) model the reverse is true. We prove that under the site model, dynamic-linear has greater availability than any static algorithm, including weighted voting, if there are four or more sites in the network. In the link model, we consider all biconnected five-site networks and a wide variety of failure and repair rates. In all cases considered, dynamic-linear had greater availability than any static algorithm.