bluuebunny/crossref_metadata_2025 huggingface dataset:
Artemis message exchange framework
Authors: Bicer Veli , Laleci Gokce B. , Dogac Asuman , Kabak Yildiray
Published: November 2005

One of the most challenging problems in the healthcare domain is providing interoperability among healthcare information systems. In order to address this problem, we propose the semantic mediation of exchanged messages. Given that most of the messages exchanged in the healthcare domain are in EDI (Electronic Data Interchange) or XML format, we describe how to transform these messages into OWL (Web Ontology Language) ontology instances. The OWL message instances are then mediated through an ontology mapping tool that we developed, namely, OWLmt. OWLmt uses OWL-QL engine which enables the mapping tool to reason over the source ontology instances while generating the target ontology instances according to the mapping patterns defined through a GUI.Through a prototype implementation, we demonstrate how to mediate between HL7 Version 2 and HL7 Version 3 messages. However, the framework proposed is generic enough to mediate between any incompatible healthcare standards that are currently in use.
CMM and TODS
Authors: Snodgrass Richard
Published: November 2005

The
Capability Maturity Model
[4] is an orderly way for organizations to determine the capabilities of their current processes for developing software and to establish priorities for improvement [2]. It defines five levels of progressively more mature process capability [3].
ExOR
Authors: Biswas Sanjit , Morris Robert
Published: November 2005

This paper describes ExOR,an integrated routing and MAC protocol that increases the throughput of large unicast transfers in multi-hop wireless networks. ExOR chooses each hop of a packet's route after the transmission for that hop, so that the choice can reflect which intermediate nodes actually received the transmission. This deferred choice gives each transmission multiple opportunities to make progress. As a result ExOR can use long radio links with high loss rates, which would be avoided by traditional routing. ExOR increases a connection's throughput while using no more network capacity than traditional routine.ExOR's design faces the following challenges. The nodes that receive each packet must agree on their identities and choose one forwarder.The agreement protocol must have low overhead, but must also be robust enough that it rarely forwards a packet zero times or more than once. Finally, ExOR must choose the forwarder with the lowest remaining cost to the ultimate destination.Measurements of an implementation on a 38-node 802.11b test-bed show that ExOR increases throughput for most node pairs when compared with traditional routing. For pairs between which traditional routing uses one or two hops, ExOR's robust acknowledgments prevent unnecessary retransmissions,increasing throughput by nearly 35%. For more distant pairs, ExOR takes advantage of the choice of forwarders to provide throughput gains of a factor of two to four.
CUTE
Authors: Sen Koushik , Marinov Darko , Agha Gul
Published: November 2005

In
unit testing
, a program is decomposed into units which are collections of functions. A part of unit can be tested by generating inputs for a single entry function. The entry function may contain pointer arguments, in which case the inputs to the unit are
memory graphs
. The paper addresses the problem of automating unit testing with memory graphs as inputs. The approach used builds on previous work combining
symbolic
and
concrete execution
, and more specifically, using such a combination to
generate test inputs
to explore all feasible execution paths. The current work develops a method to represent and track constraints that capture the behavior of a symbolic execution of a unit with memory graphs as inputs. Moreover, an efficient constraint solver is proposed to facilitate incremental generation of such test inputs. Finally, CUTE, a tool implementing the method is described together with the results of applying CUTE to real-world examples of C code.
Implementing declarative overlays
Authors: Loo Boon Thau , Condie Tyson , Hellerstein Joseph M. , Maniatis Petros , Roscoe Timothy , Stoica Ion
Published: November 2005

Overlay networks are used today in a variety of distributed systems ranging from file-sharing and storage systems to communication infrastructures. However, designing, building and adapting these overlays to the intended application and the target environment is a difficult and time consuming process.To ease the development and the deployment of such overlay networks we have implemented P2, a system that uses a declarative logic language to express overlay networks in a highly compact and reusable form. P2 can express a Narada-style mesh network in 16 rules, and the Chord structured overlay in only 47 rules. P2 directly parses and executes such specifications using a dataflow architecture to construct and maintain overlay networks. We describe the P2 approach, how our implementation works, and show by experiment its promising trade-off point between specification complexity and performance.
A modular and open object-oriented database system
Authors: Thatte Satish M.
Published: November 2005

On 30 August 1990, Texas Instruments Incorporated, Dallas, TX was awarded a three year contract (Contract No. DAAB07-90-C-B920) to develop a modular and open object-oriented database system. The contract is funded by DARPA/ISTO and is being managed by the U.S. Army, CECOM, Fort Monmouth, N.J. The contract is being executed at TI's Information Technologies Laboratory, Computer Science Center, Dallas, Texas. So far, we have received an outstanding response from interested parties (database research community, OODB application developers, OODB builders) to our contract award announcement. This communication is a collection of most commonly asked questions and answers to them.
Temporal databases status and research directions
Authors: Snodgrass Richard
Published: November 2005

