bluuebunny/crossref_metadata_2025 huggingface dataset:
The Cougar Project
Authors: Demers Alan , Gehrke Johannes , Rajaraman Rajmohan , Trigoni Niki , Yao Yong
Published: November 2005

We present an update on the status of the Cougar Sensor Database Project, in which we are investigating a database approach to sensor networks: Clients "program" the sensors through
queries
in a high-level
declarative
language (such as a variant of SQL). In this paper, we give an overview of our activities on energy-efficient data dissemination and query processing. Due to space constraints, we cannot present a full menu of results; instead, we decided to only whet the reader's appetite with some problems in energy-efficient routing and in-network aggregation and some thoughts on how to approach them.
Energy and rate based MAC protocol for wireless sensor networks
Authors: Kannan Rajgopal , Kalidindi Ram , Iyengar S. S. , Kumar Vijay
Published: November 2005

Sensor networks are typically unattended because of their deployment in hazardous, hostile or remote environments. This makes the problem of conserving energy at individual sensor nodes challenging. S-MAC and PAMAS are two MAC protocols which periodically put nodes (selected at random) to sleep in order to achieve energy savings. Unlike these protocols, we propose an approach in which node duty cycles (i.e sleep and wake schedules) are based on their criticality. A distributed algorithm is used to find sets of winners and losers, who are then assigned appropriate slots in our TDMA based MAC protocol. We introduce the concept of of
energy-criticality
of a sensor node as a function of energies and traffic rates. Our protocol makes more critical nodes sleep longer, thereby balancing the energy consumption. Simulation results show that the performance of the protocol with increase in traffic load is better than existing protocols with increase in traffic load is better than existing protocols, thereby illustrating the energy balancing nature of the approach.
Multimedia streaming in large-scale sensor networks with mobile swarms
Authors: Gerla Mario , Xu Kaixin
Published: November 2005

Sensor networking technologies have developed very rapidly in the last ten years. In many situations, high quality multimedia streams may be required for providing detailed information of the hot spots in a large scale network. With the limited capabilities of sensor node and sensor network, it is very difficult to support multimedia streams in current sensor network structure. In this paper, we propose to enhance the sensor network by deploying limited number of mobile "swarms". The swarm nodes have much higher capabilities than the sensor nodes in terms of both hardware functionalities and networking capabilities. The mobile swarms can be directed to the hot spots in the sensor network to provide detailed information of the intended area. With the help of mobile swarms, high quality of multimedia streams can be supported in the large scale sensor network without too much cost. The wireless backbone network for connecting different swarms and the routing schemes for supporting such a unified architecture is also discussed and verified via simulations.
Reasoning on regular path queries
Authors: Calvanese D. , De Giacomo G. , Lenzerini M. , Vardi M. Y.
Published: November 2005

Current information systems are required to deal with more complex data with respect to traditional relational data. The database community has already proposed abstractions for these kinds of data, in particular in terms of semistructured data models. A semistructured model conceives a database essentially as a finite directed labeled graph whose nodes represent objects, and whose edges represent relationships between objects. In the same way as conjunctive queries form the core of any query language for the relational model, regular path queries (RPQs) and their variants are considered the basic querying mechanisms for semistructured data.Besides the basic task of query answering, i.e., evaluating a query over a database, databases should support other reasoning services related to querying. One of the most important is query containment, i.e., verifying whether for all databases the answer to a query is a subset of the answer to a second query. Another important reasoning service that has received considerable attention in the recent years is view-based query processing, which amounts to processing queries based on a set of materialized views, rather than on the raw data in the database.The goal of this paper is to describe basic results and techniques concerning query containment and view based query processing for the class of two-way regular-path queries (which extend RPQs with the inverse operator). We will demonstrate that the basic services for reasoning about two way regular path queries are decidable, thus showing that the limited form of recursion expressible by these queries does not endanger the decidability of reasoning. Besides the specific results, our methods show the power of two-way automata in reasoning on complex queries.
Agent-Oriented software engineering report on the 4
th
AOSE workshop (AOSE 2003)
Authors: Giorgini Paolo
Published: November 2005

Agent-Orientation is emerging as a powerful new paradigm in computing. Concepts, methodologies and tools from the agents paradigm are one of the best candidates for the foundations of the next generation of mainstream software systems. The Agent-Oriented Software Engineering (AOSE) workshop is an international event that brings together researchers and groups active in the area of agent-based software development. Here we briefly report on the fourth edition of the AOSE workshop.
Microprocessors for non-numeric processing
Authors: Zaky S. G.
Published: November 2005

