bluuebunny/crossref_metadata_2025 huggingface dataset:
An Illustra technical white paper
Authors: Gaffney John
Published: November 2005

Illustra's Web DataBlade module is a comprehensive toolset for creating Web-enabled database applications that dynamically retrieve and update Illustra database content. You can construct simple query front ends in a matter of minutes and powerful Web applications in just a few hours with the Web DataBlade module. The Illustra Web DataBlade makes it easy for you to take full advantage of the Illustra server's many important features, including extensible data types, an underlying rules system, and Time Travel capabilities, all of which make Illustra the database of choice for managing all types of content on the World Wide Web.
Shutdown, budget, and funding
Authors: Qian Xiaolei
Published: November 2005

There are few new funding announcements and requests for proposals, mostly due to the partial government shutdown and the budget impasse. We will report on the potential impact on NSF of the government shutdown and a 7-year balanced budget. We then briefly discuss some BAAs from ARPA, Rome Laboratory, and the Air Force.
The interpreted-compiled range of AI/DB systems
Authors: O'Hare Anthony B. , Sheth Amit P.
Published: November 2005

A range of approaches to integrating rule-based Artificial Intelligence (AI) systems and Database Management Systems are classified according to the degree of
compilation
that is performed by the AI system. This
interpreted—compiled range
provides a framework for enumerating several relevant aspects of AI/DB systems, for showing how these aspects vary along the dimension, and for comparing and contrasting previous work on AI/DB systems. In particular, this framework focuses on the nature of the interaction between the two systems as well as some of the consequences of the particular approach with respect to the utilization, functionality, and performance of each of the two systems.
Conceptual modeling in the classroom
Authors: Pletch Andrew
Published: November 2005

The conceptual model is the focal point of the process of database design. All activities either converge upon or emanate from the conceptual model. All structures, through mappings either into or out of the conceptual model, must be to some extent compatible with it. Students generally find it difficult to manage the complexity surrounding the conceptual model, its development and usage. This article describes one approach to overcoming this difficulty through an exercise in conceptual modeling and shows some of the results of this approach.
Semantic modeling through identification and characterization of objects
Authors: Jonsson Dan
Published: November 2005

So-called
semantic data models
represent the structure of some part of reality, on the one hand, and the structure of the data in some database system, on the other hand. Semantic modeling is an important tool for database design. Several techniques and tools for semantic modeling have been proposed [2, 4]. A new approach to semantic modeling — the ICAROS approach — will be presented here.
Four valued logic for relational database systems
Authors: Gessert G. H.
Published: November 2005

This paper proposes a specific four-valued logic (4VL) as a means of handling missing data in Relational Data Base Management systems. The proposed 4VL is a minor variant of the standard 4VL in which the “least true” condition is interpreted as “inapplicable” rather than “false”. The use of this 4VL is defended on the grounds that by defining several additional unary operators, the 4VL can be rendered intuitively manageable. The proposed unary operators contribute to the conceptual utility of the 4VL by providing an explicit way for users to relate familiar results of two-valued logic to analogous results in 4VL.
An SQL-based query language for networks of relations
Authors: Basu Amit , Ahad Rafiul
Published: November 2005

A set of relations can be modeled as a network through the use of
image attributes
, which are attributes defined on the domain of relation names. Such networks of relations can effectively meet many of the modeling requirements of advanced database applications such as engineering design and knowledge base systems. In this paper, we describe the features of ESQL, a novel query language that is an extension of SQL [Cham74] to exploit the added semantics of image attributes. Details of ESQL and its underlying principles can be found in [Ahad88] and [Ahad89].
Optimization of nested SQL queries revisited
Authors: Ganski Richard A. , Wong Harry K. T.
Published: November 2005

Current methods of evaluating nested queries in the SQL language can be inefficient in a variety of query and data base contexts. Previous research in the area of nested query optimization which sought methods of reducing evaluation costs is summarized, including a classification scheme for nested queries, algorithms designed to transform each type of query to a logically equivalent form which may then be evaluated more efficiently, and a description of a major bug in one of these algorithms. Further examination reveals another bug in the same algorithm. Solutions to these bugs are proposed and incorporated into a new transformation algorithm, and extensions are proposed which will allow the transformation algorithms to handle a larger class of predicates. A recursive algorithm for processing a general nested query is presented and the action of this algorithm is demonstrated. This algorithm can be used to transform any nested query.
Magic counting methods
Authors: Sacca Domenico , Zaniolo Carlo
Published: November 2005