It seems somehow fitting to begin this paper on databases that store historical information with a chronology, touching briefly on all work that I am aware of in this area. I discuss in some detail what I consider to be the ten most important papers and events in terms of their impact on the discipline of temporal databases. These are emphatically not meant to detract from the other excellent papers in temporal databases. My goal is to characterize the evolution of this field, as an introduction to the approximately 350 papers specifically relating time to databases that have appeared thus far. I then identify and discuss areas where more work is needed.
The design of the Triton nested relational database system
Authors: Harvey Tina M. , Schnepf Craig W. , Roth Mark A.
Published: November 2005

Unique database requirements of applications such as computer-aided design (CAD), computer-aided software engineering(CASE), and office information systems(OIC) have driven the development of new data models and database systems based on these new models. In particular, the goal of these new database systems is to exploit the advantages of complex data models that are more efficient (in terms of time and space) than their relational counterparts.

In this paper, we describe the design and implementation of the Triton nested relational database system, a prototype system based on the nested relational data model. Triton is intended to be used as the backend storage and access component of the aforementioned applications.

This paper describes the architecture of the Triton system, and compares the performance of the nested relational model versus the relational model using Triton. In addition, this paper evaluates the EXODUS extensible database toolkit used in the development of the Triton system including key features of the persistent programming language E and the EXODUS storage manager.
An overview of three commercial object-oriented database management systems
Authors: Soloviev Valery
Published: November 2005

We present an analysis of three current object-oriented DBMS products: ONTOS, ObjectStore, and O2, as described by their available documentation. The most attractive feature of ONTOS and Object-Store is their use of C++ as a user interface - a widespread object-oriented language. They also provide persistent data implementation, transaction and recovery mechanisms, and modern application development tool sets following the recommendations of [Atkinson et al. 89]. O2 was chosen for a well-developed data type system and end-user interface, and for its reputation from the literature.
Advanced capabilities of the outer join
Authors: David Michael M.
Published: November 2005

This paper demonstrates that the modeling of complex data structures can be performed easily and naturally in SQL using the direct outer join operation as defined in the proposed ISO-ANSI SQL2 standard. This paper goes on to demonstrate four advanced capabilities that can be implemented by SQL vendors utilizing the data modeling ability of the outer join. These capabilities are: powerful optimization techniques that can dynamically shorten the access path length; intelligent join view updates that utilize the semantics in the data structure being modeled; direct disparate heterogeneous database access that is transparent and efficient; and automatic conversion of multi-table structures into nested relations allowing for more powerful SQL operations.
A denotational semantics for the Starburst production rule language
Authors: Widom Jennifer
Published: November 2005

Researchers often complain that the behavior of database production rules is difficult to reason about and understand, due in part to the lack of formal declarative semantics. It has even been claimed that database production rule languages inherently cannot be given declarative semantics, in contrast to, e.g., deductive database rule languages. In this short paper we dispute this claim by giving a denotational semantics for the Starburst database production rule language.
SQL/SE
Authors: Roddick John F.
Published: November 2005

The incorporation of a knowledge of time within database systems allows for temporally related information to be modelled more naturally and consistently. Adding this support to the metadatabase further enhances its semantic capability and allows elaborate interrogation of data. This paper presents SQL/SE, an SQL extension capable of handling schema evolution in relational database systems.
Semantic optimization
Authors: Kowarschick Wolfgang L. J.
Published: November 2005

Residues have been proved to be a very important means for doing semantic optimization. In this paper we will discuss a new kind of residues—the disjunctive residues. It will be shown that they are very useful to perform subformula elimination, if, in addition, a powerful reduction algorithm is available.
A glossary of temporal database concepts
Authors: Jensen C. S. , Clifford J. , Gadia S. K. , Segev A. , Snodgrass Richard Thomas
Published: November 2005

This glossary contains concepts specific to temporal databases that are well-defined, well understood, and widely used. In addition to defining and naming the concepts, the glossary also explains the decisions made. It lists competing alternatives and discusses the pros and cons of these. It also includes evaluation criteria for the naming of concepts.

This paper is a structured presentation of the results of e-mail discussions initiated during the preparation of the first book on temporal databases,
Temporal Databases: Theory, Design, and Implementation,
published by Benjamin Cummings, to appear January 1993. Independently of the book, an initiative aimed at designing a consensus Temporal SQL is under way. The paper is a contribution towards establishing common terminology, an initial subtask of this initiative.
A review of recent work on multi-attribute access methods
Authors: Lomet David
Published: November 2005