The problem of processing of non-numeric data has received considerable attention in the last few years. This is primarily motivate by the pressing needs in the are a of data base management. It has long been recognized that the parallel processing capabilities of an associative processor are fundamentally well suited to this environment. However, the complexity and cost of truely associative memories make this approach impractical. In this paper, the demands that non-numeric processing place on memory and processor hardware are discussed. Some emerging trends are presented, and a suggestion is given regarding the development of a “general purpose” microprocessor that is suited to this environment.

Basically, the microprocessor discussed here is capable of performing simple search and update functions on a high speed, serial data stream. Therefore, it is suited to any application where such a situation is encountered, such as in digital communications.
The data management machine, a classification
Authors: Rosenthal Robert S.
Published: November 2005

There has been much interest in the use of special purpose processors as the data base management component of data processing systems. The generic terms “backend” and “data management machine” have been applied to such devices. Examination of the literature reveals a broad cross section of host to backend functional distribution and interconnection methodology. This discussion represents an attempt to examine and classify several of these backend data base management machine configurations in terms of their operational parameters and application constraints. A formal taxonomy of such systems remains yet to be performed.

At least three distinct classes of data management machine (DMM) are evidenced in the literature; they are the large host backend, distributed network data node and smart peripheral. The intended classes of problem that the various authors envision amenable to solution by the DMM approach exhibit overlap while the performance envelope in which each DMM architecture would provide a technically acceptable, economically sound solution to a given user requirement set varies. Some of the papers used as source for this work contained no explicit mention of either the problem classes or performance constraints that the described configuration was to address; thus liberty has been taken in interpreting the implicit application goals of these authors.
Trends in non-software support for input-output functions
Authors: McDonell Ken J.
Published: November 2005

Input-output subsystem architectures have evolved over the past 20-odd years to the point where two divergent approaches have found acceptance in current computer systems; the 'IBM channel' is the archetype of the lower level alternative, while the functionally more complex techniques involve a wide spectrum of distributed processor architectures supporting database and/or storage management functions independently with respect to the central processor. The paper traces the historical development of support (outside central processor based software) for input-output functions and concludes with a preliminary comparison of the relative merits of the software interfaces provided by the alternative input-output subsystem architectures.
Ulisse
Authors: Cerretti R. , Jasilli D. , Matteucci D. R.
Published: November 2005

The paper describes a project conducted in collaboration between CNUCE, an Institute of the Italian National Research Council, and a private research center, concerning a multifunctional system (Ulisse) capable of operating both as a stand alone unit for office administration and automation (word processsing, file management and retrieval) and as an intelligent terminal with local facilities for text editing, text formatting and storage.

The first results of the application of Ulisse in the environment of the scientific users of CNUCE are illustrated.
Data management requirements
Authors: Bray Olin H.
Published: November 2005

Memory management, database management, and message processing have in the past been defined in a relatively narrow way. With memory management the problem was to obtain cost effective use of real memory. Given a multiprogrammed environment, virtual memory systems allowed more effective use of expensive real memory. Memory management has become even more important with the development of very large and complex memory hierarchies. Database management systems were developed to allow the more effective use, sharing, and control of data resources - objectives which operating systems had previously provided for hardware resources. The driving force behind message processing has been the increased use of data communications and computer networks. This paper will consider the basis of the overlap in these areas, their common data management functions. Data management, as defined in this paper, includes the locating, routing, moving, and translating of data resources and the locating, reserving, and releasing of physical resources, i.e., primary and secondary storage.

The analysis performed in this paper is essential because of trends in computer architecture discussed below. Early hardware was designed for general purpose environments with software used to tailor it to specific applications. However, according to Gagliardi
9
future systems will consist of a set of subsystems, including a storage subsystem at the core surrounded by computational, spooling, and communications subsystems. The computational subsystem is the traditional “number cruncher” part of the system. The spooling subsystem provides the I/O interface between the system and the outside world. The communications subsystem links the various subsystems together and provides an interface to the rest of the network if the system is part of a larger distributed system. The storage subsystem consists of all the system's storage resources and their control processes. It controls all levels of the system memory and storage hierarchy. The storage subsystem controls the allocation of the physical storage resources and the movement of the data resources through the system. Depending on how these resources are used, they may be non-conserved or conserved, and if conserved, either serially reusable or sharable. Physical and data resources may be located, and if necessary reserved, independently or jointly.
Database usability
Authors: Date C. J.
Published: November 2005

