bluuebunny/crossref_metadata_2025 huggingface dataset:
The handwritten trie
Authors: Aref Walid , Barbará Daniel , Vallabhaneni Padmavathi
Published: November 2005

The emergence of the pen as the main interface device for personal digital assistants and pen-computers has made handwritten text, and more generally
ink,
a first-class object. As for any other type of data, the need of retrieval is a prevailing one. Retrieval of handwritten text is more difficult than that of conventional data since it is necessary to identify a handwritten word given slightly different variations in its shape. The current way of addressing this is by using handwriting recognition, which is prone to errors and limits the expressiveness of ink. Alternatively, one can retrieve from the database handwritten words that are similar to a query handwritten word using techniques borrowed from pattern and speech recognition. In particular, Hidden Markov Models (HMM) can be used as representatives of the handwritten words in the database. However, using HMM techniques to match the input against every item in the database (sequential searching) is unacceptably slow and does not scale up for large ink databases. In this paper, an indexing technique based on HMMs is proposed. The new index is a variation of the trie data structure that uses HMMs and a new search algorithm to provide approximate matching. Each node in the tree contains handwritten letters, where each letter is represented by an HMM. Branching in the trie is based on the ranking of matches given by the HMMs. The new search algorithm is parametrized so that it provides means for controlling the matching quality of the search process via a time-based budget. The index dramatically improves the search time in a database of handwritten words. Due to the variety of platforms for which this work is aimed, ranging from personal digital assistants to desktop computers, we implemented both main-memory and disk-based systems. The implementations are reported in this paper, along with performance results that show the practicality of the technique under a variety of conditions.
FastMap
Authors: Faloutsos Christos , Lin King-Ip
Published: November 2005

A very promising idea for fast searching in traditional and multimedia databases is to map objects into points in
k
-d space, using
k
feature-extraction functions, provided by a domain expert [25]. Thus, we can subsequently use highly fine-tuned spatial access methods (SAMs), to answer several types of queries, including the 'Query By Example' type (which translates to a range query); the 'all pairs' query (which translates to a spatial join [8]); the nearest-neighbor or best-match query, etc.However, designing feature extraction functions can be hard. It is relatively easier for a domain expert to assess the similarity/distance of two objects. Given only the distance information though, it is not obvious how to map objects into points.This is exactly the topic of this paper. We describe a fast algorithm to map objects into points in some
k
-dimensional space (
k
is user-defined), such that the dis-similarities are preserved. There are two benefits from this mapping: (a) efficient retrieval, in conjunction with a SAM, as discussed before and (b) visualization and data-mining: the objects can now be plotted as points in 2-d or 3-d space, revealing potential clusters, correlations among attributes and other regularities that data-mining is looking for.We introduce an older method from pattern recognition, namely,
Multi-Dimensional Scaling
(MDS) [51]; although unsuitable for indexing, we use it as yardstick for our method. Then, we propose a much faster algorithm to solve the problem in hand, while in addition it allows for indexing. Experiments on real and synthetic data indeed show that the proposed algorithm is significantly faster than MDS, (being linear, as opposed to quadratic, on the database size
N
), while it manages to preserve distances and the overall structure of the data-set.
Applying update streams in a soft real-time database system
Authors: Adelberg B. , Garcia-Molina H. , Kao B.
Published: November 2005

Many papers have examined how to efficiently export a materialized view but to our knowledge none have studied how to efficiently import one. To import a view, i.e., to install a stream of updates, a real-time database system must process new updates in a timely fashion to keep the database "fresh," but at the same time must process transactions and ensure they meet their time constraints. In this paper, we discuss the various properties of updates and views (including staleness) that affect this tradeoff. We also examine, through simulation, four algorithms for scheduling transactions
and
installing updates in a soft real-time database.
Temporal conditions and integrity constraints in active database systems
Authors: Sistla A. Prasad , Wolfson Ouri
Published: November 2005

In this paper, we present a unified formalism, based on Past Temporal Logic, for specifying conditions and events in the rules for active database system. This language permits specification of many time varying properties of database systems. It also permits specification of temporal aggregates. We present an efficient incremental algorithm for detecting conditions specified in this language. The given algorithm, for a subclass of the logic, was implemented on top of Sybase.
Dynamic resource brokering for multi-user query execution
Authors: Davison Diane L. , Graefe Goetz
Published: November 2005

