bluuebunny/crossref_metadata_2025 huggingface dataset:
Implementing crash recovery in QuickStore
Authors: White Seth J. , DeWitt David J.
Published: November 2005

Implementing crash recovery in an Object-Oriented Database System (OODBMS) raises several challenging issues for performance that are not present in traditional DBMSs. These performance concerns result both from significant architectural differences between OODBMSs and traditional database systems and differences in OODBMS's target applications. This paper compares the performance of several alternative approaches to implementing crash recovery in an OODBMS based on a client-server architecture. The four basic recovery techniques examined in the paper are termed page differencing, sub-page differencing, whole-page logging, and redo-at-server. All of the recovery techniques were implemented in the context of QuickStore, a memory-mapped store built using the EXODUS Storage Manager, and their performance is compared using the OO7 database benchmark. The results of the performance study show that the techniques based on differencing generally provide superior performance to whole-page logging.
Broadcast disks
Authors: Acharya Swarup , Alonso Rafael , Franklin Michael , Zdonik Stanley
Published: November 2005

This paper proposes the use of repetitive broadcast as a way of augmenting the memory hierarchy of clients in an asymmetric communication environment. We describe a new technique called "Broadcast Disks" for structuring the broadcast in a way that provides improved performance for non-uniformly accessed data. The Broadcast Disk superimposes multiple disks spinning at different speeds on a single broadcast channel--in effect creating an arbitrarily fine-grained memory hierarchy. In addition to proposing and defining the mechanism, a main result of this work is that exploiting the potential of the broadcast structure requires a re-evaluation of basic cache management policies. We examine several "pure" cache management policies and develop and measure implementable approximations to these policies. These results and others are presented in a set of simulation studies that substantiates the basic idea and develops some of the intuitions required to design a particular broadcast program.
Adapting materialized views after redefinitions
Authors: Gupta Ashish , Mumick Inderpal S. , Ross Kenneth A.
Published: November 2005

We consider a variant of the view maintenance problem: How does one keep a materialized view up-to-date when the view definition itself changes? Can one do better than recomputing the view from the base relations? Traditional view maintenance tries to maintain the materialized view in response to modifications to the base relations; we try to "adapt" the view in response to changes in the view definition.Such techniques are needed for applications where the user can change queries dynamically and see the changes in the results fast. Data archaeology, data visualization, and dynamic queries are examples of such applications.We consider all possible redefinitions of SQL SELECT-FROM-WHERE-GROUPBY, UNION, and EXCEPT views, and show how these views can be adapted using the old materialization for the cases where it is possible to do so. We identify extra information that can be kept with a materialization to facilitate redefinition. Multiple simultaneous changes to a view can be handled without necessarily materializing intermediate results. We identify guidelines for users and database administrators that can be used to facilitate efficient view adaptation.
Balancing histogram optimality and practicality for query result size estimation
Authors: Ioannidis Yannis E. , Poosala Viswanath
Published: November 2005

Many current database systems use histograms to approximate the frequency distribution of values in the attributes of relations and based on them estimate query result sizes and access plan costs. In choosing among the various histograms, one has to balance between two conflicting goals: optimality, so that generated estimates have the least error, and practicality, so that histograms can be constructed and maintained efficiently. In this paper, we present both theoretical and experimental results on several issues related to this trade-off. Our overall conclusion is that the most effective approach is to focus on the class of histograms that accurately maintain the frequencies of a few attribute values and assume the uniform distribution for the rest, and choose for each relation the histogram in that class that is optimal for a self-join query.
Semantic assumptions and query evaluation in temporal databases
Authors: Bettini Claudio , Wang X. Sean , Bertino Elisa , Jajodia Sushil
Published: November 2005

When querying a temporal database, a user often makes certain semantic assumptions on stored temporal data. This paper formalizes and studies two types of semantic assumptions: point-based and interval-based. The point-based assumptions include those assumptions that use interpolation methods, while the interval-based assumptions include those that involve different temporal types (time granularities). Each assumption is viewed as a way to derive certain implicit data from the explicit data stored in the database. The database system must use all explicit as well as (possibly infinite) implicit data to answer user queries. This paper introduces a new method to facilitate such query evaluations. A user query is translated into a system query such that the answer of this system query over the explicit data is the same as that of the user query over the explicit
and
the implicit data. The paper gives such a translation procedure and studies the properties (safety in particular) of user queries and system queries.
Incremental maintenance of views with duplicates
Authors: Griffin Timothy , Libkin Leonid
Published: November 2005