There is a clear shift of emphasis in the way in which computer systems in general, and database management systems in particular, are perceived in the marketplace today. Questions of usability are beginning to outweigh the more traditional concerns with raw performance. The reason for this state of affairs is obvious; People costs are rising and machine costs are falling. This presentation consists of a critical examination of database management systems, or more specifically the externals of such systems, from a usability standpoint.The talk is divided into three parts. The first part, "What Does Usability Mean?", is an attempt to capture the notion of usability, or at least to characterize certain aspects of the notion in a variety of helpful ways. It is argued that usability is fundamentally concerned with raising the level of abstraction of the user interface in an appropriate and coherent manner --- with the emphasis on "appropriate" and "coherent".The second part of the talk, "Where We Are Today", contrasts the usability of modern (relational) systems with the comparative lack of usability found in older (nonrelational) systems. The usability advantages of the relational model and of relational systems are summarized and briefly analyzed.The third (and longest) part is called "How We Might Improve". Improvements are needed in at least four somewhat overlapping areas:1. Quality of current interfacesEven though they represent a major advance over earlier systems, most relational systems today still suffer from a number of usability problems, specifically with regard to missing function and what might be termed "ad hoc"-ness. Both of these aspects are illustrated with examples. Some principles of interface design (for example, uniformity and orthogonality) are briefly discussed.2. More semantics over current dataRaising the intelligence of the system (via semantic modeling) can also help to make the system more usable, especially with regard to database design and definition.3. New kinds of dataIncorporating new kinds of data (e.g., text, arrays, noncoded information) can also help to raise the level of the user interface, especially if the database management function is properly integrated with appropriate statistics, word-processing, graphics, and similar packages.4. New kinds of interfaceConventional, written-word-oriented query languages are very clumsy in many applications. The Field is wide open for improvements: text-editor-like interfaces, voice input and output, 3D terminals, pictorial interfaces, etc., etc.
Distributing a database for parallelism
Authors: Wong E. , Katz R. H.
Published: November 2005

In this paper we treat the problem of subdividing a database and allocating the fragments to the sites in a distributed database system in order to maximize non-duplicative parallelism. Our goal is to establish a conceptual framework for distributing data without being committed to specific cost models.We introduce the concept of "local sufficiency" as a measure of parallelism, and show how certain classes of queries lead naturally to irredundant partitions of a database that are locally sufficient. For classes of queries for which no irredundant distribution is locally sufficient, we offer ways to introduce redundancy in achieving local sufficiency
Query processing utilizing dependencies and horizontal decomposition
Authors: Kambayashi Yahiko , Yoshikawa Masatoshi
Published: November 2005

Since join operations are expensive, usually join scheduling is very important for query processing. In this paper we will discuss new procedures to handle cyclic queries utilizing dependencies and horizontal decompositions. There are three known procedures for cyclic query processing: (1) Relation merging, (2) Tuple-wise processing, (3) Attribute addition. As join operations are applied to relations which are processed by selection operations, the number of tuples is usually less than the original relation and thus there are situations in which temporary FDs are satisfied. Such FDs can be used to simplify the given query. To convert a given cyclic query into a tree, some relations must satisfy a set of FDs. This can be attained by horizontal decomposition. Tuple-wise processing and attribute addition are shown to be special cases of the FD-based procedure. We have also developed MVD-based procedures which are generalized from the FD-based procedure.
Windows on the world
Authors: Maier David , Rozenshtein David , Warren David S.
Published: November 2005

We discuss the philosophy, history and theory of window functions. Window functions (sometimes called
connections
) are a means to treat a relational database as a semantic whole, rather than as an arbitrary collection of relations. Simply stated, a window function maps a database state and a relation scheme to a relation over the scheme. Window functions are the basis for all existing universal scheme interfaces. We present an assumption inherent in universal scheme interfaces, the
unique role assumption.
Window functions have evolved along two paths, giving rise to computational definitions and weak instance definitions. We examine several examples of each type of window function, with special attention to the association-object window function of PIQUE. We then look at properties we feel a reasonable window function should satisfy, notably the
containment condition
and
faithfulness.
We also define
implicit objects,
which are relation schemes that a window function treats in a special manner, and which are useful for describing the behavior of window functions.
An abstract model of database concurrency control algorithms
Authors: Carey Michael J.
Published: November 2005