Most database systems provide database designers with single attribute indexing capability via some form of B+tree. Multi-attribute search structures are rare, and are mostly found in systems specialized to some more narrow application area, e.g. geographic databases. The reason is that no multi-attirbute search structure has been demonstrated, with high confidence. Multi-attribute search is an active area of research. This paper reviews the state of this field and some of the difficult problems, and reviews some recent notable papers.
Opportunities in the US from NSF, DARPA, and NASA
Authors: Winslett Marianne
Published: November 2005

In this issue, we begin with general information about the High Performance Computing and Communications (HPCC) Program at NSF, followed by a more focused look at HPCC work in the database area, and a close-up of the new scientific databases initiative. A NASA program for intelligent systems, DARPA programs in 3-D visualization and multiple knowledge sources, news of recent events at DARPA, and two new small business solicitations round out the funding news for this issue.
Structure and semantics in OODB class specifications
Authors: Geller J. , Perl Y. , Neuhold E. J.
Published: November 2005

A class specification contains both structural aspects and semantic aspects. We introduce a mathematically based distinction between structural and semantic aspects. We show how this distinction is used to identify all structural aspects of a class specification to be included in the
object type
of a class. The model obtained is called the Dual Model due to the separation of structure and semantics in the class specification. Advantages of the separation of structure and semantics have been discussed in previous papers and include separate hierarchies for structural and semantic aspects, refined inheritance mechanisms, support of physical database design and
structural integration
which is impossible in other models.
Semantic vs. structural resemblance of classes
Authors: Fankhauser Peter , Kracker Martin , Neuhold Erich J.
Published: November 2005

We present an approach to determine the similarity of classes which utilized
fuzzy
and
incomplete
terminological knowledge together with schema knowledge. We clearly distinguish between
semantic
similarity determining the degree of resemblance according to real world semantics, and
structural correspondence
explaining
how
classes can actually be interrelated. To compute the
semantic similarity
we introduce the notion of
semantic relevance
and apply fuzzy set theory to reason about both terminological knowledge and schema knowledge.
Data manipulation in heterogeneous databases
Authors: Chatterjee Abhirup , Segev Arie
Published: November 2005

Many important information systems applications require access to data stored in multiple heterogeneous databases. This paper examines a problem in interdatabase data manipulation within a heterogeneous environment, where conventional techniques are no longer useful. To solve the problem, a broader definition for join operator is proposed. Also, a method to probabilistically estimate the accuracy of the join is discussed.
Funding for small US businesses and from DARPA and NASA
Authors: Winslett Marianne
Published: November 2005

This column is the first of a regular series describing database funding programs in the United States and abroad. I plan to include profiles of major funding agencies and programs, major efforts underway, new calls for proposals, and the outcomes of funding initiatives. I welcome submissions of relevant material; they can be sent to winslett@cs.uiuc.edu. In this issue, I describe funding in the database area for innovative research in small US businesses, and new requests for proposals from DARPA and from NASA.
Rule condition testing and action execution in Ariel
Authors: Hanson Eric N.
Published: November 2005

This paper describes testing of rule conditions and execution of rule actions in Ariel active DBMS. The Ariel rule system is tightly coupled with query and update processing. Ariel rules can have conditions based on a mix of patterns, events, and transitions. For testing rule conditions, Ariel makes use of a discrimination network composed of a special data structure for testing single-relation selection conditions efficiently, and a modified version of the TREAT algorithm, called A-TREAT, for testing join conditions. The key modification to TREAT (which could also be used in the Rete algorithm) is the use of virtual α-memory nodes which save storage since they contain only the predicate associated with the memory node instead of copies of data matching the predicate. The rule-action executor in Ariel binds the data matching a rule's condition to the action of the rule at rule fire time, and executes the rule action using the query processor.
Behavior of database production rules
Authors: Aiken Alexander , Widom Jennifer , Hellerstein Joseph M.
Published: November 2005

Static analysis methods are given for determining whether arbitrary sets of database production rules are (1) guaranteed to terminate; (2) guaranteed to produce a unique final database state; (3) guaranteed to produce a unique stream of observable actions. When the analysis determines that one of these properties is not guaranteed, it isolates the rules responsible for the problem and determines criteria that, if satisfied, guarantee the property. The analysis methods are presented in the context of the Starburst Rule System; they will form the basis of an interactive development environment for Starburst rule programmers.
DOODLE: a visual language for object-oriented databases
Authors: Cruz Isabel F.
Published: November 2005