We study the problem of efficient maintenance of materialized views that may contain duplicates. This problem is particularly important when queries against such views involve aggregate functions, which need duplicates to produce correct results. Unlike most work on the view maintenance problem that is based on an algorithmic approach, our approach is algebraic and based on equational reasoning. This approach has a number of advantages: it is robust and easily extendible to new language constructs, it produces output that can be used by query optimizers, and it simplifies correctness proofs.We use a natural extension of the relational algebra operations to bags (multisets) as our basic language. We present an algorithm that propagates changes from base relations to materialized views. This algorithm is based on reasoning about equivalence of bag-valued expressions. We prove that it is correct and preserves a certain notion of minimality that ensures that no unnecessary tuples are computed. Although it is generally only a heuristic that computing changes to the view rather than recomputing the view from scratch is more efficient, we prove results saying that under normal circumstances one should expect, the change propagation algorithm to be significantly faster and more space efficient than complete recomputing of the view. We also show that our approach interacts nicely with aggregate functions, allowing their correct evaluation on views that change.
The SPIFFI scalable video-on-demand system
Authors: Freedman Craig S. , DeWitt David J.
Published: November 2005

This paper presents a simulation study of a video-on-demand system. We present video server algorithms for real-time disk scheduling, prefetching, and buffer pool management. The performance of these algorithms is compared against the performance of simpler algorithms such as elevator and round-robin disk scheduling and global LRU buffer pool management. Finally, we show that the SPIFFI video-on-demand system scales nearly linearly as the number of disks, videos, and terminals is increased.
Copy detection mechanisms for digital documents
Authors: Brin Sergey , Davis James , García-Molina Héctor
Published: November 2005

In a digital library system, documents are available in digital form and therefore are more easily copied and their copyrights are more easily violated. This is a very serious problem, as it discourages owners of valuable information from sharing it with authorized users. There are two main philosophies for addressing this problem: prevention and detection. The former actually makes unauthorized use of documents difficult or impossible while the latter makes it easier to discover such activity.In this paper we propose a system for registering documents and then detecting copies, either complete copies or partial copies. We describe algorithms for such detection, and metrics required for evaluating detection mechanisms (covering accuracy, efficiency, and security). We also describe a working prototype, called COPS, describe implementation issues, and present experimental results that suggest the proper settings for copy detection parameters.
High availability of commercial applications
Authors: Ivinskis Kestutis
Published: November 2005

The increased performance capabilities of UNIX server systems have led to their acceptance as the server of choice for medium-sized and large organizations. But performance is just one facet. Another facet is the end user perception of the availability of an information system.Traditional mainframe based IS shops have a long experience in supplying computing services to their commercial end users. The ultimate goal of the end user is to have no downtimes for his work at his PC or workstation terminal. Key issues related to system availability in client/server based information systems remain the same as in the mainframe based world, e.g. system responsiveness, maximum downtime per year and maximum number of system outages per year. But there are also new aspects, which have been introduced into the discussion.In a multi-tiered client/server based information system the OLTP workload is distributed on different servers. Hence one can ask: Why should a failure of one server automatically imply downtime for the whole system ? Can't most of the system continue to operate ? Redistribution of the workload on the remaining active servers can be used to attack this problem. Workload balancing can be applied for replicated system services. Other techniques have to be applied for non-replicated system services.This paper considers client/server based applications running in a local or wide area network of computers in a distributed system.
Integration approaches for CIM
Authors: Norrie Moira C.
Published: November 2005

In response to pressures to reduce product lead times, manufacturing companies are increasingly aware of the need for some form of integration along the whole product chain. Engineering tasks must be coordinated and data exchanged between the various specialised tools. An enterprise has two main tracks of information flow, namely technical and managerial, and product data management spans both tracks. On the technical track, applications are highly specialised supporting tasks such as product design (CAD) and the programming of numerically controlled machines (CAM). Generally, the various application systems on the technical track are referred to as CAx systems. CAx systems may not only differ in terms of functionality but also in terms of the amount and type of data managed, the run-time environment and performance characteristics.

For complete support of Computer Integrated Manufacturing (CIM), we must be able to integrate existing technical and administrative component application systems. These component systems vary in their data management support and many CAx systems store their data directly in files rather than in a database system. The issues are how to describe the dependencies between these component systems and ensure system-wide data consistency. A particularly difficult problem is that of how to interface existing application systems in such a way that their operation can be monitored and controlled and a global transaction scheme provided.