An abstract model of concurrency control algorithms is presented. The model facilitates implementation-independent descriptions of various algorithms, allowing them to be specified in terms of the information that they require, the conditions under which blocking or restarts are called for, and the manner in which requests are processed. The model also facilitates comparisons of the relative storage and CPU overheads of various algorithms based on their descriptions. Results are given for single-site versions of two-phase locking, basic timestamp ordering, and serial validation. Extensions which will allow comparisons of multiple version and distributed algorithms are discussed as well.
Forms approach to requirements specification for database design
Authors: Shu Nan C. , Wong Harry K. T. , Lum Vincent Y.
Published: November 2005

One of the most difficult tasks in database design is the collection of relevant information needed for database design. This information can be separated into two categories: information about the
processes
which use, modify or produce the data, and information about the
data
which is used, modified, or produced by the processes. This paper describes a "forms" oriented requirements specification facility as a formal means for capturing the information crucial for database design. Both kinds of information are expressible by the proposed structured forms specification. Furthermore, not only the application usage, but also the integrity constraints that must be maintained in the database can be captured in a concise, unambiguous and machine manipulable manner. The concepts underlying the forms approach are few and simple, hence it is easy to use for the database designer and can be understood by non-computer specialists. This facilitates the cooperation from users to participate in the specification of database application requirements.
Incomplete information and dependencies in relational databases
Authors: Imielinski Tomasz , Lipski Witold
Published: November 2005

An incomplete information relational database combines two types of information about the real world modeled by the database: (a) the information represented by tables with null values ("value not known") allowed as entries, and (b) the data dependencies, which are known to be satisfied in the real world. We view the well known chase procedure as a process which transforms type (b) information into an "equivalent" type (a) form. Assuming that the data dependencies are arbitrary implicational dependencies, we show that this transformation is not quite equivalent, but the corruption of information introduced cannot be discovered if the query language uses the operations of projection, positive selection (i.e. no negation in selection condition), union, natural join and renaming of attributes. This result can be interpreted also as the new important property of chase.The influence of so-called view dependencies on the table with null values is also examined.
Range nesting
Authors: Jarke Matthias , Koch Jürgen
Published: November 2005

Database queries explicitly containing existential and universal quantification become increasingly important in a number of areas such as integrity checking, interaction of databases and AI systems, heterogeneous databases, and statistical databases. Using a concept of range nesting in relational calculus expressions, the paper describes evaluation algorithms and transformation methods for an important class of quantified relational calculus queries called perfect expressions. This class includes well-known classes of "easy" queries such as tree queries (with free and existentially quantified variables only), and complacent (disconnected) queries.
The database language GEM
Authors: Zaniolo Carlo
Published: November 2005

GEM (an acronym for General Entity Manipulator) is a general-purpose query and update language for the DSIS data model, which is a semantic data model of the Entity-Relationship type. GEM is designed as an easy-to-use extension of the relational language QUEL, providing support for the notions of entities with surrogates, aggregation, generalization, null values, and set-valued attributes.
Overview of an Ada compatible distributed database manager
Authors: Chan Arvola , Dayal Umeshwar , Fox Stephen , Goodman Nathan , Ries Daniel R. , Skeen Dale
Published: November 2005

Adaplex is an integrated language for programming database applications. It results from the embedding of the database sublanguage DAPLEX in the general purpose programming language Ada. This paper provides an overview of the DDM: a distributed database manager (DDM) that supports the use of Adaplex as an interface language. The important technical innovations we have incorporated in the design of this system include:1. An advanced data model that captures more application semantics than conventional data models.2. Support for flexible data distribution options that improve locality of reference and efficiency of query processing.3. Extensive query optimization that combines compile time access path optimization with run time site selection.4. Efficient transaction management that reduces transaction conflicts and improves the resiliency of replicated data.5. Robust, incremental recovery management that provides for automatic recovery from certain "catastrophic" failure conditions.
"I wish I were over there"
Authors: Wilms Paul F. , Lindsay Bruce G. , Selinger Patricia G.
Published: November 2005

The design and implementation of R*, an experimental prototype of a distributed system for the management of interrelated, voluntarily cooperating, but also autonomous databases is based on several major objectives: site autonomy, transparency, ease of use and performance. This paper discusses the way data definition and control statements are executed in a distributed environment and shows how the general objectives are fulfilled. Specialized distributed execution facilities have been developed to facilitate the implementation of complex multi-site functions. This paper describes the facilities and methodology used to implement the distributed processing needed to perform multi-site data definition operations in R*.
Database evaluation using multiple regression techniques
Authors: Fedorowicz Jane
Published: November 2005