The problem considered is that of implementing recursive queries, expressed in a logic-based language, by efficient fixpoint computations. In particular, the situation is studied where the initial bindings in the recursive predicate can be used to restrict the search space and ensure safety of execution. Two key techniques previously proposed to solve this problem are (i) the highly efficient counting method, and (ii) the magic set method which is safe in a wider range of situations than (i). In this paper, we present a family of methods, called the magic counting methods, that combines the advantages of (i) and (ii). This is made possible by the similarity of the strategies used by the counting method and the magic set method for propagating the bindings. This paper introduces these new methods, examines their computational complexity, and illustrates the trade-offs between the family members and their superiority with respect to the old methods.
A recovery algorithm for a high-performance memory-resident database system
Authors: Lehman Tobin J. , Carey Michael J.
Published: November 2005

With memory prices dropping and memory sizes increasing accordingly, a number of researchers are addressing the problem of designing high-performance database systems for managing memory-resident data. In this paper we address the recovery problem in the context of such a system. We argue that existing database recovery schemes fall short of meeting the requirements of such a system, and we present a new recovery mechanism which is designed to overcome their shortcomings. The proposed mechanism takes advantage of a few megabytes of reliable memory in order to organize recovery information on a per “object” basis. As a result, it is able to amortize the cost of checkpoints over a controllable number of updates, and it is also able to separate post-crash recovery into two phases—high-speed recovery of data which is needed immediately by transactions, and background recovery of the remaining portions of the database. A simple performance analysis is undertaken, and the results suggest our mechanism should perform well in a high-performance, memory-resident database environment.
Implementation of a compiler for a semantic data model: Experiences with taxis
Authors: Nixon Brian , Chung Lawrence , Mylopoulos John , Lauzon David , Borgida Alex , Stanley M.
Published: November 2005

The features of a compiler for the Taxis design language are described and discussed. Taxis offers an entity-based framework for designing interactive information systems and supports generalisation, classification and aggregation as abstraction mechanisms. Its features include multiple inheritance of attributes, isA hierarchies of transactions, metaclasses, typed attributes, a procedural exception-handling mechanism and an iteration construct based on the abstraction mechanisms supported Developing a compiler for the language involved dealing with the problems of efficiently representing and accessing a large collection of entities, performing (static) type checking and representing isA hierarchies of transactions.
The design of ¬ 1NF relational databases into nested normal form
Authors: Roth Mark A. , Korth Henry F.
Published: November 2005

We develop new algorithms for the design of non first normal form relational databases that are in nested normal form. Previously, a set of given multivalued dependencies and those multivalued dependencies implied by given functional dependencies were used to obtain a nested normal form decomposition of a scheme. This method ignored the semantic distinction between functional and multivalued dependencies and utilized only full multivalued dependencies in the design process. We propose new algorithms which take advantage of this distinction, and use embedded multivalued dependencies to enhance the decomposition. This results in further elimination of redundancy due to functional dependencies in nested normal form designs.
A rule-based view of query optimization
Authors: Freytag Johann Christoph
Published: November 2005

The query optimizer is an important system component of a relational database management system (DBMS). It is the responsibility of this component to translate the user-submitted query - usually written in a non-procedural language - into an efficient query evaluation plan (QEP) which is then executed against the database. The research literature describes a wide variety of optimization strategies for different query languages and implementation environments. However, very little is known about how to design and structure the query optimization component to implement these strategies.

This paper proposes a first step towards the design of a
modular query optimizer
. We describe its operations by
transformation rules
which generate different QEPs from initial query specifications. As we distinguish different aspects of the query optimization process, our hope is that the approach taken in this paper will contribute to the more general goal of a modular query optimizer as part of an extensible database management system.
A system for semantic query optimization
Authors: Shenoy Sreekumar T. , Ozsoyoglu Z. Meral
Published: November 2005

This paper describes a scheme to utilize semantic integrity constraints in optimizing a user specified query. The scheme uses a graph theoretic approach to identify redundant join clauses and redundant restriction clauses specified in a user query. An algorithm is suggested to eliminate such redundant joins and avoid unnecessary restrictions. In addition to these eliminations, the algorithm aims to introduce as many restrictions on indexed attributes as possible, thus yielding an equivalent, but potentially more profitable, form of the original query.
Architecture and implementation of the Darmstadt database kernel system
Authors: Paul H. B. , Schek H. J. , Scholl M. H.
Published: November 2005