Integration must be achieved in a way that supports system evolution in terms of the introduction and replacement of application systems. This is particularly important given the trend towards the notions of the extended enterprise and virtual factories in which a particular product chain may span several enterprises. Further, emerging legal statutes (especially in relation to environmental factors) are resulting in changes to the requirements for product data management. Enterprise integration must be both flexible and dynamic. The best way of achieving this is to integrate component systems by mans of a control layer which coordinates tasks based on explicit inter-system dependencies amenable to both direct view and update.

Product Data Management systems (also known as Engineering Databases) have been developed for the integration of CAx systems by managing product data centrally. One problem with a centralised system controlling access to data is that its availability is critical to the operation of all component systems. In an effort to overcome this, systems are being developed which replicate the metadata and data required for coordination.

Alternatively, coordination approaches have been proposed which aim to maximise component subsystem autonomy and increase CIM system flexibility. These systems place less emphasis on data sharing and more emphasis on task coordination. The integration effort is minimised and only that information strictly essential to coordination is managed centrally.
Paradise
Authors: The Paradise Team CORPORATE
Published: November 2005

The goal of the Paradise project is to apply object-oriented and parallel database technology to the task of implementing a parallel GIS system capable of managing extremely large (multi-terabyte) data sets such as those that will be produced by the upcoming NASA EOSDIS project [Car92]. The project is focusing its resources on algorithms, processing, and storage techniques, and not on making new contributions to the data modeling, query language, or user interface domains.At the outset, we organized the Paradise project as two phases. The goal of first phase was to produce a client-server version of Paradise. The second phase of the project is to add support for tertiary storage and extend the software to run on clusters of workstations and "shared nothing" multiprocessors [Sto86]. Phase one of the project is now complete and has produced a usable, client-server version of the system whose performance and functionality is comparable to other integrated GIS systems [DKL
+
94].
The cougar approach to in-network query processing in sensor networks
Authors: Yao Yong , Gehrke Johannes
Published: November 2005

The widespread distribution and availability of small-scale sensors, actuators, and embedded processors is transforming the physical world into a computing platform. One such example is a sensor network consisting of a large number of sensor nodes that combine physical sensing capabilities such as temperature, light, or seismic sensors with networking and computation capabilities. Applications range from environmental control, warehouse inventory, and health care to military environments. Existing sensor networks assume that the sensors are preprogrammed and send data to a central frontend where the data is aggregated and stored for offline querying and analysis. This approach has two major drawbacks. First, the user cannot change the behavior of the system on the fly. Second, conservation of battery power is a major design factor, but a central system cannot make use of in-network programming, which trades costly communication for cheap local computation.In this paper, we introduce the Cougar approach to tasking sensor networks through declarative queries. Given a user query, a query optimizer generates an efficient query plan for in-network query processing, which can vastly reduce resource usage and thus extend the lifetime of a sensor network. In addition, since queries are asked in a declarative language, the user is shielded from the physical characteristics of the network. We give a short overview of sensor networks, propose a natural architecture for a data management system for sensor networks, and describe open research problems in this area.
Clustering validity checking methods
Authors: Halkidi Maria , Batistakis Yannis , Vazirgiannis Michalis
Published: November 2005

Clustering results validation is an important topic in the context of pattern recognition. We review approaches and systems in this context. In the first part of this paper we presented clustering validity checking approaches based on internal and external criteria. In the second, current part, we present a review of clustering validity approaches based on relative criteria. Also we discuss the results of an experimental study based on widely known validity indices. Finally the paper illustrates the issues that are under-addressed by the recent approaches and proposes the research directions in the field.
A study on the management of semantic transaction for efficient data retrieval
Authors: Huang Shi Ming , Kwan Irene , Li Chih He
Published: November 2005

Mobile computing technology is developing rapidly due to the advantages of information access through mobile devices and the need to retrieve information at remote locations. However, many obstacles within the discipline of wireless computing are yet to be resolved. One of the most significant of these issues is the speed of data retrieval, which directly affects the performance of mobile database applications. To remedy this problem, we propose here a revised methodology focusing on the management of mobile transactions. This paper investigates an extended semantic-based transaction management mechanism, and applies a model-based approach for developing a simulation model to evaluate the performance of our approach.
Interviewing during a tight job market
Authors: Ives Zachary G. , Luo Qiong
Published: November 2005

