bluuebunny/crossref_metadata_2025 huggingface dataset:
A comparison of high-availability media recovery techniques
Authors: Copeland George , Keller Tom
Published: November 2005

We compare two high-availability techniques for recovery from media failures in database systems. Both techniques achieve high availability by having two copies of all data and indexes, so that recovery is immediate. “Mirrored declustering” spreads two copies of each relation across two identical sets of disks. “Interleaved declustering” spreads two copies of each relation across one set of disks while keeping both copies of each tuple on separate disks. Both techniques pay the same costs of doubling storage requirements and requiring updates to be applied to both copies.

Mirroring offers greater simplicity and universality. Recovery can be implemented at lower levels of the system software (e.g., the disk controller). For architectures that do not share disks globally, it allows global and local cluster indexes to be independent. Also, mirroring does not require data to be declustered (i.e., spread over multiple disks).

Interleaved declustering offers significant improvements in recovery time, mean time to loss of both copies of some data, throughput during normal operation, and response time during recovery. For all architectures, interleaved declustering enables data to be spread over twice as many disks for improved load balancing. We show how tuning for interleaved declustering is simplified because it is dependent only on a few parameters that are usually well known for a specific workload and system configuration.
A performance evaluation of four parallel join algorithms in a shared-nothing multiprocessor environment
Authors: Schneider Donovan A. , DeWitt David J.
Published: November 2005

In this paper we analyze and compare four parallel join algorithms. Grace and Hybrid hash represent the class of hash-based join methods, Simple hash represents a looping algorithm with hashing, and our last algorithm is the more traditional sort-merge. The performance of each of the algorithms with different tuple distribution policies, the addition of bit vector filters, varying amounts of main-memory for joining, and non-uniformly distributed join attribute values is studied. The Hybrid hash-join algorithm is found to be superior except when the join attribute values of the inner relation are non-uniformly distributed and memory is limited. In this case, a more conservative algorithm such as the sort-merge algorithm should be used. The Gamma database machine serves as the host for the performance comparison.
F-logic: a higher-order language for reasoning about objects, inheritance, and scheme
Authors: Kifer Michael , Lausen Georg
Published: November 2005

We propose a database logic which accounts in a clean declarative fashion for most of the “object-oriented” features such as object identity, complex objects, inheritance, methods, etc. Furthermore, database schema is part of the object language, which allows the user to browse schema and data using the same declarative formalism. The proposed logic has a formal semantics and a sound and complete resolution-based proof procedure, which makes it also computationally attractive.
On accessing object-oriented databases: expressive power, complexity, and restrictions
Authors: Hull Richard , Su Jianwen
Published: November 2005

A formal framework for studying the expressive power and complexity of OODB queries is developed. Three approaches to modeling sets are articulated and compared. The class of
regular
OODB schemas supports the explicit representation of set-valued types. Using an
object-based
semantics for sets, the regular schemas correspond to most implemented OODB systems in the literature; a
value-based
semantics for sets is also introduced. Without restrictions, both of these approaches support the specification of all computable queries. Assuming that the new operator is prohibited, the query language of the regular OODB schemas under the object-based semantics is complete in PSPACE; and under the value-based semantics it has hyper-exponential complexity. The third approach to modeling sets is given by the
algebraic OODB
model, in which multi-valued attributes rather than set-valued types are supported. method implementations can use operators stemming from the relational algebra, and do not have side-effects. The query language of algebraic OODBs is more powerful than the relational algebra but has complexity bounded by PTIME. The expressive power and complexity of data access for other variations of OODBs are also considered. Finally, a new relational query language, called
algebra
+
pointwise recursion
, is introduced. This is equivalent to the algebraic OODB language, and can compute generalized transitive closure.
Object identity as a query language primitive
Authors: Abiteboul Serge , Kanellakis Paris C.
Published: November 2005