A model of the inverted file of an automated bibliographic system is constructed using the Zipf distribution of word frequency. By ascertaining the parameters of the Zipfian model of the inverted file system, one can estimate the minimum data storage requirements of the database. In addition, given a few additional system parameters, access time for a specified query can be estimated. The estimation procedures are accomplished using logarithmic transformations and multiple regression techniques. This paper introduces the Zipfian models, their regression formulation, and their results and interpretation for application to database evaluation.
Database support for interactive computer graphics
Authors: Spooner David L.
Published: November 2005

Software applications involving interactive computer graphics are made up of several components. One of these is a data modeling component. This data modeling component is often application dependent and therefore difficult to integrate with the data model of other related applications. One solution to this problem is to interface a DBMS with an interactive graphics system to reduce data model dependency and increase sharing of data. This also has the advantage of allowing novice users to use computer graphics by eliminating the need for the user to write complex programs invoking the graphics system.This paper explores these ideas by discussing the implementation of a prototype interface between a relational DBMS and an interactive computer graphics system. It presents both the database structures used to manage the data and the techniques used to design the interface. It concludes by discussing an approach for making the interface portable.
A multikey hashing scheme using predicate trees
Authors: Valduriez Patrick , Viemont Yann
Published: November 2005

A new method for multikey access suitable for dynamic files is proposed that transforms multiple key values into a logical address This method is based on a new structure, called predicate tree, that represents the function applied to several keys A predicate tree permits to specify in a unified way various hashing schemes by allowing for different definitions of predicates A logical address qualifies a space partition of a file according to its predicate tree This address is seen as a single key by a digital hashing method which transforms it into a physical address This method is used to address records in a file and to transform a retrieval qualification on a file into a set of partitions to access Finally, a qualitative analysis of the behavior of the method is given which exhibits its value
Combining relational and network retrieval methods
Authors: Chen Huei-huang , Kuck Sharon McCure
Published: November 2005

New methods for retrieving records from a database with links are given so that records are retrieved only once and not multiple times as happens when using the traditional method of retrieval Improvements as great as 50 percent are expected for queries over databases containing only many-to-one relationships and much greater improvements are expected when many-to-many relationships are embedded in the database Furthermore, it is shown how to combine relational and network retrieval methods Relations, containing many tuples, are created during the evaluation of a network query Each relation is either joined with other relations or is used to continue the evaluation of the network query The methods given show how to optimize data retrieval from a relational database that is implemented using links, where each link represents a many-to-one relationship
Optimal computation of total projections with unions of simple chase join expressions
Authors: Chan Edward P. F.
Published: November 2005

The representative instance has been proposed as a query answering device in systems using the Universal Relation Interface. One approach is to use the total projections of the representative instance to generate the answer for a query. Associated with this approach is the problem of how to generate the total projections of the representative instance efficiently. We propose a generalization of extension joins, called chase join expressions, as a means to compute the total projections when functional dependencies are given as constraints. In particular, we identify an important subclass of chase join expressions called simple chase join expressions and show that the total projections with respect to a set of functional dependencies can be computed by unions of simple chase join expressions when an independent scheme is assumed. We also find a simple and efficient algorithm that minimizes the number of join operations in a union of simple chase join expressions.
Performance comparison of index structures for multi-key retrieval
Authors: Kriegel Hans-Peter
Published: November 2005

In this paper, we report on a performance comparison of four software implemented index structures for multi-key retrieval the inverted file, the grid file and two variants of multidimensional B-trees It turns out that the recently suggested structures multidimensional B-tree and grid file outperform the traditional inverted file
Browsing in a loosely structured database
Authors: Motro Amihai
Published: November 2005

Current database architectures emphasize structure and are inappropriate for applications which model environments that are subject to constant evolution, or environments which do not lend themselves to massive classifications In this paper we describe an architecture which promotes databases that are only
loosely structured
heaps of facts instead of highly structured data This architecture avoids the traditional dichotomy between "schema" and "data", and it incorporates a single mechanism for defining both inference rules and integrity constraints As lack of organization will usually have adverse effect on retrieval, the principal retrieval method for loosely structured databases is
browsing
exploratory searching which does not assume any knowledge of the organization (or even the very existence of organization) Two styles of browsing, called navigation and probing, are defined Both are derived from a standard query language based on predicate logic
Overview of the Jasmin database machine
Authors: Fishman Daniel H , Lai Ming-Yee , Wilkinson W Kevin
Published: November 2005