The following collection of articles aims to provide a sequel to Ugur Cetintemel's December 2001 interviewing advice article, with specific tips for times when the economy is in recession. The contributions are based on the personal experience of recent database graduates who were on the job market in the 2001-2002 season.
Wrapping web data into XML
Authors: Han Wei , Buttler David , Pu Calton
Published: November 2005

The vast majority of online information is part of the World Wide Web. In order to use this information for more than human browsing, web pages in HTML must be converted into a format meaningful to software programs. Wrappers have been a useful technique to convert HTML documents into semantically meaningful XML files. However, developing wrappers is slow and labor-intensive. Further, frequent changes on the HTML documents typically require frequent changes in the wrappers. This paper describes XWRAP Elite, a tool to automatically generate robust wrappers. XWRAP breaks down the conversion process into three steps. First, discover where the data is located in an HTML page and separating the data into individual objects. Second, decompose objects into data elements. Third, mark objects and elements in an output format. XWRAP Elite automates the first two steps and minimizes human involvement in marking output data. Our experience shows that XWRAP is able to create useful wrapper software for a wide variety of real world HTML documents.
XML document versioning
Authors: Chien Shu Yao , Tsotras Vassilis J. , Zaniolo Carlo
Published: November 2005

Managing multiple versions of XML documents represents an important problem, because of many applications ranging from traditional ones, such as software configuration control, to new ones, such as link permanence of web documents. Research on managing multiversion XML documents seeks to provide efficient and robust techniques for (i) storing and retrieving, (ii) exchanging, and (iii) querying such documents. In this paper, we first show that traditional version control methods, such as RCS, and SCCS, fall short from satisfying these three requirements, and discuss alternative solutions. First, we enhance RCS with a temporal page clustering policy to achieve objective (i). Then, we discuss a reference-based versioning scheme that achieves both objectives (i) and (ii) and is also effective at supporting simple queries. The topic of supporting complex queries, including temporal ones, meshes with the burgeoning interest of database researchers in XML as a database description language, and in XML query languages. In this context, the XML versioning problems are akin to those of transaction time management for databases of objects and semistructured information. Nevertheless, the need to preserve the natural ordering of XML documents frequently requires different techniques.
Data analysis and mining in the life sciences
Authors: Huyn Nam
Published: November 2005

Biotech companies routinely generate vast amounts of biological measurement data that must be analyzed rapidly and mined for diagnostic, prognostic, or drug evaluation purposes. While these data analysis tasks are critical to their success, they have not benefited from recent advances that emerged from database and KDD research. In this paper, we focus on two such tasks: on-line analysis of clinical study data, and mining broad datasets for biomarkers. We examine the new requirements that are not met by current data analysis technologies and we identify new database and KDD research to address these needs. We describe our experience implementing a
Scientific OLAP
system and a data mining platform for the support of biomarker discovery at SurroMed, and we outline some key technical challenges that must be overcome before data analysis and data mining technologies can be widely adopted in the biotech industry.
Mining system audit data
Authors: Lee Wenke , Fan Wei
Published: November 2005

Intrusion detection is an essential component of computer security mechanisms. It requires accurate and efficient analysis of a large amount of system and network audit data. It can thus be an application area of data mining. There are several characteristics of audit data: abundant raw data, rich system and network semantics, and ever "streaming". Accordingly, when developing data mining approaches, we need to focus on: feature extraction and construction, customization of (general) algorithms according to semantic information, and optimization of execution efficiency of the output models. In this paper, we describe a data mining framework for mining audit data for intrusion detection models. We discuss its advantages and limitations, and outline the open research problems.
Mining e-mail content for author identification forensics
Authors: de Vel O. , Anderson A. , Corney M. , Mohay G.
Published: November 2005

We describe an investigation into e-mail content mining for author identification, or authorship attribution, for the purpose of forensic investigation. We focus our discussion on the ability to discriminate between authors for the case of both aggregated e-mail topics as well as across different e-mail topics. An extended set of e-mail document features including structural characteristics and linguistic patterns were derived and, together with a Support Vector Machine learning algorithm, were used for mining the e-mail content. Experiments using a number of e-mail documents generated by different authors on a set of topics gave promising results for both aggregated and multi-topic author categorisation.
SQL multimedia and application packages (SQL/MM)
Authors: Melton Jim , Eisenberg Andrew
Published: November 2005