In this paper we introduce DOODLE, a new visual and declarative language for object-oriented databases. The main principle behind the language is that it is possible to
display and query the database with arbitrary pictures
. We allow the user to tailor the display of the data to suit the application at hand or her preferences. We want the user-defined visualizations to be stored in the database, and the language to express all kinds of visual manipulations. For extendibility reasons, the language is object-oriented. The semantics of the language is given by a well-known deductive query language for object-oriented databases. We hope that the formal basis of our language will contribute to the theoretical study of database visualizations and visual query languages, a subject that we believe is of great interest, but largely left unexplored.
A transformation-based approach to optimizing loops in database programming languages
Authors: Lieuwen Daniel F. , DeWitt David J.
Published: November 2005

Database programming languages like
O
2
,
E
, and
O
++ include the ability to iterate through a set. Nested iterators can be used to express joins. This paper describes compile-time optimizations similar to relational transformations like join reordering for such programming constructs. This paper also shows how to use a standard transformation-based optimizer to optimize these joins. An optimizer built using the EXODUS Optimizer Generator [GRAE87] was added to the Bell Labs
O
++ [AGRA89] compiler. We used the resulting optimizing compiler to experimentally validate the ideas in this paper. The experiments show that this technique can significantly improve the performance of database programming languages.
H-trees: a dynamic associative search index for OODB
Authors: Low Chee Chin , Ooi Beng Chin , Lu Hongjun
Published: November 2005

The support of the superclass-subclass concept in object-oriented databases (OODB) makes an instance of a subclass also an instance of its superclass. As a result, the access scope of a query against a class in general includes the access scope of all its subclasses, unless specified otherwise. To support the superclass-subclass relationship efficiently, the index must achieve two objectives. First, the index must support efficient retrieval of instances from a single class. Second, it must also support efficient retrieval of instances from classes in a hierarchy of classes. In this paper, we propose a new index called the H-tree that supports efficient retrieval of instances of a single class as well as retrieval of instances of a class and its subclasses. The unique feature of H-trees is that they capture the superclass-subclass relationships. A performance analysis is conducted and both experimental and analytical results indicate that the H-tree is an efficient indexing structure for OODB.
On the performance of object clustering techniques
Authors: Tsangaris Manolis M. , Naughton Jeffrey F.
Published: November 2005

We investigate the performance of some of the best-known object clustering algorithms on four different workloads based upon the tektronix benchmark. For all four workloads, stochastic clustering gave the best performance for a variety of performance metrics. Since stochastic clustering is computationally expensive, it is interesting that for every workload there was at least one cheaper clustering algorithm that matched or almost matched stochastic clustering. Unfortunately, for each workload, the algorithm that approximated stochastic clustering was different. Our experiments also demonstrated that even when the workload and object graph are fixed, the choice of the clustering algorithm depends upon the goals of the system. For example, if the goal is to perform well on traversals of small portions of the database starting with a cold cache, the important metric is the per-traversal expansion factor, and a well-chosen placement tree will be nearly optimal; if the goal is to achieve a high steady-state performance with a reasonably large cache, the appropriate metric is the number of pages to which the clustering algorithm maps the active portion of the database. For this metric, the PRP clustering algorithm, which only uses access probabilities achieves nearly optimal performance.
Using multiversioning to improve performance without loss of consistency (Abstract Only)
Authors: Bamford Roger
Published: November 2005

Oracle first implemented multiversioning, which was called read consistency, in Version 4 (ea. 1983) of the kernel. It supported the old master/new master programming paradigm for both application builders and query-processor implementors while avoiding the reader/writer serialization that results from using automatic share locks. The resulting transaction consistency model was arcane, not exactly serializable, but pragmatic in actual use. In this session, Mr. Bamford will cover read consistency from a number of viewpoints. First, the model will be described and a little detail about Oracles current implementation will be given. Next, the consequences of having read consistency as part of the databases core architecture will be discussed. In particular, the effects on the designs for row locking, query processing, distributed query, distributed cache coherence, referential integrity, and set updates will be described. This will be followed by a comparison of Oracles read consistency model to other common concurrency models, looking at cost and throughput under a variety of workloads, Finally, Mr. Barnford will propose how Oracle intends to carry read consistency into the future as support is added for complex objects, distributed computations, and long transactions.
Crash recovery in client-server EXODUS
Authors: Franklin Michael J. , Zwilling Michael J. , Tan C. K. , Carey Michael J. , DeWitt David J.
Published: November 2005

In this paper, we address the correctness and performance issues that arise when implementing logging and crash recovery in a page-server environment. The issues result from two characteristics of page-server systems: 1) the fact that data is modified and cached in client database buffers that are not accessible by the server, and 2) the performance and cost trade-offs that are inherent in a client-server environment. We describe a recovery system that we have implemented for the client-server version of the EXODUS storage manager. The implementation supports efficient buffer management policies, allows flexibility in the interaction between clients and the server, and reduces the server load by generating log records at clients. We also present a preliminary performance analysis of the implementation.
MLR: a recovery method for multi-level systems
Authors: Lomet David B.
Published: November 2005