We propose a new framework for resource allocation based on concepts from microeconomics. Specifically, we address the difficult problem of managing resources in a multiple-query environment composed of queries with widely varying resource requirements. The central element of the framework is a resource broker that realizes a profit by "selling" resources to competing operators using a performance-based "currency." The guiding principle for brokering resources is profit maximization. In other words, since the currency is derived from the performance objective, the broker can achieve the best performance by making the scheduling and resource allocation decisions that maximize profit. Moreover, the broker employs dynamic techniques and adapts by changing previous allocation decisions while queries are executing. In a first validation study of the framework, we developed a prototype broker that manages memory and disk bandwidth for a multi-user query workload. The performance objective for the prototype broker is to minimize slowdown with the constraint of fairness. Slowdown measures how much higher the response time is in a multi-user environment than a single-user environment, and fairness measures how even is the degradation in response time among all queries as the system load increases, Our simulation results show the viability of the broker framework and the effectiveness of our query admission and resource allocation policies for multi-user workloads.
Reducing multidatabase query response time by tree balancing
Authors: Du Weimin , Shan Ming-Chien , Dayal Umeshwar
Published: November 2005

Execution of multidatabase queries differs from that of traditional queries in that sort merge and hash joins are more often favored, as nested loop join requires repeated accesses to external data sources. As a consequence, left deep join trees obtained by traditional (e.g., System-R style) optimizers for multidatabase queries are often suboptimal, with respect to response time, due to the long delay for a sort merge (or hash) join node to produce its last result after the subordinate join node did. In this paper, we present an optimization strategy that first produces an optimal left deep join tree and then reduces the response time using simple tree transformations. This strategy has the advantages of guaranteed minimum total resource usage, improved response time, and low optimization overhead. We describe a class of basic transformations that is the cornerstone of our approach. Then we present algorithms that effectively apply basic transformations to balance a left deep join tree, and discuss how the technique can be incorporated into existing query optimizers.
View maintenance in a warehousing environment
Authors: Zhuge Yue , García-Molina Héctor , Hammer Joachim , Widom Jennifer
Published: November 2005

A warehouse is a repository of integrated information drawn from remote data sources. Since a warehouse effectively implements materialized views, we must maintain the views as the data sources are updated. This view maintenance problem differs from the traditional one in that the view definition and the base data are now decoupled. We show that this decoupling can result in anomalies if traditional algorithms are applied. We introduce a new algorithm, ECA (for "Eager Compensating Algorithm"), that eliminates the anomalies. ECA is based on previous incremental view maintenance algorithms, but extra "compensating" queries are used to eliminate anomalies. We also introduce two streamlined versions of ECA for special cases of views and updates, and we present an initial performance study that compares ECA to a view recomputation algorithm in terms of messages transmitted, data transferred, and I/O costs.
Efficient maintenance of materialized mediated views
Authors: Lu James J. , Moerkotte Guido , Schue Joachim , Subrahmanian V. S.
Published: November 2005

Integrating data and knowledge from multiple heterogeneous sources -- like databases, knowledge bases or specific software packages -- is often required for answering certain queries. Recently, a powerful framework for defining mediated views spanning multiple knowledge bases by a set of constrained rules was proposed [24, 4, 16]. We investigate the materialization of these views by unfolding the view definition and the efficient maintenance of the resulting materialized mediated view in case of updates. Thereby, we consider two kinds of updates: updates to the view and updates to the underlying sources. For each of these two cases several efficient algorithms maintaining materialized mediated views are given. We improve on previous algorithms like the DRed algorithm [12] and introduce a new fixpoint operator

W
P

which -- opposed to the standard fixpoint operator

T
P

[9] -- allows us to correctly capture the update's semantics without any recomputation of the materialized view.
An online video placement policy based on bandwidth to space ratio (BSR)
Authors: Dan Asit , Sitaram Dinkar
Published: November 2005

In a video-on-demand server, resource reservation is required to guarantee continuous delivery. Hence any given storage device (or a striping group treated as a single logical device) can serve only up to a fixed number of client access streams. Each storage device is also limited by the number of video files it can store. For the reasons of availability, incremental growth, and heterogeneity, there may be multiple storage devices in a video server environment. Hence, one or more copies of a particular video may be placed on different storage devices. Since the access rates to different videos are not uniform, there may be load imbalance among the devices. In this paper, we propose a dynamic placement policy (called the Bandwidth to Space Ratio (BSR) Policy) that creates and/or deletes replica of a video, and mixes hot and cold videos so as to make the best use of bandwidth and space of a storage device. The proposed policy is evaluated using a simulation study.
Join queries with external text sources
Authors: Chaudhuri Surajit , Dayal Umeshwar , Yan Tak W.
Published: November 2005