Regular readers of this column will have become familiar with database language SQL -- indeed, most readers are already familiar with it. We have also discussed the fact that the SQL standard is being published in multiple parts and have even discussed one of those parts in some detail[l].Another standard, based on SQL and its structured user-defined types[2], has been developed and published by the International Organization for Standardization (ISO). This standard, like SQL, is divided into multiple parts (more independent than the parts of SQL, in fact). Some parts of this other standard, known as SQL/MM, have already been published and are currently in revision, while others are still in preparation for initial publication.In this issue, we introduce SQL/MM and review each of its parts, necessarily at a high level.
Java support for data-intensive systems
Authors: Shah Mehul A. , Franklin Michael J. , Madden Samuel , Hellerstein Joseph M.
Published: November 2005

Database system designers have traditionally had trouble with the default services and interfaces provided by operating systems. In recent years, developers and enthusiasts have increasingly promoted Java as a serious platform for building data-intensive servers. Java provides a number of very helpful language features, as well as a full run-time environment reminiscent of a traditional operating system. This combination of features and community support raises the question of whether Java is better or worse at supporting data-intensive server software than a traditional operating system coupled with a weakly-typed language such as C or C++.In this paper, we summarize and discuss our experience building the Telegraph dataflow system in Java. We highlight some of the pleasures of coding with Java, and some of the pains of coding
around
Java in order to obtain good performance in a data-intensive server. For those issues that were painful, we present concrete suggestions for evolving Java's interfaces to better suit serious software systems development. We believe these experiences can provide insight for other designers to avoid pitfalls we encountered and to decide if Java is a suitable platform for their system.
The problem of identification
Authors: Schiel Ulrich
Published: November 2005

The existing models for database applications use a few fundamental concepts for the description of the world to be modeled. The most common of these concepts is the
entity
, also called object, element, concept, information, token, data or value. Entities are identifiable and distinguishable existing things of the real world. In general the concept of entity, is used only for static things whose existence does not depend directly from other entities, in contrast to the dynamic happenings called
events
and the existence of some dependency between two or more entities called
relationship
(or attribute or property) which can exist only in conjunction with the related entities. More complex combinations of entities, relationships and events we call
facts
. Therefore “
John has broken his leg yesterday and is in Santa Clara Hospital
” is a fact which combines the event of “
breaking a leg
” occurred with the entity “
leg of John
” at time-event “
yesterday
” and the relationship “
is in
” valid between “
John
” and “
Santa Clara Hospital
” now. We use the term object to refer to entities, relationships, events or facts, undistinguishably.
Dynamic multipaging in even less space
Authors: Merrett T. H. , Hamel Louis
Published: November 2005

We present an improvement to the directory structure of dynamic multipaging which reduces the overall storage requirement from The outstanding advantage of multipaging is that it provides multi-attribute access to a database file using directories of negligible size. The present improvement makes the directory size even more negligible and the addressing algorithm easier.
Replicated data management in distributed database systems
Authors: Son Sang Hyuk
Published: November 2005

Replication is the key factor in improving the availability of data in distributed systems. Replicated data is stored at multiple sites so that it can be accessed by the user even when some of the copies are not available due to site failures. A major restriction to using replication is that replicated copies must behave like a single copy, i.e., mutual consistency as well as internal consistency must be preserved. Synchronization techniques for replicated data in distributed database systems have been studied in order to increase the degree of concurrency and to reduce the possibility of transaction rollback. In this paper, we classify different synchronization methods by underlying mechanisms and the type of information they use in ordering the operations of transactions, and survey some of the replication management methods appeared in the literature.
Data modelling versus ontology engineering
Authors: Spyns Peter , Meersman Robert , Jarrar Mustafa
Published: November 2005

Ontologies in current computer science parlance are computer based resources that represent agreed domain semantics. Unlike data models, the fundamental asset of ontologies is their relative independence of particular applications, i.e. an ontology consists of relatively generic knowledge that can be reused by different kinds of applications/tasks. The first part of this paper concerns some aspects that help to understand the differences and similarities between ontologies and data models. In the second part we present an ontology engineering framework that supports and favours the genericity of an ontology. We introduce the DOGMA ontology engineering approach that separates "atomic" conceptual relations from "predicative" domain rules. A DOGMA ontology consists of an
ontology base
that holds sets of intuitive context-specific conceptual relations and a layer of "relatively generic"
ontological commitments
that hold the domain rules. This constitutes what we shall call
the double articulation
of a DOGMA ontology
1
.
Methodology for development and employment of ontology based knowledge management applications
Authors: Sure York , Staab Steffen , Studer Rudi
Published: November 2005