To achieve high concurrency in a database system has meant building a system that copes well with important special cases. Recent work on multi-level systems suggest a systematic path to high concurrency. A multi-level system using locks permits restrictive low level locks of a subtransaction to be replaced with less restrictive high level locks when sub-transactions commit, enhancing concurrency. This is possible because sub-transactions can be undone via high level compensation actions rather than by restoring a prior lower level state. We describe a recovery scheme, called Multi-Level Recovery (MLR) that logs this high level undo operation with the commit record for the subtransaction that it compensates, posting log records to only a single log. A variant of the method copes with nested transactions, and both nested and multi-level transactions can be treated in a unified fashion.
Fast search in main memory databases
Authors: Analyti Anastasia , Pramanik Sakti
Published: November 2005

The objective of this paper is to develop and analyze high performance hash based search methods for main memory databases. We define optimal search in main memory databases as the search that requires at most one key comparison to locate a record. Existing hashing techniques become impractical when they are adapted to yield optimal search in main memory databases because of their large directory size. Multi-directory hashing techniques can provide significantly improved directory utilization over single-directory hashing techniques. A multi-directory hashing scheme, called fast search multi-directory hashing, and its generalization, called controlled search multi-directory hashing, are presented. Both methods achieve linearly increasing expected directory size with the number of records. Their performance is compared to existing alternatives.
Improving fault tolerance and supporting partial writes in structured coterie protocols for replicated objects
Authors: Rabinovich Michael , Lazowska Edward D.
Published: November 2005

This paper presents a new technique for efficiently controlling replicas in distributed systems. Conventional structured coterie protocols are efficient but incur a penalty of reduced availability in exchange for the performance gain. Further, the performance advantage can only be fully realized when write operations always
replace
the old data item with the new value instead of
updating a portion
of the data item. Our new approach significantly improves availability while allowing partial write operations.

After presenting our general approach, we apply it to an existing structured coterie protocol and analyze the availability of the resulting protocol. We also show that other classes of protocols can make use of our approach.
An efficient scheme for providing high availability
Authors: Bhide Anupam , Goyal Ambuj , Hsiao Hui-I , Jhingran Anant
Published: November 2005

Replication at the partition level is a promising approach for increasing availability in a Shared Nothing architecture. We propose an algorithm for maintaining replicas with little overhead during normal failure-free processing. Our mechanism updates the secondary replica in an asynchronous manner: entire dirty pages are sent to the secondary at some time before they are discarded from primary's buffer. A log server node (hardened against failures) maintains the log for each node. If a primary node fails, the secondary fetches the log from the log server, applied it to its replica, and brings itself to the primary's last transaction-consistent state. We study the performance of various policies for sending pages to secondary and the corresponding trade-offs between recovery time and overhead during failure-free processing.
Optimization of object-oriented recursive queries using cost-controlled strategies
Authors: Lanzelotte Rosana S. G. , Valduriez Patrick , Zaït Mohamed
Published: November 2005

Object-oriented data models are being extended with recursion to gain expressive power. This complicates the optimization problem which has to deal with recursive queries on complex objects. Because unary operations invoking methods or path expressions on objects may be costly to execute, traditional heuristics for optimizing recursive queries are no longer valid. In this paper we propose a cost-based optimization method which handles object-oriented recursive queries. In particular, it is able to delay the decision of pushing selective operations through recursion until the effect of such a transformation can be measured by a cost model. The approach integrates rewriting and increases the optimization opportunities for recursive queries on objects while allowing for efficient optimization.
The performance of three database storage structures for managing large objects
Authors: Biliris Alexandros
Published: November 2005

This study analyzes the performance of the storage structures and algorithms employed in three experimental database storage systems – EXODUS, Starburst, and EOS – for managing large unstructured general-purpose objects. All three mechanisms are segment-based in that the large object is stored in a sequence of segments, each consisting of physically continuous disk block. To analyze the algorithms we measured object creation time, sequential scan time, storage utilization in the presence of updates, and the I/O cost of random reads, inserts, and deletes.
Continuous queries over append-only databases
Authors: Terry Douglas , Goldberg David , Nichols David , Oki Brian
Published: November 2005