Text is a pervasive information type, and many applications require querying over text sources in addition to structured data. This paper studies the problem of query processing in a system that loosely integrates an extensible database system and a text retrieval system. We focus on a class of conjunctive queries that include joins between text and structured data, in addition to selections over these two types of data. We adapt techniques from distributed query processing and introduce a novel class of join methods based on
probing
that is especially useful for joins with text systems, and we present a cost model for the various alternative query processing methods. Experimental results confirm the utility of these methods. The space of query plans is extended due to the additional techniques, and we describe an optimization algorithm for searching this extended space. The techniques we describe in this paper are applicable to other types of external data managers loosely integrated with a database system.
Leveraging the information asset
Authors: Perna Janet
Published: November 2005

Data is a corporate asset, and being able to derive more information from data can provide database users with a competitive advantage. For example, catching on to trends quickly can reduce unwanted store inventory and lower capital outlay for the same profit. If you have store sales data by product analyzed on a daily basis, that can make a 2-3% difference in margin -- and in a business where margins might be 4%, this is a significant competitive edge. This paper will cover what technology is needed by customers to leverage their information assets. Real-time access to production point of sale information, database mining for analysis to detect trends immediately, high performance, and multi-vendor database connectivity, cooperation among heterogeneous clients and servers are among the customer needs we are seeing in the marketplace.
Enterprise Objects Framework
Authors: Kleissner Charly
Published: November 2005

Today's information system executives desperately need to improve programmer productivity and reduce software maintenance costs. They are demanding flexibility in frameworks and architectures in order to meet unforeseen changes (see
[Yankee 94]
). Adaptability is a major requirement of most company's information systems efforts. Management of change is one of the key computing concepts of the 1990s.Object-oriented tools and development frameworks are starting to deliver the benefits of increased productivity and flexibility. These next-generation products now need to be combined with relational databases to leverage investments and facilitate access to business data.
Object-Relational Enablers
automate the process of storing complex objects in a relational database management system (see
[Aberdeen 94]
).The
Enterprise Objects Framework
product is a second generation product bringing the benefits of object-oriented programming to relational database application development. Enterprise Objects Framework enables developers to construct reusable business objects that combine business logic with persistent storage in industry-standard relational databases. Enterprise objects are first class citizens in the NEXTSTEP and OpenStep developer and user environments. They can be geographically distributed throughout heterogeneous servers within an enterprise using the
Portable Distributed Objects
product (see
[NeXT-DO 94]
).In this extended abstract we first describe the enterprise object distribution model and then give a brief synopsis of how relational data is mapped into objects. We then present an outline of the system architecture, explain how objects are mapped to multiple tables, and summarize the transaction semantics as well as the application development life-cycle. We conclude with an outlook on future development.
An overview of DB2 parallel edition
Authors: Baru Chaitanya , Fecteau Gilles
Published: November 2005

In this paper, we describe the architecture and features of DB2 Parallel Edition (PE). DB2 PE belongs to the IBM family of open DB2 client/server database products including DB2/6000, DB2/2, DB2 for HP-UX, and DB2 for the Solaris Operating Environment. DB2 PE employs a
shared nothing
architecture in which the database system consists of a set of independent
logical database nodes.
Each logical node represents a collection of system resources including, processes, main memory, disk storage, and communications, managed by an independent database manager. The logical nodes use message passing to exchange data with each other. Tables are partitioned across nodes using a hash partitioning strategy. The cost-based parallel query optimizer takes table partitioning information into account when generating parallel plans for execution by the runtime system. A DB2 PE system can be configured to contain one or more logical nodes per physical processor. For example, the system can be configured to implement one node per processor in a shared-nothing, MPP system or multiple nodes in a symmetric multiprocessor (SMP) system. This paper provides an overview of the storage model, query optimization, runtime system, utilities, and performance of DB2 Parallel Edition.
Informix online XPS
Authors: Gerber Bob
Published: November 2005

Parallel database systems have delivered on the promise of providing excellent, linear performance speedups for both decision support and transaction processing workloads across a variety of parallel system platforms. The challenge is now to extend those results across the entire open systems spectrum of loosely coupled environments while realizing the inherent high availability of such systems. The Informix eXtended Parallel Server (XPS) will accomplish that goal.XPS is the third and latest in the series of Online database servers that are based upon the Informix Dynamic Scalable Architecture (DSA). Earlier Online DSA servers have proven the effectiveness of the SMP-based high performance parallel data query (PDQ) technology that is the foundation of XPS: multi-threaded process groups, table partitioning, pipelined hash-partitioned operators, light access methods, and parallel resource management. XPS extends that PDQ technology across the continuum from small clusters of large SMP systems to massively parallel clusters of SMP or uniprocessor systems.
Order-of-magnitude advantage on TPC-C through massive parallelism
Authors: Levine Charles
Published: November 2005