The Jasmin database machine is being implemented as part of a research project in distributed processing and database management A primary goal of the work is to demonstrate the feasibility of a practical multiprocessor database machine suitable for large database, high transaction-rate applications Key features of Jasmin are its configurable performance, its use of off-the-shelf parts, and its ability to handle distributed databases A uniprocessor prototype of Jasmin has already been completed and the multiprocessor version is planned for later this year In this paper we describe Jasmin's architecture and discuss the performance observed in the uniprocessor prototype
Maintenance of views
Authors: Shmueli Oded , Itai Alon
Published: November 2005

In relational databases a
view definition
is a query against the database, and a
view materialization
is the result of applying the view definition to the current database A view materialization over a database may change as relations in the database undergo modificationsIn this paper a mechanism is proposed in which the view is materialized at all times The problem which this mechanism addresses is how to quickly update the view in response to database changes A structure is maintained which provides information useful in minimizing the amount of work caused by updatesMethods are presented for handling both general databases and the much simpler
tree
databases (also called
acyclic
database) In both cases adding or deleting a tuple can be performed in polynomial time For tree databases the degree of the polynomial is independent of the schema structure while for cyclic databases the degree depends on the schema structure The cost of a sequence of tuple additions (deletions) is also analyzed
An optimizing prolog front-end to a relational query system
Authors: Jarke Matthias , Clifford Jim , Vassiliou Yannis
Published: November 2005

An optimizing translation mechanism for the dynamic interaction between a logic-based expert system written in PROLOG and a relational database accessible through SQL is presented. The mechanism makes use of an intermediate language that decomposes the optimization problem and makes the proposed approach target-language independent. It can either facilitate expert system - database interaction, e.g., when integrating expert systems into business systems, or augment existing databases with (external) deductive capabilities.
Prism
Authors: Shepherd Allan , Kerschberg Larry
Published: November 2005

This paper presents a knowledge-based approach to the specification, design, implementation, and evolution of database applications The knowledge base consists of 1) facts regarding database objects that are organized into a hierarchy of models, and 2) rules that specify the behavior of objects within a model and among modelsThe model hierarchy consists of database application data, database schemas, data model definitions, and system-related objects that control the user's interaction with the system The rules governing the behavior of objects are specified as explicit constraints on those objects User goals are transformed into conjectures that the inference engine must prove are satisfiable by interpreting all applicable constraintsThe semantic architecture of the PRISM system is described, together with the syntax and semantics of the constraint language PRISM is implemented in the C programming language and runs under the UNIX ** operating system
SIM: a database system based on the semantic data model
Authors: Jagannathan D. , Fritchman B. L. , Guck R. L. , Thompson J. P. , Tolbert D. M.
Published: November 2005

SIM is a fully featured, commercially available database management system based on a semantic data model similar to Hammer and McLeod's SDM SIM has two primary modeling goals. The first is to narrow the gap between a user's real-world perception of data and the conceptual view imposed by the database system because of modeling presuppositions or limitations. The second goal is to allow, as much as possible, the semantics of data to be defined in the schema and make the database system responsible for enforcing its integrity SIM provides a rich set of constructs for schema definition, including those for specifying generalization hierarchies modeled by directed acyclic graphs, interobject relationships and integrity constraints. It also features a novel, easy-to-use, English-like DML. This paper describes the key modeling features of SIM, the architecture of the system and its implementation considerations.
Contexts and metamessages in object-oriented database programming language design
Authors: Caruso Michael , Sciore Edward
Published: November 2005

VISION is an object-oriented database system currently used commercially to develop investment analysis and other large statistical applications. Characteristic of these applications, beside the standard issues of structural and computational richness, is the need to handle time, versions, and concurrency control in a manner that does not produce combinatoric complexity in object protocol. This paper describes the approach taken by VISION in addressing these issues.
Partition semantics for incomplete information in relational databases
Authors: Laurent D. , Spyratis N.
Published: November 2005

We define partition semantics for databases with incomplete information and we present an algorithm for query processing in the presence of incomplete information and functional dependencies. We show that Lipski's model for databases with incomplete information can be seen as a special case of our model.
The derivation problem of summary data
Authors: Malvestuto F. M.
Published: November 2005