In a database to which data is continually added, users may wish to issue a permanent query and be notified whenever data matches the query. If such
continuous queries
examine only single records, this can be implemented by examining each record as it arrives. This is very efficient because only the incoming record needs to be scanned. This simple approach does not work for queries involving joins or time. The Tapestry system allows users to issue such queries over a database of mail and bulletin board messages. The user issues a static query, such as “show me all messages that have been replied to by Jones,” as though the database were fixed and unchanging. Tapestry converts the query into an incremental query that efficiently finds new matches to the original query as new messages are added to the database. This paper describes the techniques used in Tapestry, which do not depend on triggers and thus be implemented on any commercial database that supports SQL. Although Tapestry is designed for filtering mail and news messages, its techniques are applicable to any append-only database.
Sequential sampling procedures for query size estimation
Authors: Haas Peter J. , Swami Arun N.
Published: November 2005

We provide a procedure, based on random sampling, for estimation of the size of a query result. The procedure is sequential in that sampling terminates after a random number of steps according to a stopping rule that depends upon the observations obtained so far. Enough observations are obtained so that, with a pre-specified probability, the estimate differs from the true size of the query result by no more than a prespecified amount. Unlike previous sequential estimation procedures for queries, our procedure is asymptotically efficient and requires no
ad hoc
pilot sample or a
a priori
assumptions about data characteristics. In addition to establishing the asymptotic properties of the estimation procedure, we provide techniques for reducing undercoverage at small sample sizes and show that the sampling cost of the procedure can be reduced through stratified sampling techniques.
Access method concurrency with recovery
Authors: Lomet David , Salzberg Betty
Published: November 2005

Providing high concurrency in B
+
-trees has been studied extensively. But few efforts have been documented for combining concurrency methods with a recovery scheme that preserves well-formed trees across system crashes. We describe an approach for this that works for a class of index trees that is a generalization of the B
link
-tree. A major feature of our method is that it works with a range of different recovery methods. It achieves this by decomposing structure changes in an index tree into a sequence of atomic actions, each one leaving the tree well-formed and each working on a separate level of the tree. All atomic actions on levels of the tree above the leaf level are independent of database transactions, and so are of short duration.
A general framework for the optimization of object-oriented queries
Authors: Cluet Sophie , Delobel Claude
Published: November 2005

The goal of this work is to integrate in a general framework the different query optimization techniques that have been proposed in the object-oriented context. As a first step, we focus essentially on the logical aspect of query optimization. In this paper, we propose a formalism (i) that unifies different rewriting formalisms, (ii) that allows easy and exhaustive factorization of duplicated subqueries, and (iii) that supports heuristics in order to reduce the optimization rewriting phase.
Query processing in the ObjectStore database system
Authors: Orenstein Jack , Haradhvala Sam , Margulies Benson , Sakahara Don
Published: November 2005

ObjectStore is an object-oriented database system supporting persistence orthogonal to type, transaction management, and associative queries. Collections are provided as objects. The data model is non-1NF, as objects may have embedded collections. Queries are integrated with the host language in the form of query operators whose operands are a collection and a predicate. The predicate may itself contain a (nested) query operating on an embedded collection. Indexes on paths may be added and removed dynamically. Collections, being treated as objects, may be referred to indirectly, e.g., through a by-reference argument. For this reason and others, multiple execution strategies are generated, and a final selection is made just prior to query execution. Nested queries can result in interleaved execution and strategy selection.
Locking protocols for concurrency control in real-time database systems
Authors: Hung S. L. , Lam K. Y.
Published: November 2005

Concurrency Control in real-time database systems is complicated by the requirement to maintain database consistency at the same time to minimize the number of transactions missing their deadlines. The scheduling of data in Basic Two Phase Locking (2PL) completely ignores the urgency of a transaction and thus the effectiveness of the adopted real-time resource scheduling protocol is greatly reduced. In Restart based locking protocols (R2PL), same priorities are used for both data and resources scheduling and should have fewer transactions missing their deadlines. However, Restart based protocols sufferred the intrinsic weakness of high restart overhead owing to ensure atomicity of transactions. In this paper, based on their weaknesses, a hybrid concurrency control protocol (H2PL) is proposed. Through performance study, results indicate that it can perform well under different degree of deadline constraint and workload as compared with other real-time locking protocols.
The winds of change?
Authors: Winslett Marianne
Published: November 2005

In this issue, we bring you coverage of recent events in the US that may have an impact on database funding, especially at NSF. We also announce two upcoming NSF Small Business Innovative Research Conferences and requests for proposals from the Air Force, the Army, and the folks at the Strategic Defense Initiative. A new database/knowledge-base BAA and other bits of news from DARPA round out the funding news for this issue.
Data management for mobile computing
Authors: Imieĺinski Tomasz , Badrinath B. R.
Published: November 2005