The multi-layered architecture of the DArmStadt Data Base System (DASDBS) for advanced applications is introduced DASDBS is conceived as a family of application-specific database systems on top of a common database kernel system. The main design problem considered here is, What features are common enough to be integrated into the kernel and what features are rather application-specific? Kernel features must be simple enough to be efficiently implemented and to serve a broad class of clients, yet powerful enough to form a convenient basis for application-oriented layers. Our kernel provides mechanisms to efficiently store hierarchically structured complex objects, and offers operations which are set-oriented and can be processed in a single scan through the objects. To achieve high concurrency in a layered system, a multi-level transaction methodology is applied. First experiences with our current implementation and some lessons we have learned from it are reported.
A data management extension architecture
Authors: Lindsay Bruce , McPherson John , Pirahesh Hamid
Published: November 2005

A database management system architecture is described that facilitates the implementation of data management extensions for relational database systems. The architecture defines two classes of data management extensions alternative ways of storing relations called relation “storage methods”, and access paths, integrity constraints, or triggers which are “attachments” to relations. Generic sets of operations are defined for storage methods and attachments, and these operations must be provided in order to add a new storage method or attachment type to the system. The data management extension architecture also provides common services for coordination of storage method and attachment execution. This article describes the data management extension architecture along with some implementation issues and techniques.
Dynamic voting
Authors: Jajodia Sushil , Mutchler David
Published: November 2005

In a voting-based algorithm, a replicated file can be updated in a partition if it contains a majority of copies. In this paper, we propose an extension of this scheme which permits a file to be updated in a partition provided it contains a majority of up-to-date copies. Our scheme not only preserves mutual consistency of the replicated file, but provides improvement in its availability as well. We develop a stochastic model which gives insight into the improvements afforded by our scheme over the voting scheme.
Sagas
Authors: Garcia-Molina Hector , Salem Kenneth
Published: November 2005

Long lived transactions (LLTs) hold on to database resources for relatively long periods of time, significantly delaying the termination of shorter and more common transactions. To alleviate these problems we propose the notion of a saga. A LLT is a saga if it can be written as a sequence of transactions that can be interleaved with other transactions. The database management system guarantees that either all the transactions in a saga are successfully completed or compensating transactions are run to amend a partial execution. Both the concept of saga and its implementation are relatively simple, but they have the potential to improve performance significantly. We analyze the various implementation issues related to sagas, including how they can be run on an existing system that does not directly support them. We also discuss techniques for database and LLT design that make it feasible to break up LLTs into sagas.
A population analysis for hierarchical data structures
Authors: Nelson Randal C. , Samet Hanan
Published: November 2005

A new method termed population analysis is presented for approximating the distribution of node occupancies in hierarchical data structures which store a variable number of geometric data items per node. The basic idea is to describe a dynamic data structure as a set of populations which are permitted to transform into one another according to certain rules. The transformation rules are used to obtain a set of equations describing a population distribution which is stable under insertion of additional information into the structure. These equations can then be solved, either analytically or numerically, to obtain the population distribution. Hierarchical data structures are modeled by letting each population represent the nodes of a given occupancy. A detailed analysis of quadtree data structures for storing point data is presented, and the results are compared to experimental data. Two phenomena referred to as
aging
and
phasing
are defined and shown to account for the differences between the experimental results and those predicted by the model. The population technique is compared with statistical methods of analyzing similar data structures.
Efficiently supporting procedures in relational database systems
Authors: Sellis Timos K.
Published: November 2005

We examine an extended relational database system which supports database procedures as full fledged objects. In particular, we focus on the problems of query processing and efficient support for database procedures. First, a variation to the original INGRES decomposition algorithm is presented. Then, we examine the idea of storing results of previously processed procedures in secondary storage (
caching
). Using a cache, the cost of processing a query can be reduced by preventing multiple evaluations of the same procedure. Problems associated with cache organizations, such as replacement policies and validation schemes are examined. Another means for reducing the execution cost of queries is indexing. A new indexing scheme for cached results, Partial Indexing, is proposed and analyzed.
A graphical query language supporting recursion
Authors: Cruz Isabel F. , Mendelzon Alberto O. , Wood Peter T.
Published: November 2005

We define a language G for querying data represented as a labeled graph
G
. By considering
G
as a relation, this graphical query language can be viewed as a relational query language, and its expressive power can be compared to that of other relational query languages. We do not propose G as an alternative to general purpose relational query languages, but rather as a complementary language in which recursive queries are simple to formulate. The user is aided in this formulation by means of a graphical interface. The provision of regular expressions in G allows recursive queries more general than transitive closure to be posed, although the language is not as powerful as those based on function-free Horn clauses. However, we hope to be able to exploit well-known graph algorithms in evaluating recursive queries efficiently, a topic which has received widespread attention recently.
A study of transitive closure as a recursion mechanism
Authors: Jagadish H. V. , Agrawal Rakesh , Ness Linda
Published: November 2005