Given a statistical database consisting of two summary tables based on a common but not identical classification criterion (e.g., two geographical partitionings of a country) there are additional summary tables that are
derivable
in the sense that they are uniquely (i.e., with no uncertainty) determined by the tables given. Derivable tables encompass not only, of course, “less detailed” tables (that is, aggregated data) but also “more detailed” tables (that is, disaggregated data). Tables of the second type can be explicitly constructed by using a “procedure of data refinement” based on the graph representation of the correspondences between the categories of the two classification systems given in some cases, that is, when such a graph representation meets the
acyclicity
condition, the underlying database is “equivalent” to a single table (called
representative table
) and then a necessary and sufficient condition for a table to be derivable can be stated.
Process and dataflow control in distributed data-intensive systems
Authors: Alexander W. , Copeland G.
Published: November 2005

In dataflow architectures, each dataflow operation is typically executed on a single physical node. We are concerned with distributed data-intensive systems, in which each base (i.e., persistent) set of data has been declustered over many physical nodes to achieve load balancing. Because of large base set size, each operation is executed where the base set resides, and intermediate results are transferred between physical nodes. In such systems, each dataflow operation is typically executed on many physical nodes. Furthermore, because computations are data-dependent, we cannot know until run time which subset of the physical nodes containing a particular base set will be involved in a given dataflow operation. This uncertainty creates several problems
.

We examine the problems of efficient program loading, dataflow—operation activation and termination, control of data transfer among dataflow operations, and transaction commit and abort in a distributed data-intensive system. We show how these problems are interrelated, and we present a unified set of mechanisms for efficiently solving them. For some of the problems, we present several solutions and compare them quantitatively.
Data placement in Bubba
Authors: Copeland George , Alexander William , Boughter Ellen , Keller Tom
Published: November 2005

This paper examines the problem of data placement in Bubba, a highly-parallel system for data-intensive applications being developed at MCC. “Highly-parallel” implies that load balancing is a critical performance issue. “Data-intensive” means data is so large that operations should be executed where the data resides. As a result, data placement becomes a critical performance issue.

In general, determining the optimal placement of data across processing nodes for performance is a difficult problem. We describe our heuristic approach to solving the data placement problem in Bubba. We then present experimental results using a specific workload to provide insight into the problem. Several researchers have argued the benefits of declustering (i e, spreading each base relation over many nodes). We show that as declustering is increased, load balancing continues to improve. However, for transactions involving complex joins, further declustering reduces throughput because of communications, startup and termination overhead.

We argue that data placement, especially declustering, in a highly-parallel system must be considered early in the design, so that mechanisms can be included for supporting variable declustering, for minimizing the most significant overheads associated with large-scale declustering, and for gathering the required statistics.
Semantics based transaction management techniques for replicated data
Authors: Kumar Akhil , Stonebraker Michael
Published: November 2005

Data is often replicated in distributed database applications to improve availability and response time. Conventional multi-copy algorithms deliver fast response times and high availability for read-only transactions while sacrificing these goals for updates. In this paper, we propose a multi-copy algorithm that works well in both retrieval and update environments by exploiting special application semantics. By subdividing transactions into various categories, and utilizing a commutativity property, we demonstrate cheaper techniques and show that they guarantee correctness. A performance comparison between our techniques and conventional ones quantifies the extent of the savings.
The group paradigm for concurrency control
Authors: El Abbadi Amr , Toueg Sam
Published: November 2005

We propose a paradigm for developing, describing and proving the correctness of concurrency control protocols for replicated databases in the presence of failures or communication restrictions. Our approach is to hierarchically divide the problem of achieving one-copy serializability by introducing the notion of a “group” that is a higher level of abstraction than transactions. Instead of dealing with the overall problem of serializing all transactions, our paradigm divides the problem into two simpler ones. (1) A
local policy
for each group that ensures a total order of all transactions in that group. (2) A
global policy
that ensures a correct serialization of all groups. We use the paradigm to demonstrate the similarities between several concurrency control protocols by comparing the way they achieve correctness.
Multidatabase update issues
Authors: Breitbart Yuri , Silberschatz Avi
Published: November 2005

A formal model of data updates in a multidatabase environment is developed, and a theory of concurrency control in such an environment is presented. We formulate a correctness condition for the concurrency control mechanism and propose a protocol that allows concurrent execution of a set of global transactions in presence of local ones. This protocol ensures the consistency of the multidatabase and deadlock freedom. We use the developed theory to prove the protocol's correctness and discuss complexity issues of implementing the proposed protocol.
Data functions, datalog and negation
Authors: Abiteboul Serge , Hull Richard
Published: November 2005