In this article we illustrate a methodology for introducing and maintaining ontology based knowledge management applications into enterprises with a focus on Knowledge Processes and Knowledge Meta Processes. While the former process circles around the usage of ontologies, the latter process guides their initial set up. We illustrate our methodology by an example from a case study on skills management.
Conceptual model of web service reputation
Authors: Maximilien E. Michael , Singh Munindar P.
Published: November 2005

Current Web services standards enable publishing service descriptions and finding services on a match based on criteria such as method signatures or service category. However, current approaches provide no basis for selecting a good service or for comparing ratings of services. We describe a conceptual model for reputation using which reputation information can be organized and shared and service selection can be facilitated and automated.
The ρ operator
Authors: Anyanwu Kemafor , Sheth Amit
Published: November 2005

In this paper, we introduce an approach that supports querying for Semantic Associations on the Semantic Web. Semantic Associations capture complex relationships between entities involving sequences of predicates, and sets of predicate sequences that interact in complex ways. Detecting such associations is at the heart of many research and analytical activities that are crucial to applications in national security and business intelligence. This in combination with the improving ability to identify entities in documents as part of automatic semantic annotation, gives a very powerful capability for semantic analysis of large amounts of heterogeneous content.The approach for supporting Semantic Associations discussed in this paper has four main facets. First, it generalizes these associations into three main classes based on their structural properties, allowing us to reason about them in a domain-independent manner. The second is the provision of an operator ρ for expressing queries about such associations. Third, it uses a graph data model for knowledge representation, allowing the semantic associations search techniques to be built upon the graph algorithms for paths, while integrating knowledge from the schema into the search process. The fourth facet is the use of a notion of context, which allows for restricting the search space and for context-driven ranking of results. Just as a Web search engine looks for relevant documents in the current Web, ρ can be seen as discovering and ranking complex relationships in the Semantic Web.In this paper, we demonstrate the need for supporting such complex semantic relationships. We also give a formal basis to the notion of Semantic Associations and give a brief discussion on our overall approach for discovering and ranking them.
A framework for semantic gossiping
Authors: Aberer Karl , Cudré-Mauroux Philippe , Hauswirth Manfred
Published: November 2005

Today the problem of semantic interoperability in information search on the Internet is solved mostly by means of centralization, both at a system and at a logical level. This approach has been successful to a certain extent. Peer-to-peer systems as a new brand of system architectures indicate that the principle of decentralization might offer new solutions to many problems that scale well to very large numbers of users.In this paper we outline how the peer-to-peer system architectures can be applied to tackle the problem of semantic interoperability in the large, driven in a bottom-up manner by the participating peers. Such a system can readily be used to study semantic interoperability as a global scale phenomenon taking place in a social network of information sharing peers.
Querying multiple bioinformatics information sources
Authors: Buttler David , Coleman Matthew , Critchlow Terence , Fileto Renato , Han Wei , Pu Calton , Rocco Daniel , Xiong Li
Published: November 2005

Advances in Semantic Web and Ontologies have pushed the role of semantics to a new frontier: Semantic Composition of Web Services. A good example of such compositions is the querying of multiple bioinformatics data sources. Supporting effective querying over a large collection of bioinformatics data sources presents a number of unique challenges. First, queries over bioinformatics data sources are often complex associative queries over multiple Web documents. Most associations are defined by string matching of textual fragments in two documents. Second, most of the queries required by Genomics researchers involve complex data extraction, and sophisticated workflows that implement the complex associative access. Third but not the least, complex Genomics-specific queries are often reused many times by Genomics researchers, either directly or through some refinements, and are considered as a part of the research results by Genomics researchers. In this short article we present a list of challenging issues in supporting effective querying over bioinformatics data sources and illustrate them through a selection of representative search scenarios provided by biologists. We end the article with a discussion on how the state-of-art research and technological development in Semantic Web, Ontology, Internet Data Management, and Internet Computing Systems can help addressing these issues.
Performing joins without decompression in a compressed database system
Authors: O'Connell S. J. , Winterbottom N.
Published: November 2005

There has been much work on compressing database indexes, but less on compressing the data itself. We examine the performance gains to be made by compression outside the index. A novel compression algorithm is reported, which enables the processing of queries without decompressing data needed to perform join operations in a database built on a triple store. The results of modelling the performance of the database with and without compression are given and compared with other recent work in this area. It is found that for some applications, gains in performance of over 50% are achievable, and in OLTP-like situations, there are also gains to be made.
XPath processing in a nutshell
Authors: Gottlob Georg , Koch Christoph , Pichler Reinhard
Published: November 2005