TPC Benchmark™ C (TPC-C) is the modern standard for measuring OLTP performance. Running TPC-C, Tandem demonstrated a massively parallel configuration of 112 CPUs which achieved ten times higher performance than any other system previously measured (and today is still better by a factor of five). This result qualifies as the largest industry-standard benchmark ever run.This paper briefly describes how the benchmark was configured and the results which were obtained.
Workflow automation
Authors: Sheth Amit
Published: November 2005

With increasing global exposure, today's enterprises must react quickly to changes, rapidly develop new services and products, and at the same time improve productivity and quality and reduce cost.
Business process re-engineering
and
workflow automation
to coordinate activities throughout the enterprise are recognized as important emerging technologies to support these requirements. Rosy estimates of a multi-billion dollar marketplace for workflow software has resulted in significant commercial activities in the area, with nearly hundred products now claiming to support workflow automation. While many help to automate document- and image-driven office applications, therefore helping to improve the productivity of small groups, most current products fail to support:• mission critical and enterprise-wide applications with requirements such as failure handling and recovery, and• interoperability with existing heterogeneous information systems.In this tutorial, we will discuss requirements for applications involving workflow automation, present an overview of the current state-of-the-art in products, and present some of the research efforts that are attempting to respond to unmet challenges.
Tutorial on storage technology
Authors: Gibson Garth A.
Published: November 2005

In stark contrast to the 25% per year increase in areal density delivered by the magnetic disk industry during the 1970s and 1980s, yearly increases today are 60%, on par with DRAM density increases. Moreover, the storage industry is also delivering substantially higher data rates, smart disk-embedded readahead and writebehind, and a new generation of high-speed serial interconnects. This industry has also embraced Redundant Arrays of Inexpensive (or Independent) Disks (RAID) technology - 1997's RAID market is expected to be 13 billion dollars. With this rapidly evolving market and technology base, parallel storage systems must evolve beyond RAID levels 1 through 5. This talk is intended for researchers and practitioners interested in current trends in storage systems. It will highlight storage technology trends, RAID technology trends, and trends toward RAID-style support for network-based parallel storage systems.
InfoHarness
Authors: Shklar Leon , Sheth Amit , Kashyap Vipul , Thatte Satish
Published: November 2005

Enormous amounts of heterogeneous information have been accumulated within corporations, government organizations and universities. It is becoming increasingly easier to create new information, but the knowledge about the existence, location, and means of retrieval of information, have become so confusing as to give rise to the phenomenon of
write-only
databases.
VisDB
Authors: Keim Daniel A. , Kriegel Hans-Peter
Published: November 2005

The
VisDB
system developed at the University of Munich is a sophisticated tool for visualizing and analyzing large databases. The key idea of the
VisDB
system is to support the exploration of large databases by using the phenomenal abilities of the human vision system which is able to analyze visualizations of mid-size to large amounts of data very efficiently. The goal of the
VisDB
system is to provide visualizations of large portions of the database, allowing properties of the data and structure in the data to become perceptually apparent.
Shore
Authors: The SHORE Team CORPORATE
Published: November 2005

Shore is a persistent object system under development at the University of Wisconsin that represents a merger of key features of object-oriented database (OODB) and file system technologies: Concurrency control and recovery and bulk operations on clustered data as in traditional databases; objects of widely varying sizes with individual identity, globally unique identifiers, and a rich object-oriented type system as in OODB systems; and an open architecture, a uniform, universal hierarchical name space, and controlled sharing of disks with reliably enforced ownership of data and space accounting. A more complete overview of the goals and structure of Share were presented at this conference last year [Carey
et al,
SIGMOD 94].
Toward autonomic computing with DB2 universal database
Authors: Lightstone Sam S. , Lohman Guy , Zilio Danny
Published: November 2005

As the cost of both hardware and software falls due to technological advancements and economies of scale, the cost of ownership for database applications is increasingly dominated by the cost of people to manage them. Databases are growing rapidly in scale and complexity, while skilled database administrators (DBAs) are becoming rarer and more expensive. This paper describes the self-managing or autonomic technology in IBM's DB2 Universal Database® for UNIX and Windows to illustrate how self-managing technology can reduce complexity, helping to reduce the total cost of ownership (TCO) of DBMSs and improve system performance.
XQuery formal semantics state and challenges
Authors: Fankhauser Peter
Published: November 2005