We show that every linearly recursive query can be expressed as a transitive closure possibly preceded and followed by operations already available in relational algebra. This reduction is possible even if there are repeated variables in the recursive literals and if some of the arguments in the recursive literals are constants. Such an equivalence has significant theoretical and practical ramifications. One the one hand it influences the design of expressive notations to capture recursion as an augmentation of relational query languages. On the other hand implementation of deductive databases is impacted in that the design does not have to provide the generality that linear recursion would demand. It suffices to study the single problem of transitive closure and to provide an efficient implementation for it.
Security and inference in multilevel database and knowledge-base systems
Authors: Morgenstern Matthew
Published: November 2005

This paper addresses the threat to multilevel security that arises from logical inference and the semantics of the application. Such compromises of security are particularly challenging since they circumvent traditional security mechanisms and rely on a user's knowledge of the application. The problems of inference and security have heretofore been amorphous and difficult to circumscribe. We focus on these problems in the context of a multilevel database system and show their relevance to knowledge-based systems, sometimes referred to as expert systems. Here we establish a framework for studying these inference control problems, describe a representation for relevant semantics of the application, develop criteria for safety and security of a system to prevent these problems, and outline algorithms for enforcing these criteria.
Design and evaluation of parallel pipelined join algorithms
Authors: Richardson James P. , Lu Hongjun , Mikkilineni Krishna
Published: November 2005

The join operation is the most costly operation in relational database management systems. Distributed and parallel processing can effectively speed up the join operation. In this paper, we describe a number of highly parallel and pipelined multiprocessor join algorithms using sort-merge and hashing techniques. Among them, two algorithms are parallel and pipelined versions of traditional sort-merge join methods, two algorithms use both hashing and sort-merge techniques, and another two are variations of the hybrid hash join algorithms. The performance of those algorithms is evaluated analytically against a generic database machine architecture. The methodology used in the design and evaluation of these algorithms is also discussed.

The results of the analysis indicate that using a hashing technique to partition the source relations can dramatically reduce the elapsed time hash-based algorithms outperform sort-merge algorithms in almost all cases because of their high parallelism. Hash-based sort-merge and hybrid hash methods provide similar performance in most cases. With large source relations, the algorithms which replicate the smaller relation usually give better elapsed time. Sharing memory among processors also improves performance somewhat.
Storage reclamation in object oriented database systems
Authors: Butler Margaret H.
Published: November 2005

When providing data management for nontraditional data, database systems encounter storage reclamation problems similar to those encountered by virtual memory managers. The paging behavior of existing automatic storage reclamation schemes as applied to objects stored in a database management system is one indicator of the performance cost of various features of storage reclamation algorithms. The results of modeling the paging behavior suggest that Mark and Sweep causes many more input/output operations than Copy-Compact. A contributing factor to the expense of Mark and Sweep is that it does not recluster memory as does Copy-Compact. If memory is not reclustered, the average cost of accessing data can go up tremendously. Other algorithms that do not recluster memory also suffer performance problems, namely all reference counting schemes. The main advantage of a reference count scheme is that it does not force a running program to pause for a long period of time while reclamation takes place, it amortizes the cost of reclamation across all accesses. The reclustering of Copy-Compact and the cost amortization of Reference Count are combined to great advantage in Baker's algorithm. This algorithm proves to be the least prohibitive for operating on disk-based data.
Analysis of object oriented spatial access methods
Authors: Faloutsos Christos , Sellis Timos , Roussopoulos Nick
Published: November 2005

This paper provides an analysis of R-trees and a variation (R
+
-trees) that avoids overlapping rectangles in intermediate nodes of the tree. The main contributions of the paper are the following. We provide the first known analysis of R-trees. Although formulas are given for objects in one dimension (line segments), they can be generalized for objects in higher dimensions as well. We show how the transformation of objects to higher dimensions [HINR83] can be effectively used as a tool for the analysis of R- and R
+
- trees. Finally, we derive formulas for R
+
-trees and compare the two methods analytically. The results we obtained show that R
+
-trees require less than half the disk accesses required by a corresponding R-tree when searching files of real life sizes R
+
-trees are clearly superior in cases where there are few long segments and a lot of small ones.
A performance analysis of view materialization strategies
Authors: Hanson Eric N.
Published: November 2005