We provide a concise yet complete formal definition of the semantics of XPath 1 and summarize e cient algorithms for processing queries in this language. Our presentation is intended both for the reader who is looking for a short but comprehensive formal account of XPath as well as the software developer in need of material that facilitates the rapid implementation of XPath engines.
A multi-paradigm querying approach for a generic multimedia database management system
Authors: Wen Ji-Rong , Li Qing , Ma Wei-Ying , Zhang Hong-Jiang
Published: November 2005

To truly meet the requirements of multimedia database (MMDB) management, an integrated framework for modeling, managing and retrieving various kinds of media data in a uniform way is necessary. MediaLand is an experimental MMDB platform being developed at
Microsoft Research Asia
for users with different levels of experiences and expertise to manage and search multimedia repositories easily, efficiently, and cooperatively. Key features of MediaLand include a uniform data model for describing all kinds of media objects and their relationships, and a 4-tier architecture based on this data model. In this paper, a multi-paradigm querying approach of MediaLand is presented, in which multimedia queries are processed based on a seamless integration of various existing search approaches. In doing so, MediaLand also offers the feature of "media independence" which is analogous to the notion of "data independence" from the classic ANSI SPARC standard. By incorporating a rich set of facilities and techniques, MediaLand lays down a good foundation for addressing further research issues, such as multimedia query rewriting, optimization, and presentation.
Analysis of existing databases at the logical level
Authors: De Marchi Fabien , Lopes Stéphane , Petit Jean-Marc , Toumani Farouk
Published: November 2005

Whereas physical database tuning has received a lot of attention over the last decade, logical database tuning seems to be under-studied. We have developed a project called
DBA Companion
devoted to the understanding of logical database constraints from which logical database tuning can be achieved.In this setting, two main data mining issues need to be addressed: the first one is the design of efficient algorithms for functional dependencies and inclusion dependencies inference and the second one is about the interestingness of the discovered knowledge. In this paper, we point out some relationships between database analysis and data mining. In this setting, we sketch the underlying themes of our approach. Some database applications that could benefit from our project are also described, including logical database tuning.
Report on the first international conference on ontologies, databases and applications of semantics (ODBASE)
Authors: Aberer Karl
Published: November 2005

ODBASE is a new conference series focussing on semantics, databases and the Web. In this article we provide a short overview of the history and the program of the first ODBASE event.
Atomic garbage collection: managing a stable heap
Authors: Kolodner Elliot , Liskov Barbara , Weihl William
Published: November 2005

Modern database systems use transactions to achieve a high degree of fault-tolerance. Many modern programming languages and systems provide garbage collected heap storage, which frees the programmer from the job of explicitly deallocating storage. In this paper we describe integrated garbage collection and recovery algorithms for managing a
stable heap
in which accessible objects survive both system crashes and media failures.

A garbage collector typically both moves and modifies objects which can lead to problems when the heap is stable because a system crash after the start of collection but before enough of the reorganized heap reaches the disk can leave the disk in an inconsistent state. Furthermore, collection has to be coordinated with the recovery system. We present a collection algorithm and recovery system that solves these problems.
On distributed processibility of datalog queries by decomposing databases
Authors: Dong Guozhu
Published: November 2005

We consider distributed or parallel processing of datalog queries. We address this issue by decomposing databases into a number of subdatabases such that the computation of a program on a database can be achieved by
unioning its independent evaluations
on the subdatabases. More specifically, we identify two kinds of distributed-processible programs according to the properties of database decomposition. (i) A program is
disjoint distributive
if it is distributed processible over a decomposition consisting of subdatabases with disjoint domains. A characterization of such programs is given in terms of an easily decidable syntactic property called
connectivity
. (ii) A program is
bounded distributive
if it is distributed processible over a decomposition consisting of subdatabases with a fixed size. Three interesting characterizations of such a program are presented, the first by bounded recursion, the second by equivalence to a 1-bounded-recursive program, and the third by constant parallel complexity
ODE (Object Database and Environment): the language and the data model
Authors: Agrawal R. , Gehani N. H.
Published: November 2005