The XQuery formalization is an ongoing effort of the W3C XML Query working group to define a precise formal semantics for XQuery. This paper briefly introduces the current state of the formalization and discusses some of the more demanding remaining challenges in formally describing an expressive query language for XML.
A general technique for querying XML documents using a relational database system
Authors: Shanmugasundaram Jayavel , Shekita Eugene , Kiernan Jerry , Krishnamurthy Rajasekar , Viglas Efstratios , Naughton Jeffrey , Tatarinov Igor
Published: November 2005

There has been recent interest in using relational database systems to store and query XML documents. Each of the techniques proposed in this context works by (a) creating tables for the purpose of storing XML documents (also called
relational schema generation
), (b) storing XML documents by shredding them into rows in the created tables, and (c) converting queries over XML documents into SQL queries over the created tables. Since relational schema generation is a physical database design issue -- dependent on factors such as the nature of the data, the query workload and availability of schemas -- there have been many techniques proposed for this purpose. Currently, each relational schema generation technique requires its own query processor to efficiently convert queries over XML documents into SQL queries over the created tables. In this paper, we present an efficient technique whereby the
same
query-processor can be used for
all
such relational schema generation techniques. This greatly simplifies the task of relational schema generation by eliminating the need to write a special-purpose query processor for each new solution to the problem. In addition, our proposed technique enables users to query seamlessly across relational data and XML documents. This provides users with unified access to both relational and XML data without them having to deal with separate databases.
On database theory and XML
Authors: Suciu Dan
Published: November 2005

Over the years, the connection between database theory and database practice has weakened. We argue here that the new challenges posed by XML and its applications are strengthening this connection today. We illustrate three examples of theoretical problems arising from XML applications, based on our own research.
Preservation of digital data with self-validating, self-instantiating knowledge-based archives
Authors: Ludäscher Bertram , Marciano Richard , Moore Reagan
Published: November 2005

Digital archives are dedicated to the long-term preservation of electronic information and have the mandate to enable sustained access despite rapid technology changes. Persistent archives are confronted with heterogeneous data formats, helper applications, and platforms being used over the lifetime of the archive. This is not unlike the interoperability challenges, for which mediators are devised. To prevent technological obsolescence over time and across platforms, a migration approach for persistent archives is proposed based on an XML infrastructure.We extend current archival approaches that build upon standardized data formats and simple metadata mechanisms for collection management, by involving high-level
conceptual models
and
knowledge representations
as an integral part of the archive and the ingestion/migration processes. Infrastructure independence is maximized by archiving generic,
executable specifications
of (i) archival constraints (i.e., "model validators"), and (ii) archival transformations that are part of the ingestion process. The proposed architecture facilitates construction of
self-validating
and
self-instantiating
knowledge-based archives. We illustrate our overall approach and report on first experiences using a sample collection from a collaboration with the National Archives and Records Administration (NARA).
The evolution of effective B-tree
Authors: Lomet David
Published: November 2005

An under-appreciated facet of index search structures is the importance of high performance search within B-tree internal nodes. Much attention has been focused on improving node fanout, and hence minimizing the tree height [BU77, LL86]. [GG97, Lo98] have discussed the importance of B-tree page size. A recent article [GL2001] discusses internal node architecture, but the subject is buried in a single section of the paper.In this short note, I want to describe the long evolution of good internal node architecture and techniques, including an understanding of what problem was being solved during each of the incremental steps that have led to much improved node organizations.
The Ecobase project
Authors: Bouganim Luc , Cavalcanti Maria Claudia , Fabret Françoise , Campos Maria Luiza , Llirbat François , Mattoso Marta , Melo Rubens , Moura Ana Maria , Pacitti Esther , Porto Fabio , Simoes Margareth , Simon Eric , Tanaka Asterio , Valduriez Patrick
Published: November 2005

A very large number of data sources on environment, energy, and natural resources are available worldwide. Unfortunately, users usually face several problems when they want to search and use relevant information. In the Ecobase project, we address these problems in the context of several environmental applications in Brazil and Europe. We propose a distributed architecture for environmental information systems (EIS) based on the Le Select middleware developed at INRIA. In this paper, we present this architecture and its capabilities, and discuss the lessons learned and open issues.
Continuous queries over data streams
Authors: Babu Shivnath , Widom Jennifer
Published: November 2005