The conventional way to process commands for relational views is to use query modification to translate the commands into ones on the base relations. An alternative approach has been proposed recently, whereby materialized copies of views are kept, and incrementally updated immediately after each modification of the database. A related scheme exists, in which update of materialized views is deferred until just before data is retrieved from the view. A performance analysis is presented comparing the cost of query modification, immediate view maintenance, and deferred view maintenance. Three different models of the structure of views are given a simple selection and projection of one relation, the natural join of two relations, and an aggregate (e.g. the sum of values in a column) over a selection-projection view. The results show that the choice of the most efficient view maintenance method depends heavily on the structure of the database, the view definition, and the type of query and update activity present.
Extending the relational algebra to support transaction time
Authors: McKenzie Edwin , Snodgrass Richard
Published: November 2005

In this paper we discuss extensions to the conventional relational algebra to support transaction time. We show that these extensions are applicable to historical algebras that support valid time, yielding a temporal algebraic language. Since transaction time concerns the storage of information in the database, the notion of state is central. The extensions are formalized using denotational semantics. The additions preserve the useful properties of the conventional relational algebra.
A database design for musical information
Authors: Rubenstein W. Bradley
Published: November 2005

As part of our research into a general purpose data management system for musical information, a major focus has been the development of tools to support a data model for music. This paper first outlines the various types of information that fall under the purview of our proposed data manager. We consider extensions to the entity-relationship data model to implement the notion of
hierarchical ordering
, commonly found in musical data. We then present examples from our schema for representing musical notation in a database, taking advantage of these extensions.
Supporting office document architectures with constrained types
Authors: Croft W. B. , Stemple D. W.
Published: November 2005

Data models have been proposed as a means of defining the objects and operations in an office information system. Office documents, because of their highly variable structure and multimedia content, are a difficult class of objects to model. The modeling task is further complicated by document architecture standards used for interchange between systems. We present an approach to data modeling based on constrained type definitions that allows architecture standards to be defined and ensures that individual document types conform to those standards. The ADABTPL model, which is used to define the schema of document types and standards, is described.
On real-time transactions
Authors: Stankovic John A. , Zhao Wei
Published: November 2005

Next generation real-time systems will require greater
flexibility
and
predictability
than is commonly found in today's systems. These future systems include the space station, integrated vision/robotics/AI systems, collections of humans/robots coordinating to achieve common objectives (usually in hazardous environments such as undersea exploration or chemical plants), and various command and control applications. The complexity of such systems due to timing constraints, concurrency, and distribution is high. It is accepted that the synchronization, failure atomicity, and permanence properties of transactions aid in the development of distributed systems. However, little work has been done in exploiting transactions in a real-time context. We have been attempting to categorize real-time data into classes depending on their time, synchronization, atomicity, and permanence properties. Then, using the semantics of the data and the applications, we are developing special, tailored, real-time transactions that only supply the minimal properties necessary for that class. This reduces the system overhead in supporting access to various types of data. The eventual goal is to verify that timing requirements can be met.
Issues and approaches to design of real-time database systems
Authors: Singhal Mukesh
Published: November 2005

Real-time database systems support applications which have severe performance constraints such as fast response time and continued operation in the face of catastrophic failures. Real-time database systems are still in the state of infancy, and issues and alternatives in their design are not very well explored. In this paper, we discuss issues in the design of real-time database systems and discuss different alternatives for resolving these issues. We discuss the aspects in which requirements and design issues of real-time database systems differ from those of conventional database systems. We discuss two approaches to design real-time database systems, viz., main memory resident databases and design by trading a feature (like serializability).

We also discuss requirements in the design of real-time distributed database systems, and specifically discuss issues in the design of concurrency control and crash recovery. It is felt that long communication delays may be a factor in limiting the performance of real-time distributed database systems. We present a concurrency control algorithm for real-time distributed database systems whose performance is not limited by communication delays.
Kardamom—a dataflow database machine for real-time applications
Authors: von Bultzingsloewen Gunter , Dittrich Klaus R.
Published: November 2005

In real-time applications, database systems have to cope with requirements different from those prevailing in a commercial environment. High performance in the presence of complex queries and high reliability are the most crucial issues. To comply with these, it seems promising to adopt techniques which have been proposed in the context of database machines, such as parallel query processing, filtering, and data flow control. In this paper we present the concepts and the design of the data flow database machine KARDAMOM which is mainly geared towards real-time applications and is currently being developed at FZI Karlsruhe.
The HiPAC project: combining active databases and timing constraints
Authors: Dayal U. , Blaustein B. , Buchmann A. , Chakravarthy U. , Hsu M. , Ledin R. , McCarthy D. , Rosenthal A. , Sarin S. , Carey M. J. , Livny M. , Jauhari R.
Published: November 2005