We demonstrate the power of object identities (oid's) as a database query language primitive. We develop an object-based data model, whose structural part generalizes most of the known complex-object data models: cyclicity is allowed in both its schemas and instances. Our main contribution is the operational part of the data model, the query language IQL, which uses oid's for three critical purposes: (1) to represent data-structures with sharing and cycles, (2) to manipulate sets and (3) to express any computable database query. IQL can be statically type checked, can be evaluated bottom-up and naturally generalizes most popular rule-based database languages. The model can also be extended to incorporate type inheritance, without changes to IQL. Finally, we investigate an analogous value-based data model, whose structural part is founded on regular infinite trees and whose operational part is IQL.
The architecture of an active database management system
Authors: McCarthy Dennis , Dayal Umeshwar
Published: November 2005

The HiPAC project is investigating active, time-constrained database management. An active DBMS is one which automatically executes specified actions when specified conditions arise. HiPAC has proposed Event-Condition-Action (ECA) rules as a formalism for active database capabilities. We have also developed an execution model that specifies how these rules are processed in the context of database transactions. The additional functionality provided by ECA rules makes new demands on the design of an active DBMS. In this paper we propose an architecture for an active DBMS that supports ECA rules. This architecture provides new forms of interaction, in support of ECA rules, between application programs and the DBMS. This leads to a new paradigm for constructing database applications.
Compiling complex database transition triggers
Authors: Cohen D.
Published: November 2005

This paper presents a language for specifying database updates, queries and rule triggers, and describes how triggers can be compiled into an efficient mechanism. The rule language allows specification of both state and transition constraints as special cases, but is more general than either. The implementation we describe compiles rules and updates independently of each other. Thus rules can be added or deleted without recompiling any update program and vice versa.
A grammar-based approach towards unifying hierarchical data models
Authors: Gyssens M. , Paredaens J. , van Gucht D.
Published: November 2005

A simple model for representing the hierarchical structure of information is proposed. This model, called the grammatical model, is based on trees that are generated by grammars; the grammars describe the hierarchy of the information represented by the trees. Two transformation languages, an algebra and a calculus, are presented and shown to be equally expressive.
A recursive algebra and query optimization for nested relations
Authors: Colby Latha S.
Published: November 2005

The nested relational model provides a better way to represent complex objects than the (flat) relational model, by allowing relations to have relation-valued attributes. A recursive algebra for nested relations that allows tuples at all levels of nesting in a nested relation to be accessed and modified without any special navigational operators and without having to flatten the nested relation has been developed. In this algebra, the operators of the nested relational algebra are extended with recursive definitions so that they can be applied not only to relations but also to subrelations of a relation. In this paper, we show that queries are more efficient and succinct when expressed in the recursive algebra than in languages that require restructuring in order to access subrelations of relations. We also show that most of the query optimization techniques that have been developed for the relational algebra can be easily extended for the recursive algebra and that queries are more easily optimizable when expressed in the recursive algebra than when they are expressed in languages like the non-recursive algebra.
Redundancy in spatial databases
Authors: Orenstein J. A.
Published: November 2005

Spatial objects other than points and boxes can be stored in spatial indexes, but the techniques usually require the use of approximations that can be arbitrarily bad. This leads to poor performance and highly inaccurate responses to spatial queries. The situation can be improved by storing some objects in the index redundantly. Most spatial indexes permit no flexibility in adjusting the amount of redundancy. Spatial indexes based on z-order permit this flexibility. Accuracy of the query response increases with redundancy, (there is a “diminishing return” effect). Search time, as measured by disk accesses first decreases and then increases with redundancy. There is, therefore, an optimal amount of redundancy (for a given data set). The optimal use of redundancy for z-order is explored through analysis of the z-order search algorithm and through experiments.
Retrieval performance versus disc space utilization on WORM optical discs
Authors: Christodoulakis Stavros , Ford Daniel Alexander
Published: November 2005

Steady progress in the development of optical disc technology over the past decade has brought it to the point where it is beginning to compete directly with magnetic disc technology. WORM optical discs in particular, which permanently register information on the disc surface, have significant advantages over magnetic technology for applications that are mainly archival in nature but require the ability to do frequent on-line insertions.

In this paper, we propose a class of access methods that use rewritable storage for the temporary buffering of insertions to data sets stored on WORM optical discs and we examine the relationship between the retrieval performance from WORM optical discs and the utilization of disc storage space when one of these organizations is employed. We describe the performance trade off as one of fast sequential retrieval of the contents of a block versus wasted space owing to data replication. A model of a specific instance of such an organization (a buffered hash file scheme) is described that allows for the specification of retrieval performance objectives. Alternative strategies for managing data replication that allow trade offs between higher consumption rates and better average retrieval performance are also described. We then provide an expected value analysis of the amount of disc space that must be consumed on a WORM disc to meet specified performance limits. The analysis is general enough to allow easy extension to other types of buffered files systems for WORM optical discs.
Access methods for multiversion data
Authors: Lomet David , Salzberg Betty
Published: November 2005

We present an access method designed to provide a single integrated index structure for a versioned timestamped database with a non-deletion policy. Historical data (superceded versions) is stored separately from current data. Our access method is called the
Time-Split B-tree
. It is an index structure based on Malcolm Easton's Write Once B-tree.

The Write Once B-tree was developed for data stored entirely on a Write-Once Read-Many or
WORM
optical disk. The Time-Split B-tree differs from the Write Once B-tree in the following ways:

Current data
must
be stored on an
erasable
random-access device.

Historical data
may
be stored on
any
random-access device, including WORMs, erasable optical disks, and magnetic disks. The point is to use a faster and more expensive device for the current data and a slower cheaper device for the historical data.

The splitting policies have been changed to reduce redundancy in the structure—the option of pure key splits as in B
+
-trees and a choice of split times for time-based splits enable this performance enhancement.

When data is migrated from the current to the historical database, it is consolidated and appended to the end of the historical database, allowing for high space utilization in WORM disk sectors.
Performance enhancement through replication in an object-oriented DBMS
Authors: Shekita Eugene J. , Carey Michael J.
Published: November 2005

In this paper we describe how replicated data can be used to speedup query processing in an object-oriented database system. The general idea is to use replicated data to eliminate some of the functional joins that would otherwise be required for query processing. We refer to our technique for replicating data as
field replication
because it allows individual data fields to be selectively replicated. In the paper we describe how field replication can be specified at the data model level and we present storage-level mechanisms to efficiently support it. We also present an analytical cost model to give some feel for how beneficial field replication can be and the circumstances under which it breaks down. While field replication is a relatively simple notion, the analysis shows that it can provide significant performance gains in many situations.
Exploiting inheritance and structure semantics for effective clustering and buffering in an object-oriented DBMS
Authors: Chang E. E. , Katz R. H.
Published: November 2005

Object-oriented databases provide new kinds of data semantics in terms of inheritance and structural relationships. This paper examines how to use these additional semantics to obtain more effective object buffering and clustering. We use the information collected from real-world object-oriented applications, the Berkeley CAD Group's OCT design tools, as the basis for a simulation model with which to investigate alternative buffering and clustering strategies. Observing from our measurements that real CAD applications exhibit high data read to write ratios, we propose a run-time clustering algorithm whose initial evaluation indicates that system response time can be improved by a factor of 200% when the read/write ratio is high. We have also found it useful to limit the amount of I/O allowed to the clustering algorithm as it examines candidate pages for clustering at run-time. Basically, there is little performance distinction between limiting reclustering to a few I/Os or many, so a low limit on I/O appears to be acceptable. We also examine, under a variety of workload assumptions, context-sensitive buffer replacement policies with alternative prefetching policies.
Dynamic query evaluation plans
Authors: Graefe G. , Ward K.
Published: November 2005

In most database systems, a query embedded in a program written in a conventional programming language is optimized when the program is compiled. The query optimizer must make assumptions about the values of the program variables that appear as constants in the query, the resources that can be committed to query evaluation, and the data in the database. The optimality of the resulting query evaluation plan depends on the validity of these assumptions. If a query evaluation plan is used repeatedly over an extended period of time, it is important to determine when reoptimization is necessary. Our work aims at developing criteria when reoptimization is required, how these criteria can be implemented efficiently, and how reoptimization can be avoided by using a new technique called
dynamic query evaluation plans
. We experimentally demonstrate the need for dynamic plans and outline modifications to the EXODUS optimizer generator required for creating dynamic query evaluation plans.
RIDL*: a tool for the computer-assisted engineering of large databases in the presence of integrity constraints
Authors: De Troyer O.
Published: November 2005

Tools and methods that transform higher level formalisms into logical database designs become very important. Rarely if ever do these transformations take into account integrity constraints existing in the “conceptual” model. Yet these become essential if one is forced to introduce redundancies for reasons of e.g. query efficiency. We therefore adopted the Binary Relationship Model (or “NIAM”) that is rich in constraints and built a flexible tool, RIDL
*
, that graphically captures NIAM semantic networks, analyzes them and then transforms them into relational designs (normalized or not), under the control of a database engineer assisted by a rule base. This is made possible by a rule-driven implementation of a new, stepwise synthesis process, and its benefits are illustrated by its treatment of e.g. subtypes. RIDL
*
is operational at several industrial sites in Europe and the U.S. on sizeable database projects.
Vertical partitioning for database design: a graphical algorithm
Authors: Navathe Shamkant B. , Ra Mingyoung
Published: November 2005

Vertical partitioning is the process of subdividing the attributes of a relation or a record type, creating fragments. Previous approaches have used an iterative binary partitioning method which is based on clustering algorithms and mathematical cost functions. In this paper, however, we propose a new vertical partitioning algorithm using a graphical technique. This algorithm starts from the attribute affinity matrix by considering it as a complete graph. Then, forming a linearly connected spanning tree, it generates all meaningful fragments simultaneously by considering a cycle as a fragment. We show its computational superiority. It provides a cleaner alternative without arbitrary objective functions and provides an improvement over our previous work on vertical partitioning.
A commentary on the POSTGRES rules system
Authors: Stonebraker M. , Hearst M. , Potamianos S.
Published: November 2005

This paper suggests modifications to the POSTGRES rules system (PRS) to increase its usability and function. Specifically, we suggest changing the rule syntax to a more powerful one and propose additional keywords, introduce the notion of rulesets whose purpose is to increase the user's control over the rule activation process, and expand the versioning facility to support a broader range of applications than is currently possible.
Rule management and evaluation: an active DBMS perspective
Authors: Chakravarthy S.
Published: November 2005

An
active database management system
is characterized by its ability to monitor and react to both database and nondatabase events in a timely and efficient manner. There have been several attempts at integrating this capability with conventional, passive DBMSs. In fact, this capability has been shown to be pivotal for supporting a variety of database functions in an elegant manner.
Rules for implementing very large knowledge base systems
Authors: Bocca J. B. , Freytag J. C.
Published: November 2005

With the current research effort in knowledge base management systems (KBMSs) the interest in storing, retrieving, and processing rules efficiently, and using them for describing and implementing such systems has increased significantly. In this paper we contribute to this subject in two ways. First, we introduce Educe*, an integrated programming system for building large knowledge base systems. In particular, we describe the treatment of rules and complex logic terms, examine at the physical level the compilation of logic programs and its subsequent storage, retrieval and execution in the specified context, and discuss performance related aspects of our system.

Second, we provide an overview on how to use rules for organizing the processing of user requests in a database/knowledge base environment. Specifically, we discuss aspects of rule-based query optimization and compilation. Finally, we outline additional query processing problems that could benefit from a rule-based specification and a rule-driven implementation.
Pattern match reduction for Relational Production Language in the USL MMDBS
Authors: Delcambre L. M. L. , Waramahaputi J. , Etheredge J. N.
Published: November 2005

The Relational Production Language, RPL, is a rule language where both the condition and action part of a rule is expressed in a relational language. This makes RPL a natural choice for expert database systems. In this paper, the performance of the RPL interpreter is addressed through the use of Pattern Match Reduction, PMR, within the context of the USL main memory database system, the USL MMDBS. PMR provides a generalization of relational view materialization by supporting relationally complete queries and by allowing the materialization of any/all intermediate nodes in a query tree. The USL MMDBS supports PMR because of its performance characteristics for query processing (due to a linear sort/join algorithm) and because intermediate query results are stored as “first class” relations. Thus the materialization required by PMR is directly supported. This paper introduces PMR and the USL MMDBS and presents preliminary performance results.
The design and implementation of an extendible deductive database system
Authors: Kierman J. , Maindreville C. , Simon E.
Published: November 2005

This paper presents the design and implementation of a deductive database system. RDL1, is the production rule language for this system. This language is an extension of logic based languages towards the support of updates and complex domains. Different features of this language are described with its applications. The general architecture of the system is presented highlighting integration with a relational database system. Then, three original features of the system are discussed: extensibility through the definition of end user data types, query optimization techniques, and the extensibility of the control strategy. Future improvements and extensions conclude the paper.
Distributed database design: a practical approach and example
Authors: Teorey T. J.
Published: November 2005

A distributed database design problem is presented that involves the development of a global model, a fragmentation, and a data allocation. The student is given a conceptual entity-relationship model for the database and a description of the transactions and a generic network environment. A stepwise solution approach to this problem is shown, based on mean value assumptions about workload and service.
The database group at ISS, National University of Singapore
Authors: Narasimhalu D.
Published: November 2005

The database group is headed by Dr. A Desai Narasimhalu. It comprises nine staff members, together with a collaborative member and three undergraduate students from the Department of Information Systems and Computer Science. The group's main research areas are listed below.
Bayan: an Arabic text database management system
Authors: King Roger , Morfeq Ali
Published: November 2005

Most existing databases lack features which allow for the convenient manipulation of text. It is even more difficult to use them if the text language is not based on the Roman alphabet. The Arabic language is a very good example of this case. Many projects have attempted to use conventional database systems for Arabic data manipulation (including text data), but because of Arabic's many differences with English, these projects have met with limited success. In the Bayan project, the approach has been different. Instead of simply trying to adopt an environment to Arabic, the properties of the Arabic language were the starting point and everything was designed to meet the needs of Arabic, thus avoiding the shortcomings of other projects. A text database management system was designed to overcome the shortcomings of conventional database management systems in manipulating text data. Bayan's data model is based on an object-oriented approach which helps the extensibility of the system for future use. In Bayan, we designed the database with the Arabic text properties in mind. We designed it to support the way Arabic words are derived, classified, and constructed. Furthermore, linguistic algorithms (for word generation and morphological decomposition of words) were designed, leading to a formalization of rules of Arabic language writing and sentence construction. A user interface was designed on top of this environment. A new representation of the Arabic characters was designed, a complete Arabic keyboard layout was created, and a window-based Arabic user interface was also designed.
OdeView: the graphical interface to Ode
Authors: Agrawal R. , Gehani N. H. , Srinivasan J.
Published: November 2005

OdeView is the graphical front end for Ode, an object-oriented database system and environment. Ode's data model supports data encapsulation, type inheritance, and complex objects. OdeView provides facilities for examining the database schema (i.e., the object type or class hierarchy), examining class definitions, browsing objects, following chains of references starting from an object, synchronized browsing, displaying selected portions of objects (projection), and retrieving objects with specific characteristics (selection).

OdeView does not need to know about the internals of Ode objects. Consequently, the internals of specific classes are not hardwired into OdeView and new classes can be added to the Ode database without requiring any changes to or recompilation of OdeView. Just as OdeView does not know about the object internals, class functions (methods) for displaying objects are written without knowing about the specifics of the windowing software used by OdeView or the graphical user interface provided by it.

In this paper, we present OdeView, and discuss its design and implementation.
The input/output complexity of transitive closure
Authors: Ullman Jeffrey D. , Yannakakis Mihalis
Published: November 2005

Suppose a directed graph has its arcs stored in secondary memory, and we wish to compute its transitive closure, also storing the result in secondary memory. We assume that an amount of main memory capable of holding
s
“values” is available, and that
s
lies between
n
, the number of nodes of the graph, and
e
, the number of arcs. The cost measure we use for algorithms is the
I/O complexity
of Kung and Hong, where we count 1 every time a value is moved into main memory from secondary memory, or vice versa.

In the dense case, where
e
is close to
n
2
, we show that I/O equal to
Ο
(
n
3
/ √
s
) is sufficient to compute the transitive closure of an
n
-node graph, using main memory of size
s
. Moreover, it is necessary for any algorithm that is “standard,” in a sense to be defined precisely in the paper. Roughly, “standard” means that paths are constructed only by concatenating arcs and previously discovered paths. This class includes the usual algorithms that work for the generalization of transitive closure to semiring problems. For the sparse case, we show that I/O equal to
Ο
(
n
2
√
e/s
) is sufficient, although the algorithm we propose meets our definition of “standard” only if the underlying graph is acyclic. We also show that Ω(
n
2
√
e/s
) is necessary for any standard algorithm in the sparse case. That settles the I/O complexity of the sparse/acyclic case, for standard algorithms. It is unknown whether this complexity can be achieved in the sparse, cyclic case, by a standard algorithm, and it is unknown whether the bound can be beaten by nonstandard algorithms.

We then consider a special kind of standard algorithm, in which paths are constructed only by concatenating arcs and old paths, never by concatenating two old paths. This restriction seems essential if we are to take advantage of sparseness. Unfortunately, we show that almost another factor of
n
I/O is necessary. That is, there is an algorithm in this class using I/O
Ο
(
n
3
√
e/s
) for arbitrary sparse graphs, including cyclic ones. Moreover, every algorithm in the restricted class must use Ω(
n
3
√
e/s
/log
3
n
) I/O, on some cyclic graphs.
Polynomial time designs toward both BCNF and efficient data manipulation
Authors: Wang Ke
Published: November 2005

We define the independence-reducibility based on a modification of key dependencies, which has better computational properties and is more practically useful than the original one based on key dependencies. Using this modification as a tool, we design BCNF databases that are highly desirable with respect to updates and/or query answering. In particular, given a set U of attributes and a set F of functional dependencies over U, we characterize when F can be embedded in a database scheme over U that is independent and is BCNF with respect to F, a polynomial time algorithm that tests this characterization and produces such a database scheme whenever possible is presented. The produced database scheme contains the fewest possible number of relation schemes. Then we show that designs of embedding constant-time-maintainable BCNF schemes and of embedding independence-reducible schemes share exactly the same method with the above design. Finally, a simple modification of this method yields a polynomial time algorithm for designing embedding separable BCNF schemes.
Write-only disk caches
Authors: Solworth Jon A. , Orji Cyril U.
Published: November 2005

With recent declines in the cost of semiconductor memory and the increasing need for high performance I/O disk systems, it makes sense to consider the design of large caches. In this paper, we consider the effect of caching writes. We show that cache sizes in the range of a few percent allow writes to be performed at negligible or no cost and independently of locality considerations.
Extending logic programming
Authors: Laenens Els , Sacca Domenico , Vermeir Dirk
Published: November 2005

An extension of logic programming, called “ordered logic programming”, which includes some abstractions of the object-oriented paradigm, is presented. An ordered program consists of a number of modules (objects), where each module is composed by a number of rules possibly with negated head predicates. A sort of “isa” hierarchy can be defined among the modules in order to allow for rule inheritance. Therefore, every module sees its own rules as local rules and the rules of the other modules to which it is connected by the “isa” hierarchy as global rules. In this way, as local rules may hide global rules, it is possible to deal with default properties and exceptions. This new approach represents a novel attempt to combine the logic paradigm with the object-oriented one in knowledge base systems. Moreover, this approach provides a new ground for explaining some recent proposals of semantics for classical logic programs with negation in the rule bodies and gives an interesting semantics to logic programs with negated rule heads.
ACTA: a framework for specifying and reasoning about transaction structure and behavior
Authors: Chrysanthis Panayiotis K. , Ramamritham Krithi
Published: November 2005

Recently, a number of extensions to the traditional transaction model have been proposed to support new information-intensive applications such as CAD/CAM and software development. However, these extended models capture only a subset of interactions that can be found in such applications, and represent only some of the points within the spectrum of interactions possible in competitive and cooperative environments.

ACTA
is a formalizable framework developed for characterizing the whole spectrum of interactions. The ACTA framework is
not
yet another transaction model, but is intended to unify the existing models. ACTA allows for specifying the
structure
and the
behavior
of transactions as well as for reasoning about the concurrency and recovery properties of the transactions. In ACTA, the semantics of interactions are expressed in terms of transactions' effects on the commit and abort of other transactions and on objects' state and concurrency status (i.e., synchronization state). Its ability to capture the semantics of previously proposed transaction models is indicative of its generality. The reasoning capabilities of this framework have also been tested by using the framework to study the properties of a new model that is derived by combining two existing transaction models.
Integrating object-oriented data modelling with a rule-based programming paradigm
Authors: Cacace F. , Ceri S. , Crespi-Reghizzi S. , Tanca L. , Zicari R.
Published: November 2005

LOGRES is a new project for the development of extended database systems which is based on the integration of the object-oriented data modelling paradigm and of the rule-based approach for the specification of queries and updates.

The data model supports generalization hierarchies and object sharing, the rule-based language extends
Datalog
to support generalized type constructors (sets, multisets, and sequences), rule-based integrity constraints are automatically produced by analyzing schema definitions. Modularization is a fundamental feature, as modules encapsulate queries and updates, when modules are applied to a LOGRES database, their side effects can be controlled.

The LOGRES project is a follow-up of the ALGRES project, and takes advantage of the ALGRES programming environment for the development of a fast prototype.
Making deductive databases a practical technology: a step forward
Authors: Kiernan G. , de Maindreville C. , Simon E.
Published: November 2005

Deductive databases provide a formal framework to study rule-based query languages that are extensions of first-order logic. However, deductive database languages and their current implementations do not seem appropriate for improving the development of real applications or even sample of them. Our goal is to make deductive database technology practical. The design and implementation of the RDL1 system, presented in this paper, constitute a step toward this goal. Our approach is based on the integration of a production rule language within a relational database system, the development of a rule-based programming environment and the support of system extensibility using Abstract Data Types. We discuss important practical experience gained during the implementation of the system. Also, comparisons with related work such as LDL, STARBURST and POSTGRES are given.
Set-oriented production rules in relational database systems
Authors: Widom Jennifer , Finkelstein S. J.
Published: November 2005

We propose incorporating a production rules facility into a relational database system. Such a facility allows definition of database operations that are automatically executed whenever certain conditions are met. In keeping with the set-oriented approach of relational data manipulation languages, our production rules are also set-oriented—they are triggered by sets of changes to the database and may perform sets of changes. The condition and action parts of our production rules may refer to the current state of the database as well as to the sets of changes triggering the rules. We define a syntax for production rule definition as an extension to SQL. A model of system behavior is used to give an exact semantics for production rule execution, taking into account externally-generated operations, self-triggering rules, and simultaneous triggering of multiple rules.
A predicate matching algorithm for database rule systems
Authors: Hanson Eric N. , Chaabouni Moez , Kim Chang-Ho , Wang Yu-Wang
Published: November 2005

Forward-chaining rule systems must test each newly asserted fact against a collection of predicates to find those rules that match the fact. Expert system rule engines use a simple combination of hashing and sequential search for this matching. We introduce an algorithm for finding the matching predicates that is more efficient than the standard algorithm when the number of predicates is large. We focus on equality and inequality predicates on totally ordered domains. This algorithm is well-suited for database rule systems, where predicate-testing speed is critical. A key component of the algorithm is the
interval binary search tree
(IBS-tree). The IBS-tree is designed to allow efficient retrieval of all intervals (e.g. range predicates) that overlap a point, while allowing dynamic insertion and deletion of intervals. The algorithm could also be used to improve the performance of forward-chaining inference engines for large expert systems applications.
On rules, procedure, caching and views in data base systems
Authors: Stonebraker Michael , Jhingran Anant , Goh Jeffrey , Potamianos Spyros
Published: November 2005

This paper demonstrates that a simple rule system can be constructed that supports a more powerful view system than available in current commercial systems. Not only can views be specified by using rules but also special semantics for resolving ambiguous view updates are simply additional rules. Moreover, procedural data types as proposed in POSTGRES are also efficiently simulated by the same rules system. Lastly, caching of the action part of certain rules is a possible performance enhancement and can be applied to materialize views as well as to cache procedural data items. Hence, we conclude that a rule system is a fundamental concept in a next generation DBMS, and it subsumes both views and procedures as special cases.
A performance evaluation of pointer-based joins
Authors: Shekita Eugene J. , Carey Michael J.
Published: November 2005

In this paper we describe three pointer-based join algorithms that are simple variants of the nested-loops, sort-merge, and hybrid-hash join algorithms used in relational database systems. Each join algorithm is described and an analysis is carried out to compare the performance of the pointer-based algorithms to their standard, non-pointer-based counterparts. The results of the analysis show that the pointer-based algorithms can provide significant performance gains in many situations. The results also show that the pointer-based nested-loops join algorithm, which is perhaps the most natural pointer-based join algorithm to consider using in an object-oriented database system, performs quite poorly on most medium to large joins.
The R*-tree: an efficient and robust access method for points and rectangles
Authors: Beckmann Norbert , Kriegel Hans-Peter , Schneider Ralf , Seeger Bernhard
Published: November 2005

The R-tree, one of the most popular access methods for rectangles, is based on the heuristic optimization of the area of the enclosing rectangle in each inner node. By running numerous experiments in a standardized testbed under highly varying data, queries and operations, we were able to design the R
*
-tree which incorporates a combined optimization of area, margin and overlap of each enclosing rectangle in the directory. Using our standardized testbed in an exhaustive performance comparison, it turned out that the R
*
-tree clearly outperforms the existing R-tree variants. Guttman's linear and quadratic R-tree and Greene's variant of the R-tree. This superiority of the R
*
-tree holds for different types of queries and operations, such as map overlay, for both rectangles and multidimensional points in all experiments. From a practical point of view the R
*
-tree is very attractive because of the following two reasons 1 it efficiently supports point and spatial data at the same time and 2 its implementation cost is only slightly higher than that of other R-trees.
Linear clustering of objects with multiple attributes
Authors: Jagadish H. V.
Published: November 2005

There is often a need to map a multi-dimensional space on to a one-dimensional space. For example, this kind of mapping has been proposed to permit the use of one-dimensional indexing techniques to a multi-dimensional index space such as in a spatial database. This kind of mapping is also of value in assigning physical storage, such as assigning buckets to records that have been indexed on multiple attributes, to minimize the disk access effort.

In this paper, we discuss what the desired properties of such a mapping are, and evaluate, through analysis and simulation, several mappings that have been proposed in the past. We present a mapping based on Hilbert's space-filling curve, which out-performs previously proposed mappings on average over a variety of different operating conditions.
A comparison of spatial query processing techniques for native and parameter spaces
Authors: Orenstein Jack
Published: November 2005

Spatial queries can be evaluated in native space or in a parameter space. In the latter case, data objects are transformed into points and query objects are transformed into search regions. The requirement for different data and query representations may prevent the use of parameter-space searching in some applications. Native-space and parameter-space searching are compared in the context of a z order-based spatial access method. Experimental results show that when there is a single query object, searching in parameter space can be faster than searching in native space, if the data and query objects are large enough, and if sufficient redundancy is used for the query representation. The result is, however, less accurate than the native space result. When there are multiple query objects, native-space searching is better initially, but as the number of query objects increases, parameter space searching with low redundancy is superior. Native-space searching is much more accurate for multiple-object queries.
Analysis of SIGMOD's co-authorship graph
Authors: Nascimento Mario A. , Sander Jörg , Pound Jeffrey
Published: November 2005

In this paper we investigate the co-authorship graph obtained from all papers published at SIGMOD between 1975 and 2002. We find some interesting facts, for instance, the identity of the authors who, on average, are "closest" to all other authors at a given time. We also show that SIGMOD's co-authorship graph is yet another example of a small world---a graph topology which has received a lot of attention recently. A companion web site for this paper can be found at http://db.cs.ualberta.ca/coauthorship.
Design issues and challenges for RDF- and schema-based peer-to-peer systems
Authors: Nejdl Wolfgang , Siberski Wolf , Sintek Michael
Published: November 2005

Databases have employed a schema-based approach to store and retrieve structured data for decades. For peer-to-peer (P2P) networks, similar approaches are just beginning to emerge. While quite a few database techniques can be re-used in this new context, a P2P data management infrastructure poses additional challenges which have to be solved before schema-based P2P networks become as common as schema-based databases. We will describe some of these challenges and discuss approaches to solve them. Our discussion will be based on the design decisions we have employed in our Edutella infrastructure, a schema-based P2P network based on RDF and RDF schemas, and will also point out additional work addressing the issues discussed.
The Piazza peer data management project
Authors: Tatarinov Igor , Ives Zachary , Madhavan Jayant , Halevy Alon , Suciu Dan , Dalvi Nilesh , Dong Xin (Luna) , Kadiyska Yana , Miklau Gerome , Mork Peter
Published: November 2005

A major problem in today's information-driven world is that sharing heterogeneous, semantically rich data is incredibly difficult. Piazza is a
peer data management
system that enables sharing heterogeneous data in a distributed and scalable way. Piazza assumes the participants to be interested in sharing data, and willing to define pairwise mappings between their schemas. Then, users formulate queries over their preferred schema, and a query answering system expands recursively any mappings relevant to the query, retrieving data from other peers. In this paper, we provide a brief overview of the Piazza project including our work on developing mapping languages and query reformulation algorithms, assisting the users in defining mappings, indexing, and enforcing access control over shared data.
Selective information dissemination in P2P networks
Authors: Koubarakis Manolis , Tryfonopoulos Christos , Idreos Stratos , Drougas Yannis
Published: November 2005

We study the problem of selective dissemination of information in P2P networks. We present our work on data models and laiguages for textual information dissemination and discuss a relemnt P2P architecture that motivates our efforts. We also survey our results on the computational complexity of three related algorithmic problems (query satisfiability, entailment and filtering) and present efficient algorithms for the most crucial of these problems (filtering). Finally, we discuss the features of P2P-DIET, a super-peer system we have implemented at the Technical Lniversity of Crete, that realizes our vision and is able to support both ad-hoc querying and selective information dissemination scenarios in a P2P framework.
Sensor
Authors: Kumar Vijay
Published: November 2005

We visualize the world as a fully connected information space where each object communicates with all other objects without any temporal and geographical constraints. We can model this fully connected space using fine granularity processing which can be implemented using sensors technology. We regard sensors as atomic computing particles which can deployed to geographical locations for capturing and processing data of their surrounding. This report introduces a number of excellent research articles which present unique problems and their success in finding efficient solutions for them. It also peeks in to the future of ever changing information processing discipline.
The sensor spectrum
Authors: Hellerstein Joseph M. , Hong Wei , Madden Samuel R.
Published: November 2005

Though physical sensing instruments have long been used in astronomy, biology, and civil engineering, the recent emergence of wireless sensor networks and RFID has spurred a renaissance in sensor interest in both academia and industry. In this paper, we examine the spectrum of sensing platforms, from billion dollar satellites to tiny RF tags, and discuss the technological differences between them. We show that battery powered sensor networks, with low-power multihop radios and low-cost processors, occupy a sweet spot in this spectrum that is rife with opportunity for novel database research. We briefly summarize some of our research work in this space and present a number of examples of interesting sensor network-related problems that the database community is uniquely equipped to address.
Managing uncertainty in sensor database
Authors: Cheng Reynold , Prabhakar Sunil
Published: November 2005

Sensors are often employed to monitor continuously changing entities like locations of moving objects and temperature. The sensor readings are reported to a centralized database system, and are subsequently used to answer queries. Due to continuous changes in these values and limited resources (e.g., network bandwidth and battery power), the database may not be able to keep track of the actual values of the entities, and use the old values instead. Queries that use these old values may produce incorrect answers. However, if the degree of uncertainty between the actual data value and the database value is limited, one can place more confidence in the answers to the queries. In this paper, we present a frame-work that represents uncertainty of sensor data. Depending on the amount of uncertainty information given to the application, different levels of imprecision are presented in a query answer. We examine the situations when answer imprecision can be represented qualitatively and quantitatively. We propose a new kind of probabilistic queries called
Probabilistic Threshold Query
, which requires answers to have probabilities larger than a certain threshold value. We also study techniques for evaluating queries under different details of uncertainty, and investigate the tradeoff between data uncertainty, answer accuracy and computation costs.