ODE is a database system and environment based on the object paradigm. It offers one integrated data model for both database and general purpose manipulation. The database is defined, queried and manipulated in the database programming language O++ which is based on C++. O++ borrows and extends the object definition facility of C++, called the class. Classes support data encapsulation and multiple inheritance. We provide facilities for creating persistent and versioned objects, defining sets, and iterating over sets and clusters of persistent objects. We also provide facilities to associate constraints and triggers with objects. This paper presents the linguistic facilities provided in O++ and the data model it supports.
Database programming in Machiavelli—a polymorphic language with static type inference
Authors: Ohori Atsushi , Buneman Peter , Breazu-Tannen Val
Published: November 2005

Machiavelli is a polymorphically typed programming language in the spirit of ML, but supports an extended method of type inferencing that makes its polymorphism more general and appropriate for database applications. In particular, a function that selects a field ƒ of a records is polymorphic in the sense that it can be applied to any record which contains a field ƒ with the appropriate type. When combined with a set data type and database operations including join and projection, this provides a natural medium for relational database programming. Moreover, by implementing database objects as reference types and generating the appropriate views — sets of structures with “identity” — we can achieve a degree of static type checking for object-oriented databases.
CLASSIC: a structural data model for objects
Authors: Borgida Alexander , Brachman Ronald J. , McGuinness Deborah L. , Resnick Lori Alperin
Published: November 2005

CLASSIC is a data model that encourages the description of objects not only in terms of their relations to other known objects, but in terms of a level of intensional structure as well. The CLASSIC language of
structured descriptions
permits i) partial descriptions of individuals, under an 'open world' assumption, ii) answers to queries either as extensional lists of values or as descriptions that necessarily hold of all possible answers, and iii) an easily extensible schema, which can be accessed uniformly with the data. One of the strengths of the approach is that the same language plays multiple roles in the processes of defining and populating the DB, as well as querying and answering.

CLASSIC (for which we have a prototype main-memory implementation) can actively discover new information about objects from several sources: it can recognize new classes under which an object falls based on a description of the object, it can propagate some deductive consequences of DB updates, it has simple procedural recognizers, and it supports a limited form of forward-chaining rules to derive new conclusions about known objects.

The kind of language of descriptions and queries presented here provides a new arena for the search for languages that are more expressive than conventional DBMS languages, but for which query processing is still tractable. This space of languages differs from the subsets of predicate calculus hitherto explored by deductive databases.
Processing aggregate relational queries with hard time constraints
Authors: Hou Wen-Chi , Ozsoyoglu Gultekin , Taneja Baldeo K.
Published: November 2005

We consider those database environments in which queries have strict timing constraints, and develop a time-constrained query evaluation methodology. For aggregate relational algebra queries, we describe a time constrained query evaluation algorithm. The algorithm, which is implemented in our prototype DBMS, iteratively samples from input relations, and evaluates the associated estimators developed in our previous work, until a stopping criterion (e.g., a time quota or a desired error range) is satisfied.

To determine sample sizes at each stage of the iteration (so that the time quota will not be overspent) we need to have (a) accurate sample selectivity estimations of the RA operators in the query, (b) precise time cost formulas, and (c) good time-control strategies. To estimate the sample selectivities of RA operators, we use a runtime sample selectivity estimation and improvement approach which is flexible. For query time estimations, we use time-cost formulas which are adaptive and precise. To use the time quota efficiently, we propose statistical and heuristic time-control strategies to control the risk of overspending the time quota. Preliminary evaluation of the implemented prototype is also presented.
Extending a relational database with deferred referential integrity checking and intelligent joins
Authors: Cammarata Stephanie , Ramachandra Prasadram , Shane Darrell
Published: November 2005

Interactive use of relational database management systems (DBMS) requires a user to be knowledgeable about the semantics of the application represented in the database. In many cases, however, users are not trained in the application field and are not DBMS experts. Two categories of functionality are problematic for such users: (1) updating a database without violating integrity constraints imposed by the domain and (2) using join operations to retrieve data from more than one relation. We have been conducting research to help an uninformed or casual user interact with a relational DBMS.

This paper describes two capabilities to aid an interactive database user who is neither an application specialist nor a DBMS expert. We have developed deferred Referential Integrity Checking (RIC) and Intelligent Join (IJ) which extend the operations of a relational DBMS. These facilities are made possible by explicit representation of database semantics combined with a relational schema. Deferred RIC is a static validation procedure that checks uniqueness of tuples, non-null keys, uniqueness of keys, and inclusion dependencies. IJ allows a user to identify only the “target” data which is to be retrieved without the need to additionally specify “join clauses”. In this paper we present the motivation for these facilities, describe the features of each, and present examples of their use.