The HiPAC (High Performance ACtive database system) project addresses two critical problems in time-constrained data management: the handling of timing constraints in databases, and the avoidance of wasteful polling through the use of situation-action rules that are an integral part of the database and are monitored by DBMS's condition monitor. A rich knowledge model provides the necessary primitives for definition of timing constraints, situation-action rules, and precipitating events. The execution model allows various coupling modes between transactions, situation evaluations and actions, and provides the framework for correct concurrent execution of transactions and triggered actions. Different approaches to scheduling of time-constrained tasks and transactions are explored and an architecture is being designed with special emphasis on the interaction of the time-constrained, active DBMS and the operating system. Performance models are developed to evaluate the various design alternatives.
An active functionality service for e-business applications
Authors: Cilia M. , Buchmann A. P.
Published: November 2005

Service based architectures are a powerful approach to meet the fast evolution of business rules and the corresponding software. An active functionality service that detects events and involves the appropriate business rules is a critical component of such a service-based middleware architecture. In this paper we present an active functionality service that is capable of detecting events in heterogeneous environments, it uses an integral ontology-based approach for the semantic interpretation of heterogeneous events and data, and provides notifications through a publish/subscribe notification mechanism. The power of this approach is illustrated with the help of an auction application and through the personalization of car and driver portals in Internet-enabled vehicles.
The role of B2B engines in B2B integration architectures
Authors: Bussler Christoph
Published: November 2005

Semantic B2B Integration architectures must enable enterprises to communicate standards-based B2B events like purchase orders with any potential trading partner. This requires not only back end application integration capabilities to integrate with e.g. enterprise resource planning (ERP) systems as the company-internal source and destination of B2B events, but also a capability to implement every necessary B2B protocol like Electronic Data Interchange (EDI), RosettaNet as well as more generic capabilities like web services (WS). This paper shows the placement and functionality of B2B engines in semantic B2B integration architectures that implement a generic framework for modeling and executing any B2B protocol. A detailed discussion shows how a B2B engine can provide the necessary abstractions to implement any standard-based B2B protocol or any trading partner specific specialization.
Book review column
Authors: Aberer Karl
Published: November 2005

In the last issue of SIGMOD RECORD we have introduced the new book review column. I am glad to say that in the meanwhile the call for book reviews has found very positive response and that we will be able to present three new reviews in this issue (and more are to come).
Too much middleware
Authors: Stonebraker Michael
Published: November 2005

The movement from client-server computing to multi-tier computing has created a potpourri of so-called middleware systems, including application servers, workflow products, EAI systems, ETL systems and federated data systems. In this paper we argue that the explosion in middleware has created a myriad of poorly integrated systems with overlapping functionality. The world would be well served by considerable consolidation, and we present some of the ways this might happen. Some of the points covered in this paper have been previously explored in [BERN96].
Report on the 18
th
British National Conference on Databases (BNCOD)
Authors: Goble Carole , Read Brian
Published: November 2005

The annual series of the British National Conference on Databases has been a forum for UK database practitioners and a focus for database research since 1981. In recent years, interest in this conference series has extended well beyond the UK.BNCOD 2001, the 18th conference in the series, was held at the CLRC Rutherford Appleton Laboratory (RAL) from 9th -11th July 2001. RAL hosts national large-scale facilities for advanced scientific research. The Information Technology Department collaborates with the Laboratory's data centres that manage terabytes of data in remote sensing, high-energy physics and astronomy.BNCOD 2001 included scientific papers, invited talks, a panel and a poster session. The BNCOD Programme Committee, chaired by Professor Carole Goble of Manchester University, selected for presentation at the meeting eleven papers, about one third of those papers submitted. Contributors were drawn from the Netherlands, Germany, Sweden, Canada and USA, as well as the UK. The audience of 60 attendees was chiefly drawn from the UK database community. The Proceedings are published by Springer-Verlag in the Lecture Notes in Computer Science series, and are available online at: http://link.springer.de/link/service/series/0558/tocs/t2097.htm.
Advances in databases and information systems
Authors: Caplinskas Albertas , Eder Johann , Vasilecas Olegas
Published: November 2005