Mobile Computing is a new emerging computing paradigm of the future. Data Management in this paradigm poses many challenging problems to the database community. In this paper we identify these new challenges and plan to investigate their technical significance. New research problems include management of location dependent data, wireless data broadcasting, disconnection management and energy efficient data access.
Database research at AT&T Bell Laboratories
Authors: Jagadish H. V.
Published: November 2005

Bell Laboratories is the Research and Development arm of AT&T. There is today tremendous support for database research in Bell Labs and in AT&T. This is expected to continue since database technology is recognized as being central not just to Teradata, NCR, and AT&T's computing business but to its core communication business as well. What you see described below is a survey of the current state of a young and growing research effort in the database area. You should expect to see a stronger “resume” a few years down the road.

Research at AT&T Bell Labs is never directed from above, towards specific projects or objectives. Individual researchers select their areas of research based on a combination of factors that include individual skill and interest, other on-going activity and potential for collaboration, and the likelihood of intellectual or monetary impact. While research activity can range from the highly theoretical to the completely applied, it is expected that most research be performed within the framework of some larger objective; and this framework is typically provided by a prototype system.

In addition to the core set of people here full-time, often there are visitors. You will see the names of many of these in the publications listed. For instance, most recently Oded Shmueli from the Technion spent a year with us. Currently, Avi Silberschatz is visiting from Austin.
Data base directions information resource management-making it work, executive summary
Authors: Fong Elizabeth N. , Goldfine Alan H.
Published: November 2005

On October 21-23, 1985, the Institute for Computer Sciences and Technology of the National Bureau of Standards (NBS), in cooperation with the Association for Computing Machinery Special Interest Group on Management of Data (ACM SIGMOD), the IEEE Computer Society Technical Committee on Database Engineering, and the Federal Data Management Users Group (FEDMUG), held the fourth in their series of Data Base Directions workshops. The purpose of this workshop was to assess the nature of current information resource management (IRM) practice and problems, and to explore solutions which have proven workable.
A logic-programming/object-oriented cocktail
Authors: Bancilhon Francois
Published: November 2005

I define a simple data model which is based on an object oriented approach and uses logic programming as a computational model. The query part of the data model is purely declarative and has a fixpoint semantics, while the update part is imperative and uses assignments.
A survey of distributed deadlock detection algorithms
Authors: Elmagarmid Ahmed K.
Published: November 2005

This paper surveys research work performed within the last five years in distributed deadlock detection. The last survey paper on this topic appeared in 1980; since that time a large number of interesting algorithms have been discribed in the literature. A new, more efficient scheme is the probe-based deadlock detection strategy used by many of the new algorithms. This paper will concentrate on distributed deadlock detection algorithms. Only detection of resource deadlocks will be reviewed here, though other types of deadlock handling strategies and environments are briefly mentioned.
Third normal form made easy
Authors: Salzberg Betty
Published: November 2005

Third normal form is defined in different inequivalent ways in elementary data base textbooks. The method given in many of these books for decomposing a file into third normal form is non-algorithmic, depends on human recognition of a pattern, and has severe limitations and unexplained complexities. This is not necessary. There is an excellent algorithmic method available which is easy to learn, and which can be programmed.

The objective of this paper is to examine the differences concerning how third normal form is presented in various textbooks, and to present an easy way of introducing it to students.

This article appeared previously in the June 1986 issue of SIGCSE BULLETIN.
Missing information (applicable and inapplicable) in relational databases
Authors: Codd E. F.
Published: November 2005

There has been some technical and justified criticism of the treatment of missing information in the data sublanguage SQL and in IBM's Database 2 system (a relational database management system). Some of this criticism has been directed (by mistake) at the relational model. The purpose of this paper is to clarify and extend the treatment of missing information by the relational model.

The clarification places heavy emphasis on the semantic aspects of missing information. The extension, which is relatively minor, provides a systematic approach (independent of data type) to dealing with the inapplicability of certain properties to some objects. This extension does not invalidate any part of the present version of the relational model.
SIGMOD goes online
Authors: Winslett Marianne
Published: November 2005

ACM SIGMOD is pleased to announce a new set of on line services for members, including on line copies of portions of the SIGMOD
Record
(including all funding columns since 1991, and wider coverage of the
Record
beginning with this issue), an archive of recent conference announcements, and a database of funding information. These services are fully functional and ready for use today. The remainder of this message explains how to access the services, and why you should access them in the manner suggested.
Helping computer scientists in Romania
Authors: Athanasiu Irina
Published: November 2005

As a Professor in the Computer Science Department of the Polytechnical Institute of Bucharest, Romania, I would like to bring to your attention the effort of a group of professionals, researchers, students and professors around the world. This effort, called “Free UNIX for Romania”, has been initiated and coordinated by Marius Hancu, an advisor at the Parallel Architectures Group, Center de Recherche Informatique de Montreal, Montreal, Canada.
Deadlock prevention in a distributed database system
Authors: Reddy P. Krishna , Bhalla Subhash
Published: November 2005