In many recent applications, data may take the form of continuous
data streams,
rather than finite stored data sets. Several aspects of data management need to be reconsidered in the presence of data streams, offering a new research direction for the database community. In this paper we focus primarily on the problem of query processing, specifically on how to define and evaluate
continuous queries
over data streams. We address semantic issues as well as efficiency concerns. Our main contributions are threefold. First, we specify a general and flexible architecture for query processing in the presence of data streams. Second, we use our basic architecture as a tool to clarify alternative semantics and processing techniques for continuous queries. The architecture also captures most previous work on continuous queries and data streams, as well as related concepts such as triggers and materialized views. Finally, we map out research topics in the area of query processing over data streams, showing where previous work is relevant and describing problems yet to be addressed.
Career-enhancing services at SIGMOD online
Authors: Labrinidis Alexandros , Mendelzon Alberto O.
Published: November 2005

This article serves three purposes. First of all, to introduce
dbjobs,
the database of database jobs, and also describe its functionality and architecture. Secondly, to present statistics for the dbgrads system, after 18 months of continuous operation. Finally, to describe exciting future projects for SIGMOD Online.
ADAM
Authors: Barbará Daniel , Couto Julia , Jajodia Sushil , Wu Ningning
Published: November 2005

Intrusion detection systems have traditionally been based on the characterization of an attack and the tracking of the activity on the system to see if it matches that characterization. Recently, new intrusion detection systems based on data mining are making their appearance in the field. This paper describes the design and experiences with the ADAM (Audit Data Analysis and Mining) system, which we use as a testbed to study how useful data mining techniques can be in intrusion detection.
Using unknowns to prevent discovery of association rules
Authors: Saygin Yücel , Verykios Vassilios S. , Clifton Chris
Published: November 2005

Data mining technology has given us new capabilities to identify correlations in large data sets. This introduces risks when the data is to be made public, but the correlations are private. We introduce a method for selectively removing individual values from a database to prevent the discovery of a set of rules, while preserving the data for other applications. The efficacy and complexity of this method are discussed. We also present an experiment showing an example of this methodology.
Describing semistructured data
Authors: Cardelli Luca
Published: November 2005

We introduce a rich language of
descriptions
for semistructured tree-like data, and we explain how such descriptions relate to the data they describe. Various query languages and data schemas can be based on such descriptions.
A process model for data bases
Authors: Guyot Jacques
Published: November 2005

we present a process model for data bases, which integrates concepts of relation, process, integrity constraint, event and period. The model allows one to specify the synchronization of processes and the constraints due to consumption and production of data. In particular we present the formalization which is carried out with the Petri Nets. These are obtained by using refining primitives which keep the interpretation simple for designers. The aspects of verification and validation of the specification are also examined.
A conceptual architecture for semantic web enabled web services
Authors: Bussler Christoph , Fensel Dieter , Maedche Alexander
Published: November 2005

Semantic Web Enabled Web Services (SWWS) will transform the web from a static collection of information into a distributed device of computation on the basis of Semantic technology making content within the World Wide Web machine-processable and machine-interpretable. Semantic Web Enabled Web Services will allow the automatic discovery, selection and execution of inter-organization business logic making areas like dynamic supply chain composition a reality. In this paper we introduce the vision of Semantic Web Enabled Web Services, describe requirements for building semantics-driven web services and sketch a first draft of conceptual architecture for implementing semantic web enabled web services.
The Grid
Authors: Goble Carole , De Roure David
Published: November 2005

The Grid is an emerging platform to support on-demand "virtual organisations" for coordinated resource sharing and problem solving on a global scale. The application thrust is large-scale scientific endeavour, and the scale and complexity of scientific data presents challenges for databases. The Grid is beginning to exploit technologies developed for Web Services and to realise its potential it also stands to benefit from Semantic Web technologies; conversely, the Grid and its scientific users provide application pull which will benefit the Semantic Web.
A graphical query language for mobile information systems
Authors: Chang Ya-Hui
Published: November 2005

The advance of the mobile computing environment allows data to be accessed in any place at any time, but currently only simple and ad-hoc queries are supported. People are eager for mobile information systems with more functionality and powerful querying facilities. In this paper, a graphical query language called MoSQL is proposed to be the basis of general mobile information systems. It provides a uniform way for users to access alphanumerical data and to query current or future location information, based on an
icon-based
interface. The interface is particularly suitable for the mobile environment, since it is easily operated by clicking or
dragging
the mouse. An example and the underlying theoretical framework will be presented in this paper to demonstrate the functionality of MoSQL.
A database approach to quality of service specification in video databases
Authors: Bertino Elisa , Elmagarmid Ahmed K. , Hacid Mohand-Saïd
Published: November 2005