The 5
th
East European Conference ADBIS'2001 was organized by the Vilnius Gediminas Technical University, Institute of Mathematics and Informatics (Lithuania), Lithuanian Computer Society in cooperation with Moscow ACM SIGMOD Chapter and Law University of Lithuania in Vilnius, Lithuania, September 25-28, 2001. The call for papers attracted 82 submissions from 30 countries. The international program committee, consisting of 47 researchers from 21 countries, selected 25 papers for long presentations and 19 research communications for regular sessions. Additionally, 9 professional communications and reports have been selected for industrial sessions. The authors of accepted papers come from 29 countries, indicating the truly international recognition of the ADBIS conference series. The conference had 127 registered participants from 23 countries and included invited lectures, tutorials, regular sessions, and industrial sessions. This report describes the goals of the conference and summarizes the issues discussed during the sessions.
Application and database design—putting it off
Authors: Shaw Christopher J.
Published: November 2005

There seems to be two major schools of thought about designing database application systems:

System design is mandatory, say the methodologers. How can you ever build a system unless you first determine in detail what it should do?

System design is impossible, say the prototypists. How can you ever build a system if you must first determine in detail what it should do?
Defining data types in a database language
Authors: Date C. J.
Published: November 2005

The question of defining data types in a database language is examined. In order to illustrate the general ideas and make them more concrete, the specific case of adding support for dates and times to the database language SQL is considered in detail.
MPEG-7 and multimedia database systems
Authors: Kosch Harald
Published: November 2005

The Multimedia Description Standard MPEG-7 is an International Standard since February 2002. It defines a huge set of description classes for multimedia content, for its creation and its communication. This article investigates what MPEG-7 means to Multimedia Database Systems (MMDBSs) and vice versa. We argue that MPEG-7 has to be considered complementary to, rather than competing with, data models employed in MMDBSs. Finally we show by an example scenario how these technologies can reasonably complement one another.
From ternary relationship to relational tables
Authors: Paré Rafael Camps
Published: November 2005

The transformation from n-ary relationships to a relational database schema has never been really fully analyzed. This paper presents one of the several ternary cases ignored by the ER-to-RM literature. The case shows that the following common belief is wrong: Given a set of FDs over a table resulting in a non-3NF situation, it is always possible to obtain a fully equivalent set of 3NF tables, without adding other restrictions than candidate keys and elementary inclusion dependencies.
SQL/XML is making good progress
Authors: Eisenberg Andrew , Melton Jim
Published: November 2005

Not very long ago, we discussed the creation of a new part of SQL, XML-Related Specifications (SQL/XML), in this column [1]. At the time, we referred to the work that had been done as "infrastructure". We are pleased to be able to say that significant progress has been made, and SQL/XML [2] is now going out for the first formal stage of processing, Final Committee Draft (FCD) ballot, in ISO/IEC JTC1.In our previous column, we described the mapping of SQL 〈identifier〉s to XML Names, SQL data types to XML Schema data types, and SQL values to XML values. There have been a few small corrections and enhancements in these areas, but for the most part the descriptions in our previous column are still accurate.Thc new work that we will discuss in this column comes in three parts. The first part provides a mapping from a single table, all tables in a schema, or all tables in a catalog to an XML document. The second of these parts includes the creation of an XML data type in SQL and adds functions that create values of this new type. These functions allow a user to produce XML from existing SQL data. Finally, the "infrastructure" work that we described in our previous article included the mapping of SQL's predefined data types to XML Schema data types. This mapping has been extended to include the mapping of domains, distinct types, row types, arrays, and multisets.The FCD ballot that we mentioned began in early April. This will allow the comments contained in the ballot responses to be discussed at the Editing Meeting in September or October of this year. We expect the Editing Meeting to recommend progression to Final Draft International Status (FDIS) ballot, which suggests that an International Standard will be published by the middle of 2003.
Combining fuzzy information
Authors: Fagin Ronald
Published: November 2005

Assume that each object in a database has
m
grades, or scores, one for each of
m
attributes. For example, an object can have a color grade, that tells how red it is, and a shape grade, that tells how round it is. For each attribute, there is a sorted list, which lists each object and its grade under that attribute, sorted by grade (highest grade first). Each object is assigned an overall grade, that is obtained by combining the attribute grades using a fixed monotone
aggregation function,
or
combining rule,
such as min or average. In this overview, we discuss and compare algorithms for determining the top
k
objects, that is,
k
objects with the highest overall grades.
The LyriC language
Authors: Brodsky Alexander , Kornatzky Yoram
Published: November 2005