The distributed locking based approaches to concurrency control in a distributed database system, are prone to occurrence of deadlocks. An algorithm for deadlock prevention has been considered in this proposal. In this algorithm, a transaction is executed by forming wait for relations with other conflicting transactions. The technique for generation of this kind of precedence graph for transaction execution is analyzed. This approach is a fully distributed approach. The technique is free from deadlocks, avoids resubmission of transactions, and hence reduces processing delays within the distributed environment.
Timely access to future funding announcements
Authors: Winslett Marianne , Chu Iris Sheauyin
Published: November 2005

The last issue of this column appeared six months ago, so in the interim many requests for proposals have been issued, with many of their due dates already past. We are happy to announce the availability of up-to-the-minute funding information on line, so that the
Record
's publication schedule need not prevent readers' timely access to funding information. In addition, we briefly recap recent requests for proposals from NASA, NLM, the Human Brain Project, the US Army, the US Navy, ARPA, NSF, and Intel; more detailed information on any of these (except Intel) can be found in the on-line archives. We also report on news at NSF and NIST.
Relational database integration in the IBM AS/400
Authors: Scholerman S. , Miller L. , Tenner J. , Tomanek S. , Zolliker M.
Published: November 2005

A great deal of research has been focused on the development of database machines. In parallel to this work some vendors have developed general purpose machines with database function built directly into the machine architecture. The IBM AS/400 is one of the principle examples of this approach. Designed with a strong object orientation and the basis functions of the relational database model integrated into it's architecture, the AS/400 has proved to be a commercial success. In the present work we look at the database component of the AS/400.
Experiences with HyperBase
Authors: Wiil Uffe Kock
Published: November 2005

This paper describes the architecture and experiences with a hyperbase (hypertext database). HyperBase is based on the client-server model and has been designed especially to support collaboration. HyperBase has been used in a number of (hypertext) applications in our lab and is currently being used in research projects around the world to provide database support to all kinds of applications. One application from our lab is a multiuser hypertext system for collaboration which deals with three fundamental issues in simultaneous sharing: access contention, real-time monitoring and real-time communication. Major experiences with HyperBase (collaboration support, data modeling and performance) gained from use both in our lab and in different projects at other research sites are reported. One major lesson learned is that HyperBase can provide powerful support for data sharing among multiple users simultaneously sharing the same environment.
Implementation of a graph-based data model for complex objects
Authors: Levene Mark , Poulovassilis Alexandra , Benkerimi Kerima , Schwartz Sara , Tuv Eran
Published: November 2005

We have developed a graph-based data model called the Hypernode Model whose single data structure is the
hypernode
, a directed graph whose nodes may themselves reference further directed graphs. A prototype database system supporting this model is being developed at London University as part of a project whose aims are threefold: (i) to ascertain the expressiveness and flexibility of the hypernode model, (ii) to experiment with various querying paradigms for this model, and (iii) to investigate the suitability of the directed graph as a data structure supported throughout all levels of the implementation. The purpose of this paper is to report upon our findings to date.
A performance study of concurrency control in a real-time main memory database system
Authors: Gruenwald Le , Liu Sichen
Published: November 2005

Earlier performance studies of concurrency control algorithms show that in a disk-resident real-time database system, optimistic algorithms perform better than two phase locking with higher priority (2PL-HP). In a main memory real-time database system, disk I/Os are eliminated and thus more transactions are enabled to meet their real-time constraints. Lack of disk I/Os in this environment requires concurrency control be re-examined. This paper conducts a simulation study to compare 2PL-HP with a real time optimistic concurrency control algorithm (OPT-WAIT-50) for a real time main memory database system, MARS. The results show that OPT-WAIT-50 outperforms 2PL-HP with finite resources.
Inheritance and persistence in database programming languages
Authors: Buneman Peter , Atkinson Malcolm
Published: November 2005

In order to represent inheritance, several recent designs for database programming languages have made use of
class
construct, which can be thought of as a restricted data type with an associated set of instances. Moreover, these classes are persistent they survive from one program invocation to another. This paper examines whether it is necessary to the together type, extent and persistence in order to model inheritance and suggests that they may be separated to provide more general database programming languages. In particular we shall see that it is possible to assign a generic data type to a function that extracts all the objects of a given type in the database so that the class hierarchy can be derived from the type hierarchy. We shall also examine object-level inheritance and its relationship to data types for relational databases. A final section examines how the various forms of persistence interact with inheritance at both object and type level.