Quality of Service (QoS) is defined as a set of perceivable attributes expressed in a user-friendly language with parameters that may be subjective or objective. Objective parameters are those related to a particular service and are measurable and verifiable. Subjective parameters are those based on the opinions of the end-users. We believe that quality of service should become an integral part of multimedia database systems and users should be able to query by requiring a quality of service from the system. The specification and enforcement of QoS presents an interesting challenge in multimedia systems development. A deal of effort has been done on QoS specification and control at the system and the network levels, but less work has been done at the application/user level. In this paper, we propose a language, in the style of constraint database languages, for formal specification of QoS constraints. The satisfaction by the system of the user quality requirements can be viewed as a constraint satisfaction problem. We believe this paper represents a first step towards the development of a database framework for quality of service management in video databases. The contribution of this paper lies in providing a logical framework for specifying and enforcing quality of service in video databases. To our knowledge, this work is the first from a database perspective on quality of service management.
Parallelism and concurrency control performance in distributed database machines
Authors: Carey Michael J. , Livny Miron
Published: November 2005

While several distributed (or 'shared nothing') database machines exist in the form of prototypes or commercial products, and a number of distributed concurrency control algorithms are available, the effect of parallelism on concurrency control performance has received little attention. This paper examines the interplay between parallelism and transaction performance in a distributed database machine context. Four alternative concurrency control algorithms are considered, including two-phase locking, wound-wait, basic timestamp ordering, and optimistic concurrency control. Issues addressed include how performance scales as a function of machine size and the degree to which partitioning the database for intra-transaction parallelism improves performance for the different algorithms. We examine performance from several perspectives, including response time, throughput, and speedup, and we do so over a fairly wide range of system loads. We also examine the performance impact of certain important overhead factors (e.g., communication and process initiation costs) on the four alternative concurrency control algorithms.
Relational specifications of infinite query answers
Authors: Chomicki Jan , Imieliński Tomasz
Published: November 2005

We investigate here functional deductive databases: an extension of DATALOG capable of representing infinite phenomena. Rules in functional deductive databases are Horn and predicates can have arbitrary unary and limited
k
-ary function symbols in one fixed position. This class is known to be decidable. However, least fixpoints of functional rules may be infinite. We present here a method to finitely represent infinite least fixpoints and infinite query answers as
relational specifications
. Relational specifications consist of a finite set of tuples and of a finitely specified congruence relation. Our method is applicable to every domain-independent set of functional rules.
Solving implication problems in database applications
Authors: Sun Xian-He , Kamel Nabil , Ni Lionel M.
Published: November 2005

Computing queries from derived relations, optimizing queries from a group of queries, and updating materialized views are important database problems and have attracted much attention. One thing common to these problems is their demand to quickly solve the implication problem — given two predicates σ

Q

and σ
τ
, can σ

Q

imply σ
τ
(σ

Q

→σ
τ
)? The implication problem has been solved by converting it into a satisfiability problem. Based on a graph representation, a detailed study of the general implication problem on its own is presented in this paper. We proved that the general implication problem, in which all six comparison operators: =, ≠, <, >, ≤, ≥, as well as conjunctions and disjunctions are allowed, is NP-hard. In the case when “≠” operators are not allowed in σ

Q

and disjunctions are not allowed in σ
τ
, a polynomial time algorithm is proposed to solve this restricted implication problem. The influence of the “≠” operator and disjunctions are studied. Our theoretical results show that for some special cases the polynomial complexity algorithm can solve the implication problem which allows the “≠” operator or disjunctions in the predicates. Necessary conditions for detecting when the “≠” operator and disjunctions are allowed are also given. These results are very useful in creating heuristic methods.
Towards an efficient evaluation of general queries: quantifier and disjunction processing revisited
Authors: Bry Francois
Published: November 2005

Database applications often require to evaluate queries containing quantifiers or disjunctions, e.g., for handling general integrity constraints. Existing efficient methods for processing quantifiers depart from the relational model as they rely on non-algebraic procedures. Looking at quantified query evaluation from a new angle, we propose an approach to process quantifiers that makes use of relational algebra operators only. Our approach performs in two phases. The first phase normalizes the queries producing a canonical form. This form permits to improve the translation into relational algebra performed during the second phase. The improved translation relies on a new operator - the
complement-join -
that generalizes the set difference, on algebraic expressions of universal quantifiers that avoid the expensive division operator in many cases, and on a special processing of disjunctions by means of
constrained outer-joins.
Our method achieves an efficiency at least comparable with that of previous proposals, better in most cases. Furthermore, it is considerably simpler to implement as it completely relies on relational data structures and operators.
Conflict resolution of rules assigning values to virtual attributes
Authors: Ioannidis Yannis E. , Sellis Timos K.
Published: November 2005