Datalog is extended to incorporate single-valued “data functions”, which correspond to attributes in semantic models, and which may be base (user-specified) or derived (computed). Both conventional and stratified datalog are considered. Under the extension, a datalog program may not be consistent, because a derived function symbol may evaluate to something which is not a function. Consistency is shown to be undecidable, and is decidable in a number of restricted cases. A syntactic restriction,
panwise consistency
, is shown to guarantee consistency. The framework developed here can also be used to incorporate single-valued data functions into the Complex Object Language (COL), which supports deductive capabilities, complex database objects, and set-valued data functions.

There is a natural correspondence between the extended datalog introduced here, and the usual datalog with functional dependencies. For families Φ and Γ of dependencies and a family of datalog programs Λ, the Φ-Γ
implication problem
for Λ asks, given sets F ⊆ Φ and G ⊆ Γ and a program P in Λ, whether for all inputs I, I @@@@ F implies P(I) @@@@ G. The FD-FD implication problem is undecidable for datalog, and the TGD-EGD implication problem is decidable for stratified datalog. Also, the Ø-MVD problem is undecidable (and hence also the MVD-preservation problem).
A characterization of constant-time maintainability for BCNF database schemes
Authors: Hernández Héctor J. , Chan Edward P. F.
Published: November 2005

The
maintenance problem
(for database states) of a database scheme R with respect to a set of functional dependencies
F
is the following decision problem. Let r be a consistent state of R with respect to
F
and assume we insert a tuple
t
into

r
p

ε r. Is r ∪ {
t
} a consistent state of R with respect to
F
? R is said to be
constant-time-maintainable
with respect to
F
if there is an algorithm that solves the maintenance problem of R with respect to
F
in time independent of the state size.

A characterization of constant-time-maintainability for the class of BCNF database schemes is given. An efficient algorithm that tests this characterization is shown, as well as an algorithm for solving the maintenance problem in time independent of the state size. It is also proven that constant-time-maintainable BCNF database schemes are bounded. In particular, it is shown that total projections of the representative instance can be computed via unions of projections of extension joins. Throughout we assume that database schemes are cover embedding and BCNF, and that functional dependencies are given in the form of key dependencies.
A polynomial time algorithm for testing implications of a join dependency and embodied functional dependencies
Authors: Leuchner J. , Miller L. , Slutzki G.
Published: November 2005

The problem of deciding whether a full join dependency (JD) ⋈ [
R
] and a set of functional dependencies (FDs)
F
imply an embedded join dependency (EJD) ⋈ [
S
] is known to be NP-complete. We show that the problem can be decided in polynomial time if
S
⊆
R
and
F
is embedded in
R
. Our work uses arguments based on an extension of complete intersection graphs rather than tableaus. This approach has facilitated our results and should prove useful for future research.
The powerset algebra as a result of adding programming constructs to the nested relational algebra
Authors: Gyssens Marc , van Gucht Dirk
Published: November 2005

In this paper, we discuss augmentations of the nested relational algebra with programming constructs, such as while-loops and for-loops. We show that the algebras obtained in this way are equivalent to a slight extension of the powerset algebra, thus emphasizing both the strength and the naturalness of the powerset algebra as a tool to manipulate nested relations, and, at the same time, indicating more direct ways to implement this algebra.
High contention in a stock trading database: a case study
Authors: Peinl Peter , Reuter Andreas , Sammer Harald
Published: November 2005

Though in general, current database systems adequately support application development and operation for online transaction processing (OLTP), increasing complexity of applications and throughput requirements reveal a number of weaknesses with respect to the data model and implementation techniques used. By presenting the experiences gained from a case study of a large, high volume stock trading system, representative for a broad class of OLTP applications, it is shown, that this particularly holds for dealing with high frequency access to a small number of data elements (hot spots). As a result, we propose extended data types and several novel mechanisms, which are easy to use and highly increase the expressional power of transaction oriented programming, that effectively cope with hot spots. Moreover, their usefulness and their ability to increased parallelism is exemplified by the stock trading application.
A benchmark of NonStop SQL on the debit credit transaction
Authors: Tandem Performance Group
Published: November 2005

NonStop SQL is an implementation of ANSI SQL on Tandem Computer Systems Debit Credit is a widely used industry-standard transaction. This paper summarizes a benchmark of NonStop SQL which demonstrated linear growth of throughout from 14 to 208 Debit Credit transactions per second as the hardware grew from 2 to 32 processors. The benchmark also compared the performance of NonStop SQL to the performance of a record-at a time file system interface