We propose a novel data model and its language for querying object-oriented databases where objects may hold spatial, temporal or constraint data, conceptually represented by linear equality and inequality constraints. The proposed
LyriC
language is designed to provide a uniform and flexible framework for diverse application realms such as (1) constraint-based design in two-, three-, or higher-dimensional space, (2) large-scale optimization and analysis, based mostly on linear programming techniques, and (3) spatial and geographic databases.
LyriC
extends flat constraint query languages, especially those for linear constraint databases, to structurally complex objects. The extension is based on the object-oriented paradigm, where constraints are treated as first-class objects that are organized in classes. The query language is an extension of the language XSQL, and is built around the idea of extended path expressions. Path expressions in a query traverse nested structures in one sweep. Constraints are used in a query to filter stored constraints and to create new constraint objects.
OFL
Authors: Gardarin Georges , Machuca Fernando , Pucheral Philippe
Published: November 2005

We present a functional paradigm for querying efficiently abstract collections of complex objects. Abstract collections are used to model class extents, multivalued attributes as well as indexes or hashing tables. Our paradigm includes a functional language called OFL (Object Functional Language) and a supporting execution model based on graph traversals. OFL is able to support any complex object algebra with recursion as macros. It is an appropriate target language for OQL-like query compilers. The execution model provides various strategies including set-oriented and pipelined traversals. OFL has been implemented on top of an object manager. Measures of a typical query extracted from a geographical benchmark show the value of hybrid strategies integrating pipelined and set-oriented evaluations. They also show the potential of function result memorization, a typical optimization approach known as "Memoization"
2
in functional languages.
Nearest neighbor queries
Authors: Roussopoulos Nick , Kelley Stephen , Vincent Frédéric
Published: November 2005

A frequently encountered type of query in Geographic Information Systems is to find the k nearest neighbor objects to a given point in space. Processing such queries requires substantially different search algorithms than those for location or range queries. In this paper we present an efficient branch-and-bound R-tree traversal algorithm to find the nearest neighbor object to a point, and then generalize it to finding the k nearest neighbors. We also discuss metrics for an optimistic and a pessimistic search ordering strategy as well as for pruning. Finally, we present the results of several experiments obtained using the implementation of our algorithm and examine the behavior of the metrics and the scalability of the algorithm.
A general solution of the n-dimensional B-tree problem
Authors: Freeston Michael
Published: November 2005

We present a generic solution to a problem which lies at the heart of the unpredictable worst-case performance characteristics of a wide class of multi-dimensional index designs: those which employ a recursive partitioning of the data space. We then show how this solution can produce modified designs with fully predictable and controllable worst-case characteristics. In particular, we show how the recursive partitioning of an n-dimensional dataspace can be represented in such a way that the characteristics of the one-dimensional B-tree are preserved in n dimensions, as far as is topologically possible i.e. a representation guaranteeing logarithmic access and update time, while also guaranteeing a one-third minimum occupancy of both data and index nodes.
Topological relations in the world of minimum bounding rectangles
Authors: Papadias Dimitris , Sellis Timos , Theodoridis Yannis , Egenhofer Max J.
Published: November 2005

Recent developments in spatial relations have led to their use in numerous applications involving spatial databases. This paper is concerned with the retrieval of topological relations in Minimum Bounding Rectangle-based data structures. We study the topological information that Minimum Bounding Rectangles convey about the actual objects they enclose, using the concept of projections. Then we apply the results to R-trees and their variations, R
+
-trees and R*-trees in order to minimise disk accesses for queries involving topological relations. We also investigate queries that involve complex spatial conditions in the form of disjunctions and conjunctions and we discuss possible extensions.
OODB indexing by class-division
Authors: Ramaswamy Sridhar , Kanellakis Paris C.
Published: November 2005

Indexing a class hierarchy, in order to efficiently search or update the objects of a class according to a (range of) value(s) of an attribute, impacts OODB performance heavily. For this indexing problem, most systems use the class hierarchy index (CH) technique of [15] implemented using B
+
-trees. Other techniques, such as those of [14, 18,31], can lead to improved average-case performance but involve the implementation of new data-structures. As a special form of external dynamic two-dimensional range searching, this OODB indexing problem is solvable within reasonable worst-case bounds [12]. Based on this insight, we have developed a technique, called indexing by class-division (CD), which we believe can be used as a practical alternative to CH. We present an optimized implementation and experimental validation of CD's average-case performance. The main advantages of the CD technique are: (1) CD is an extension of CH that provides a significant speed-up over CH for a wide spectrum of range queries--this speed-up is at least linear in the number of classes queried for uniform data and larger otherwise; and (2) CD queries, updates and concurrent use are implementable using existing B
+
-tree technology. The basic idea of class-division involves a time-space tradeoff and CD requires some space and update overhead in comparison to CH. In practice, this overhead is a small factor (2 to 3) and, in worst-case, is bounded by the depth of the hierarchy and the logarithm of its size.