In the majority of research work done on logic programming and deductive databases, it is assumed that the set of rules defined by the user is
consistent
, i.e., that no contradictory facts can be inferred by the rules. In this paper, we address the problem of resolving conflicts of rules that assign values to virtual attributes. We devise a general framework for the study of the problem, and we propose an approach that subsumes all previously suggested solutions. Moreover, it suggests several additional solutions, which very often capture the semantics of the data more accurately than the known approaches. Finally, we address the issue of how to index rules so that conflicts are resolved efficiently, i.e., only one of the applicable rules is processed at query time.
Composite objects revisited
Authors: Kim Won , Bertino Elisa , Garza Jorge F.
Published: November 2005

In object-oriented systems, an object may recursively reference any number of other objects. The references, however, do not capture any special relationships between objects. An important semantic relationship which may be superimposed on a reference is the IS-PART-OF relationship between a pair of objects. A set of objects related by the IS-PART-OF relationship is collectively called a composite object.

An earlier paper [KIM87b] presented a model of composite objects which has been implemented in the ORION object-oriented database system at MCC. Although the composite-object feature has been found quite useful, the model suffers from a number of serious shortcomings, primarily because it overloads a number of orthogonal semantics on the references. In this paper, first we present a more general model of composite objects which does not suffer from these shortcomings. Further, [KIM87b] made an important contribution by exploring the use of composite objects as a unit for versions, physical clustering, and concurrency control. The extended model of composite objects necessitates non-trivial changes to the results of [KIM87b]. This paper describes the new results on the use of composite objects as a unit of not only versions, physical clustering and concurrency control, but also authorization.
Modular synchronization in multiversion databases: version control and concurrency control
Authors: Agrawal D. , Sengupta S.
Published: November 2005

In this paper we propose a version control mechanism that enhances the modularity and extensibility of multiversion concurrency control algorithms. We decouple the multiversion algorithms into two components: version control and concurrency control. This permits modular development of multiversion protocols, and simplifies the task of proving the correctness of these protocols. An interesting feature of our framework is that the execution of read-only transactions becomes completely independent of the underlying concurrency control implementation. Also, algorithms with the version control mechanism have several advantages over most other multiversion algorithms.
An initial report on the design of Ariel DBMS with an integrated production rule system
Authors: Hanson E. N.
Published: November 2005

The design and implementation strategy for Ariel, A DBMS with a built-in production rule system (a trigger system), is described. Ariel is being built with the EXODUS database tool kit. The query language of Ariel is a subset of POSTQUEL extended with a new rule language. Effort is focussed on integrating the rule system with transaction processing, and making the rule system powerful and efficient. The current implementation of the rule condition-testing mechanism in Ariel is based on a variation of the Rete network, a type of discrimination network used widely in rule-based systems tools for artificial intelligence programming. The standard Rete algorithm has been extended to improve performance in a database environment.
Rule representation and management in conceptbase
Authors: Jarke M. , Jeusfeld M.
Published: November 2005

ConceptBase is an experimental knowledge base management system for design applications, especially in the software engineering area. The knowledge representation language it supports, CML/Telos, combines the functionalities of deductive and temporal databases with structural object orientation. In this paper, we demonstrate how to exploit a process-oriented software data model that uses just the object-oriented structural language kernel, to bootstrap efficient internal representations of the rule sub-language.
Data intensive production systems: the DIPS approach
Authors: Sellis T. , Lin C. , Raschid L.
Published: November 2005

In this paper we highlight the basic approach taken in the design of the DIPS system, and briefly present the main contributions. These include the use of special data structures to store rule definitions; they are implemented using relations. A matching algorithm uses these structures to efficiently identify when the antecedents of productions are satisfied, making them applicable for execution. Partial match information stored in the data structures is used by the matching algorithm. We also describe a proposed concurrent execution strategy for applicable productions, which surpasses in performance, the traditional sequential OPS5 production execution algorithm. The requirements for a correct, serializable execution, based on locking, is described. An advantage of the matching technique in DIPS is that it is fully parallelizable, which makes it attractive for implementation in parallel computing environments.
The case for partial indexes
Authors: Stonebraker M.
Published: November 2005

Current data managers support secondary and/or primary indexes on columns of relations. In this paper we suggest the advantages that result from indexes which contain only some of the possible values in a column of a relation.
A note on the relational calculus
Authors: Date C. J.
Published: November 2005

We examine a logical anomaly in Codd's relational calculus [1], according to which queries can occasionally return somewhat surprising results.