bluuebunny/crossref_metadata_2025 huggingface dataset:
Adding spice to software development
Authors: Beams Jay D.
Published: November 2005

The Office of Military Applications and Stockpile Support of the Office of Defense Programs (DP-20) within the U.S. Department of Energy (DOE) is responsible for managing nuclear materials. Over the last five years, changes at home and abroad have had a dramatic effect on DP-20. The end of the Cold War and the associated treaties have shifted much of DP-20 work from nuclear weapons production to the maintenance of a shrinking stockpile. The declassification of information has required DP-20 personnel to probe into data archived for decades. (You can't declassify information without having the information available.) Finally, the election of a new president has led to the restructuring of DOE and severe down-sizing of DP. These changes, and many others not mentioned, have made DP-20 a rapidly changing environment.
A framework for the development of information appliances
Authors: Thomas Peter J. , Meech John F. , Macredie Robert D.
Published: November 2005

This paper provides a framework for the design and development of personal information appliances - interactive technologies which aim to assist users in managing personal information in organisational, group and environmental contexts. The emphasis is on integration, both in terms of the development of integrated families of appliances and in terms of way in which appliances provide an integration of the diverse media necessary to support the management of personal information.
PC notes
Authors: Styer Eugene
Published: November 2005

In this second installment in the series, we will explore the representation of integer numbers. With some exceptions among the early computers, almost every digital computer built has worked in binary, including (for our purposes) the 80x86 family. Therefore we will take a little time to see how binary numbers work.
Multi-table joins through bitmapped join indices
Authors: O'Neil Patrick , Graefe Goetz
Published: November 2005

This technical note shows how to combine some well-known techniques to create a method that will efficiently execute common multi-table joins. We concentrate on a commonly occurring type of join known as a
star-join,
although the method presented will generalize to any type of multi-table join. A star-join consists of a central
detail
table with large cardinality, such as an orders table (where an order row contains a single purchase) with foreign keys that join to
descriptive
tables, such as customers, products, and (sales) agents. The method presented in this note uses
join indices
with
compressed bitmap
representations, which allow predicates restricting columns of descriptive tables to determine an answer set (or
foundset
) in the central detail table; the method uses different predicates on different descriptive tables in combination to restrict the detail table through compressed bitmap representations of join indices, and easily completes the join of the fully restricted detail table rows back to the descriptive tables. We outline realistic examples where the combination of these techniques yields substantial performance improvements over alternative, more traditional query evaluation plans.
Mapping extended entity relationship model to object modeling technique
Authors: Fong Joseph
Published: November 2005

A methodology of reengineering existing extended Entity-Relationship(EER) model to Object Modeling Technique(OMT) model is described. A set of translation rules from EER model to a generic Object-Oriented(OO) model of OMT methodology is devised. Such reengineering practices not only can provide us with significant insight to the "interoperability" between the OO and the traditional semantic modelling techniques, but also can lead us to the development of a practical design methodology for object-oriented databases(OODB).
An introduction to Remy's fast polymorphic record projection
Authors: Wong Limsoon
Published: November 2005

Traditionally, a record projection is compiled when all fields of the record are known in advance. The need to know all fields in advance leads to very clumsy programs, especially for querying external data sources. In a paper that had not been widely circulated in the database community, Remy presented in programming language context a constant-time implementation of the record projection operation that does not have such a requirement. This paper introduces his technique and suggests an improvement to his technique in the context of database queries.
On the issue of valid time(s) in temporal databases
Authors: Kokkotos Stavros , Ioannidis Efstathios V. , Panayiotopoulos Themis , Spyropoulos Constantine D.
Published: November 2005

Recent research activities in the area of Temporal Databases have revealed some problems related to the definition of time. In this paper we discuss the problem arising from the definition of valid time and the assumptions about valid time, which exist in current Temporal Database approaches. For this problem we propose a solution, while we identify some consistency problems that may appear in Temporal Databases, and which require further investigation.
Information finding in a digital library
Authors: Yan Tak W. , García-Molina Héctor
Published: November 2005

In a digital library one of the most challenging problems is finding relevant information. Information finding is the research focus of the Stanford component of the ARPA-sponsored CS-TR Project, and the work has continued as one of the main thrusts in the Stanford Integrated Digital Library project [14]. In this paper we discuss some of the emerging issues in information finding, such as text-database discovery, efficient information dissemination, and copy detection and removal. We also outline our approaches to these issues.
Data management research at the MITRE Corporation
Authors: Rosenthal Arnon , Seligman Len , McCollum Catherine , Blaustein Barbara , Thuraisingham Bhavani , Lafferty Edward
Published: November 2005

The MITRE Corporation provides technical assistance, system engineering, and acquisition support to large organizations, especially U.S. Government agencies. We help our customers to plan complex systems based on emerging technologies, and to implement systems based on commercial-off-the-shelf products. In MITRE's research program, instead of emphasizing concerns of DBMS or CASE vendors, our research emphasizes the issues of organizations who need to use such products. For example, we favor areas where we can build over commercial products, rather than changing their internals.Data management at MITRE goes beyond research, to include technology transition, system engineering, product evaluation, prototypes, tutorials, advice on customers' strategic directions, and participation in standards efforts. We use prototyping to illustrate potential improvements in customer systems, to understand vendors' capabilities, or both. There are close connections with efforts in object management, real-time systems, reengineering, artificial intelligence, and security.This paper emphasizes the research efforts, grouped into five major themes: information integration, security and privacy, active and responsive systems, metrics, and digital libraries. For each theme, we list the major questions being explored, and identify projects and contacts for further information.
Wireless client/server computing for personal information services and applications
Authors: Elmagarmid Ahmed , Jing Jin , Furukawa Tetsuya
Published: November 2005

We are witnessing a profound change in the global information infrastructure that has the potential to fundamentally impact many facets of our life. An important aspect of the evolving infrastructure is the seamless, ubiquitous wireless connectivity which engenders continuous interactions between people and interconnected computers. A challenging area of future ubiquitous wireless computing is the area of providing mobile users with integrated Personal Information Services and Applications (PISA). In this paper, a wireless client/server computing architecture will be discussed for the delivery of PISA. Data management issues such as transactional services and cache consistency will be examined under this architecture.
Managing video data in a mobile environment
Authors: Alonso Rafael , Chang Yuh-Lin , Iftode Liviu , Mani V. S.
Published: November 2005

Two key technological trends of the last few years have been the emergence of handheld computational elements and the implementation of practical wireless communication networks. These two changes have made mobile computer systems feasible. While there has been much research interest devoted to mobile computer issues, such systems have not yet been commercially successful. This has been ascribed to the lack of a
killer mobile app
. We believe that the support of video on mobile systems will indeed make possible many new interesting applications.

However, providing mobile video is a non-trivial task, and much work needs to be done before practical systems are widely available. In this short note we address the issue of mobile multimedia from a practitioner's perspective. We note what software and hardware are currently available in the market in support of mobile multimedia, and point out some of their deficiencies. We also discuss some of the communication and data management research issues that need to be tackled in order to address said deficiencies. Exploring these research issues is the focus of our project.
Digital library services in mobile computing
Authors: Bhargava Bharat , Annamalai Melliyal , Pitoura Evaggelia
Published: November 2005

Digital libraries bring about the integration, management, and communication of gigabytes of multimedia data in a distributed environment. Digital library systems currently envision users as being static when they access information. But it is expected in the near future that tens of millions of users will have access to a digital library through wireless access. Providing digital library services to users whose location is constantly changing, whose network connections are through a wireless medium, and whose computing power is low necessitates modifications to existing digital library systems. In this paper, we identify the issues that arise when users are mobile, classify queries that are specific to mobile users and introduce an architecture that supports flexible and transparent access to digital libraries for mobile users. The main features of the architecture include a layered data representation, support of adaptability, dual broadcast and on demand querying, caching, and mobile-specific user interfaces.
Replication
Authors: Stacey Doug
Published: November 2005

Is replication salvation or the devil in disguise? Here's what three implementations tell us
K12 and the web
Authors: Mengel Susan A.
Published: November 2005

K12 resources on and uses of the internet are becoming plentiful. Previously many home pages on the World Wide Web (WWW) were only text, but now students have created colorful graphics and even movies for the Web. The excitement of the students is contagious and, as a result, many schools have allowed part of their home pages to be designed by the students themselves. This paper discusses how students are gaining access to the internet and how educators are enabling that access to happen.
The state of HTML
Authors: Bouvier Dennis J.
Published: November 2005

In the brief history of the World Wide Web (WWW), much has changed. Millions of web pages have been published in a very short time. Next to the Web content, the most dynamic aspect of the WWW is the development of HyperText Markup Language (HTML). This paper explores the various version of HTML and gives a status report on HTML standards development.
PC notes
Authors: Styer Eugene
Published: November 2005

In this third installment in the series, we will start looking at the internals of the 80x86 family. There are fourteen registers contained in the original 8088. The registers are listed below:See pdf for registers.
Surfin on the Net
Authors: McKenna Christopher
Published: November 2005

The purpose of this document is to help people to understand how to write basic hypertext documents in the HyperText Markup Language (HTML). HTML is the language of the World Wide Web(WWW), a spider web of documentation spread all across the world. HTML allows the "readers" to interact with the documents they read. The author can set up "HyperLinks" within a document or between documents to help the reader move through the information or get to a specific piece of information more quickly. HTML also allows the author to imbed images, sound, movie clips, and even animation into his/her document making it more exciting to read. HTML uses tags to structure the document to its final viewing/reading form. One can just about find a browser, a client application that will request documents from a server, for any platform. This make HTML very portable and a powerful tool for delivering documents to a large audience of people.
Intelligent forms
Authors: Wong Ka-Wing , Saiedian Hossein
Published: November 2005

This paper discusses intelligent forms and the development of distributed object-oriented intelligent form processing. Intelligent forms are described as objects at two levels: The metaphor-level and the operational level.
Open issues in parallel query optimization
Authors: Hasan Waqar , Florescu Daniela , Valduriez Patrick
Published: November 2005

We provide an overview of query processing in parallel database systems and discuss several open issues in the optimization of queries for parallel machines.
Control strategies for complex relational query processing in shared nothing systems
Authors: Brunie Lionel , Kosch Harald
Published: November 2005

In this paper, we present an original and complete methodology for supervising relational query processing in shared nothing systems. A new control mechanism is introduced which allows the detection and the correction of optimizer estimation errors and load imbalance. We especially focus on the management of intraprocessor communication and on the overlapping of communication and computation. Performance evaluations on an hypercube and a grid interconnection machine show the efficiency and the robustness of the proposed methods.
The active database management system manifesto
Authors: Act-Net Consortium Corporate
Published: November 2005

Active database systems have been a hot research topic for quite some years now. However, while “active functionality” has been claimed for many systems, and notions such as “active objects” or “events” are used in many research areas (even beyond database technology), it is not yet clear which functionality a database management system must support in order to be legitimately considered as an active system. In this paper, we attempt to clarify the notion of “active database management system” as well as the functionality it has to support. We thereby distinguish mandatory features that are needed to qualify as an active database system, and desired features which are nice to have. Finally, we perform a classification of applications of active database systems and identify the requirements for an active database management system in order to be applicable in these application areas.
BeSS object storage manager
Authors: Biliris Alexandros , Panagos Euthimios
Published: November 2005

BeSS is a high performance, memory-mapped object storage manager offering distributed transaction management facilities and extensible support for persistence. In this paper, we present an overview of the peer-to-peer architecture of BeSS, and we discuss issues related to space management, inter-object references, database corruption, operation modes, cache replacement, and transaction management.
Rapid bushy join-order optimization with Cartesian products
Authors: Vance Bennet , Maier David
Published: November 2005

Query optimizers often limit the search space for join orderings, for example by excluding Cartesian products in subplans or by restricting plan trees to left-deep vines. Such exclusions are widely assumed to reduce optimization effort while minimally affecting plan quality. However, we show that searching the complete space of plans is more affordable than has been previously recognized, and that the common exclusions may be of little benefit.We start by presenting a Cartesian product optimizer that requires at most a few seconds of workstation time to search the space of bushy plans for products of up to 15 relations. Building on this result, we present a join-order optimizer that achieves a similar level of performance, and retains the ability to include Cartesian products in subplans wherever appropriate. The main contribution of the paper is in fully separating join-order enumeration from predicate analysis, and in showing that the former problem in particular can be solved swiftly by novel implementation techniques. A secondary contribution is to initiate a systematic approach to the benchmarking of join-order optimization, which we apply to the evaluation of our method.
SQL query optimization
Authors: Goel Piyush , Iyer Bala
Published: November 2005

The strength of commercial query optimizers like DB2 comes from their ability to select an optimal order by generating all equivalent reorderings of binary operators. However, there are no known methods to generate all equivalent reorderings for a SQL query containing joins, outer joins, and groupby aggregations. Consequently, some of the reorderings with significantly lower cost may be missed. Using hypergraph model and a set of novel identities, we propose a method to reorder a SQL query containing joins, outer joins, and groupby aggregations. While these operators are sufficient to capture the SQL semantics, it is during their reordering that we identify a powerful primitive needed for a dbms. We report our findings of a simple, yet fundamental operator,
generalized selection,
and demonstrate its power to solve the problem of reordering of SQL queries containing joins, outer joins, and groupby aggregations.
Fundamental techniques for order optimization
Authors: Simmen David , Shekita Eugene , Malkemus Timothy
Published: November 2005

Decision support applications are growing in popularity as more business data is kept on-line. Such applications typically include complex SQL queries that can test a query optimizer's ability to produce an efficient access plan. Many access plan strategies exploit the physical ordering of data provided by indexes or sorting. Sorting is an expensive operation, however. Therefore, it is imperative that sorting is optimized in some way or avoided all together. Toward that goal, this paper describes novel optimization techniques for pushing down sorts in joins, minimizing the number of sorting columns, and detecting when sorting can be avoided because of predicates, keys, or indexes. A set of fundamental operations is described that provide the foundation for implementing such techniques. The operations exploit data properties that arise from predicate application, uniqueness, and functional dependencies. These operations and techniques have been implemented in IBM's DB2/CS.
Query caching and optimization in distributed mediator systems
Authors: Adali S. , Candan K. S. , Papakonstantinou Y. , Subrahmanian V. S.
Published: November 2005

Query processing and optimization in mediator systems that access distributed non-proprietary sources pose many novel problems. Cost-based query optimization is hard because the mediator does not have access to source statistics information and furthermore it may not be easy to model the source's performance. At the same time, querying remote sources may be very expensive because of high connection overhead, long computation time, financial charges, and temporary unavailability. We propose a cost-based optimization technique that caches statistics of actual calls to the sources and consequently estimates the cost of the possible execution plans based on the statistics cache. We investigate issues pertaining to the design of the statistics cache and experimentally analyze various tradeoffs. We also present a query result caching mechanism that allows us to effectively use results of prior queries when the source is not readily available. We employ the novel
invariants
mechanism, which shows how semantic information about data sources may be used to discover cached query results of interest.
Performance tradeoffs for client-server query processing
Authors: Franklin Michael J. , Jónsson Björn Thór , Kossmann Donald
Published: November 2005

The construction of high-performance database systems that combine the best aspects of the relational and object-oriented approaches requires the design of client-server architectures that can fully exploit client and server resources in a flexible manner. The two predominant paradigms for client-server query execution are data-shipping and query-shipping We first define these policies in terms of the restrictions they place on operator site selection during query optimization. We then investigate the performance tradeoffs between them for bulk query processing. While each strategy has advantages, neither one on its own is efficient across a wide range of circumstances. We describe and evaluate a more flexible policy called hybrid-shipping, which can execute queries at clients, servers, or any combination of the two. Hybrid-shipping is shown to at least match the best of the two "pure" policies, and in some situations, to perform better than both. The implementation of hybrid-shipping raises a number of difficult problems for query optimization. We describe an initial investigation into the use of a 2-step query optimization strategy as a way of addressing these issues.
The dangers of replication and a solution
Authors: Gray Jim , Helland Pat , O'Neil Patrick , Shasha Dennis
Published: November 2005

Update anywhere-anytime-anyway transactional replication has unstable behavior as the workload scales up: a ten-fold increase in nodes and traffic gives a thousand fold increase in deadlocks or reconciliations. Master copy replication (primary copy) schemes reduce this problem. A simple analytic model demonstrates these results. A new two-tier replication algorithm is proposed that allows mobile (disconnected) applications to propose tentative update transactions that are later applied to a master copy. Commutative update transactions avoid the instability of other replication schemes.
Bifocal sampling for skew-resistant join size estimation
Authors: Ganguly Sumit , Gibbons Phillip B. , Matias Yossi , Silberschatz Avi
Published: November 2005

This paper introduces
bifocal sampling,
a new technique for estimating the size of an equi-join of two relations. Bifocal sampling classifies tuples in each relation into two groups, sparse and dense, based on the number of tuples with the same join value. Distinct estimation procedures are employed that focus on various combinations for joining tuples (e.g., for estimating the number of joining tuples that are dense in both relations). This combination of estimation procedures overcomes some well-known problems in previous schemes, enabling good estimates with no a priori knowledge about the data distribution. The estimate obtained by the bifocal sampling algorithm is proven to lie with high probability within a small constant factor of the actual join size, regardless of the skew, as long as the join size is Ω(
n
lg
n
), for relations consisting of
n
tuples. The algorithm requires a sample of size at most
O
(√
n
lg
n
). By contrast, previous algorithms using a sample of similar size may require the join size to be Ω(
n
√
n
) to guarantee an accurate estimate. Experimental results support the theoretical claims and show that bifocal sampling is practical and effective.
Improved histograms for selectivity estimation of range predicates
Authors: Poosala Viswanath , Haas Peter J. , Ioannidis Yannis E. , Shekita Eugene J.
Published: November 2005

Many commercial database systems maintain histograms to summarize the contents of relations and permit efficient estimation of query result sizes and access plan costs. Although several types of histograms have been proposed in the past, there has never been a systematic study of all histogram aspects, the available choices for each aspect, and the impact of such choices on histogram effectiveness. In this paper, we provide a taxonomy of histograms that captures all previously proposed histogram types and indicates many new possibilities. We introduce novel choices for several of the taxonomy dimensions, and derive new histogram types by combining choices in effective ways. We also show how sampling techniques can be used to reduce the cost of histogram construction. Finally, we present results from an empirical study of the proposed histogram types used in selectivity estimation of range predicates and identify the histogram types that have the best overall performance.
Safe and efficient sharing of persistent objects in Thor
Authors: Liskov B. , Adya A. , Castro M. , Ghemawat S. , Gruber R. , Maheshwari U. , Myers A. C. , Day M. , Shrira L.
Published: November 2005

Thor is an object-oriented database system designed for use in a heterogeneous distributed environment. It provides highly-reliable and highly-available persistent storage for objects, and supports safe sharing of these objects by applications written in different programming languages.Safe heterogeneous sharing of long-lived objects requires encapsulation: the system must guarantee that applications interact with objects only by invoking methods. Although safety concerns are important, most object-oriented databases forgo safety to avoid paying the associated performance costs.This paper gives an overview of Thor's design and implementation. We focus on two areas that set Thor apart from other object-oriented databases. First, we discuss safe sharing and techniques for ensuring it; we also discuss ways of improving application performance without sacrificing safety. Second, we describe our approach to cache management at client machines, including a novel adaptive prefetching strategy.The paper presents performance results for Thor, on several OO7 benchmark traversals. The results show that adaptive prefetching is very effective, improving both the elapsed time of traversals and the amount of space used in the client cache. The results also show that the cost of safe sharing can be negligible; thus it is possible to have both safety and high performance.
An open abstract-object storage system
Authors: Blott Stephen , Relly Lukas , Schek Hans-Jörg
Published: November 2005

Database systems must become more open to retain their relevance as a technology of choice and necessity. Openness implies not only databases exporting their data, but also exporting their services. This is as true in classical application areas as in non-classical (GIS, multimedia, design, etc).This paper addresses the problem of exporting storage-management services of indexing, replication and basic query processing. We describe an abstract-object storage model which provides the basic mechanism, '
likeness
', through which these services are applied uniformly to internally-stored, internally-defined data, and to externally-stored, externally-defined data. Managing external data requires the coupling of external operations to the database system. We discuss the interfaces and protocols required of these to achieve correct resource management and admit efficient realisation. Throughout, we demonstrate our solutions in the area of semi-structured file management; in our case, geospatial metadata files.
Static detection of security flaws in object-oriented databases
Authors: Tajima Keishi
Published: November 2005

Access control in function granularity is one of the features of many object-oriented databases. In those systems, the users are granted rights to invoke composed functions instead of rights to invoke primitive operations. Although primitive operations are invoked inside composed functions, the users can invoke them only through the granted functions. This achieves access control in abstract operation level. Access control utilizing encapsulated functions, however, easily causes many "security flaws" through which malicious users can bypass the encapsulation and can abuse the primitive operations inside the functions. In this paper, we develop a technique to statically detect such security flaws. First, we design a framework to describe security requirements that should be satisfied. Then, we develop an algorithm that syntactically analyzes program code of the functions and determines whether given security requirements are satisfied or not. This algorithm is sound, that is, whenever there is a security flaw, it detects it.
Multi-dimensional resource scheduling for parallel queries
Authors: Garofalakis Minos N. , Ioannidis Yannis E.
Published: November 2005

Scheduling query execution plans is an important component of query optimization in parallel database systems. The problem is particularly complex in a shared-nothing execution environment, where each system node represents a collection of time-shareable resources (e.g., CPU(s), disk(s), etc.) and communicates with other nodes only by message-passing. Significant research effort has concentrated on only a subset of the various forms of intra-query parallelism so that scheduling and synchronization is simplified. In addition, most previous work has focused its attention on one-dimensional models of parallel query scheduling, effectively ignoring the potential benefits of resource sharing. In this paper, we develop an approach that is more general in both directions, capturing all forms of intra-query parallelism and exploiting sharing of multi-dimensional resource nodes among concurrent plan operators. This allows scheduling a set of independent query tasks (i.e., operator pipelines) to be seen as an instance of the multi-dimensional bin-design problem. Using a novel quantification of coarse grain parallelism, we present a list scheduling heuristic algorithm that is provably near-optimal in the class of coarse grain parallel executions (with a worst-case performance ratio that depends on the number of resources per node and the granularity parameter). We then extend this algorithm to handle the operator precedence constraints in a bushy query plan by splitting the execution of the plan into synchronized phases. Preliminary performance results confirm the effectiveness of our scheduling algorithm compared both to previous approaches and the optimal solution. Finally, we present a technique that allows us to relax the coarse granularity restriction and obtain a list scheduling method that is provably near-optimal in the space of all possible parallel schedules.
Rule languages and internal algebras for rule-based optimizers
Authors: Cherniack Mitch , Zdonik Stanley B.
Published: November 2005

Rule-based optimizers and optimizer generators use rules to specify query transformations. Rules act directly on query representations, which typically are based on query algebras. But most algebras complicate rule formulation, and rules over these algebras must often resort to calling to externally defined bodies of code. Code makes rules difficult to formulate, prove correct and reason about, and therefore compromises the effectiveness of rule-based systems.In this paper we present KOLA: a combinator-based algebra designed to simplify rule formulation. KOLA is not a user language, and KOLA's variable-free queries are difficult for humans to read. But KOLA is an effective internal algebra because its combinator-style makes queries manipulable and structurally revealing. As a result, rules over KOLA queries are easily expressed without the need for supplemental code. We illustrate this point, first by showing some transformations that despite their simplicity, require head and body routines when expressed over algebras that include variables. We show that these transformations are expressible without supplemental routines in KOLA. We then show complex transformations of a class of nested queries expressed over KOLA. Nested query optimization, while having been studied before, have seriously challenged the rule-based paradigm.
Evaluating queries with generalized path expressions
Authors: Christophides Vassilis , Cluet Sophie , Moerkotte Guido
Published: November 2005

In the past few years, query languages featuring generalized path expressions have been proposed. These languages allow the interrogation of both data and structure. They are powerful and essential for a number of applications. However, until now, their evaluation has relied on a rather naive and inefficient algorithm.In this paper, we extend an object algebra with two new operators and present some interesting rewriting techniques for queries featuring generalized path expressions. We also show how a query optimizer can integrate the new techniques.
Maintaining database consistency in presence of value dependencies in multidatabase systems
Authors: Morpain Claire , Cart Michéle , Ferrié Jean , Pons Jean-François
Published: November 2005

The emergence of new criteria specifically adapted to multidatabase systems, in response to constraints imposed by global serializability, leads to restrictive hypotheses in order to ensure correctness of executions. This is the case with the
two level serializability
presented in [6], that ensures
strongly correct
executions if transaction programs are
Local Database Preserving (LDP).
The main drawback of the LDP hypothesis is that it relies on rigorous programming. The principal objective of this paper has been to suppress this drawback while conserving the strong correctness of 2LSR executions We propose defining precisely the notion of value dependencies, and managing them so as not to impose the LDP property.
Algorithms for deferred view maintenance
Authors: Colby Latha S. , Griffin Timothy , Libkin Leonid , Mumick Inderpal Singh , Trickey Howard
Published: November 2005

Materialized views and view maintenance are important for data warehouses, retailing, banking, and billing applications. We consider two related view maintenance problems: 1) how to maintain views after the base tables have already been modified, and 2) how to minimize the time for which the view is inaccessible during maintenance.Typically, a view is maintained
immediately,
as a part of the transaction that updates the base tables. Immediate maintenance imposes a significant overhead on update transactions that cannot be tolerated in many applications. In contrast,
deferred
maintenance allows a view to become inconsistent with its definition. A
refresh
operation is used to reestablish consistency. We present new algorithms to incrementally refresh a view during deferred maintenance. Our algorithms avoid a
state bug
that has artificially limited techniques previously used for deferred maintenance.Incremental deferred view maintenance requires auxiliary tables that contain information recorded since the last view refresh. We present three scenarios for the use of auxiliary tables and show how these impact per-transaction overhead and view refresh time. Each scenario is described by an invariant that is required to hold in all database states. We then show that, with the proper choice of auxiliary tables, it is possible to lower both per-transaction overhead and view refresh time.
A framework for supporting data integration using the materialized and virtual approaches
Authors: Hull Richard , Zhou Gang
Published: November 2005

This paper presents a framework for data integration currently under development in the Squirrel project. The framework is based on a special class of mediators, called
Squirrel integration mediators.
These mediators can support the traditional virtual and materialized approaches, and also hybrids of them.In the Squirrel mediators, a relation in the integrated view can be supported as (a) fully materialized, (b) fully virtual, or (c) partially materialized (i.e., with some attributes materialized and other attributes virtual). In general, (partially) materialized relations of the integrated view are maintained by incremental updates from the source databases. Squirrel mediators provide two approaches for doing this: (1) materialize all needed auxiliary data, so that data sources do not have to be queried when processing the incremental updates; or (2) leave some or all of the auxiliary data virtual, and query selected source databases when processing incremental updates.The paper presents formal notions of consistency and "freshness" for integrated views defined over multiple autonomous source databases. It is shown that Squirrel mediators satisfy these properties.
A query language and optimization techniques for unstructured data
Authors: Buneman Peter , Davidson Susan , Hillebrand Gerd , Suciu Dan
Published: November 2005

A new kind of data model has recently emerged in which the database is not constrained by a conventional schema. Systems like ACeDB, which has become very popular with biologists, and the recent Tsimmis proposal for data integration organize data in tree-like structures whose components can be used equally well to represent sets and tuples. Such structures allow great flexibility y in data representation.What query language is appropriate for such structures? Here we propose a simple language UnQL for querying data organized as a rooted, edge-labeled graph. In this model, relational data may be represented as fixed-depth trees, and on such trees UnQL is equivalent to the relational algebra. The novelty of UnQL consists in its programming constructs for arbitrarily deep data and for cyclic structures. While strictly more powerful than query languages with path expressions like XSQL, UnQL can still be efficiently evaluated. We describe new optimization techniques for the deep or "vertical" dimension of UnQL queries. Furthermore, we show that known optimization techniques for operators on flat relations apply to the "horizontal" dimension of UnQL.
State of the art in workflow management research and products
Authors: Mohan C.
Published: November 2005

In the last few years, workflow management has become a hot topic in the research community and, especially, in the commercial arena. Workflow management is multidisciplinary in nature encompassing many aspects of computing: database management, distributed client-server systems, transaction management, mobile computing, business process reengineering, integration of legacy and new applications, and heterogeneity of hardware and software. Many academic and industrial research projects are underway. Numerous successful products have been released. Standardization efforts are in progress under the auspices of the Workflow Management Coalition. As has happened in the RDBMS area with respect to some topics, in the workflow area also, some of the important real-life problems faced by customers and product developers are not being tackled by researchers. This tutorial will survey the state of the art in workflow management research and products.
Data mining techniques
Authors: Han Jiawei
Published: November 2005

Data mining, or knowledge discovery in databases, has been popularly recognized as an important research issue with broad applications. We provide a comprehensive survey, in database perspective, on the data mining techniques developed recently. Several major kinds of data mining methods, including generalization, characterization, classification, clustering, association, evolution, pattern matching, data visualization, and meta-rule guided mining, will be reviewed. Techniques for mining knowledge in different kinds of databases, including relational, transaction, object-oriented, spatial, and active databases, as well as global information systems, will be examined. Potential data mining applications and some research issues will also be discussed.
DBMiner
Authors: Han Jaiwei , Fu Youngjian , Wang Wei , Chiang Jenny , Zaïane Osmar R. , Koperski Krzysztof
Published: November 2005

Based on our years-of-research, a data mining system, DB-Miner, has been developed for interactive mining of multiple-level knowledge in large relational databases. The system implements a wide spectrum of data mining functions, including generalization, characterization, association, classification, and prediction. By incorporation of several interesting data mining techniques, including attribute-oriented induction, progressive deepening for mining multiple-level rules, and meta-rule guided knowledge mining, the system provides a user-friendly, interactive data mining environment with good performance.
The Demeter method: an efficient way to build adaptive software
Authors: Liu Yang , Pradhan Salil
Published: November 2005

Many object-oriented software developers often face the optimal class structure problem when a large, complex project starts. They have to find a class structure and improve it iteratively during the development process. Changes to the class structure cause substantial effort to maintain behaviors built upon the original class structure[5]. And a general application, like a project defect management system, is usually developed based on a class structure extracted from a specific problem domain, for example, software system defect tracking and repairing. Next time when similar requirements (i.e. a semiconductor system defect tracking and repairing) come in, the existing application is found hard to adapt to the new context for the reason that too many details of user-related class structure are included and encoded into the application implementation. Most developers would rather adopt the build-from-scratch techniques than reuse the current system, though they have very similar requirements.
Knowledge-based OOP
Authors: Wong Ka-Wing
Published: November 2005

Writing concurrent programs in the Object-Oriented Programming (OOP) environment is a challenge. In this paper, we present a knowledge-based solution in which program properties are specifiable and verifiable. We demonstrate the usefulness of the solution by solving the mutual exclusion problem [4] for a set of processes competing for a method in a class.
PC note
Authors: Styer Eugene
Published: November 2005

In this sixth installment in the series it is time to look at the addressing modes and how some common high-level language constructs would be translated into assembly language.
A neural network for speedy trials
Authors: Hashemi Ray R. , Schafer Therese M. , Hinson William G. , Talburt John R.
Published: November 2005

In recent years, the case loads of judges have increased, while speedy trial laws place a time limit between the defendant's arrest and trial dates. Because of this time constraint, it seems that for minor cases, judges pass sentences based on a set of certain factors (patterns) not based on the individual merits of each case. Patterns may be learned by a neural network. In this paper, we investigate the credibility of the neural network approach as a viable tool in the sentencing process and we show its superiority over the ID3 approach.
Decentralized routing algorithms for automated guided vehicles
Authors: Soh Jeffrey T. L. , Hsu Wen-Jing , Huang Shell-Ying , Ong Adrian C. Y.
Published: November 2005

Automated Guided Vehicles (AGVs) are driverless vehicles that are becoming a popular means for material handling. Existing methods for routing AGVs are generally based on centralized control. The central controller is potentially a bottleneck of communication and the single point of weakness of the system. Moreover, the computational cost required to preplan all AGV routes may be too high as to affect the scalability of the solution. Our project aims to design and develop decentralized routing strategies for an AGV system deployed within a container port. Two routing algorithms were developed: Row-First and Semi-Random. The goal is to minimize deadlocks and congestion and maximize throughput. The performance of the algorithms were monitored and compared with each other using a graphics based computer simulator called SIM-PORT.
An Arabic programming environment
Authors: Al-Salman AbdulMalik S.
Published: November 2005

This work presents the interface design of an Arabic Programming Environment (APE). The environment is an attempt to Arabize the user interface for programming languages under MS-Windows. It consists of two interrelated parts. The first part is the Arabic environment that enables users to create and edit programs in Arabic. The second part is the Arabic compiler. This paper describes only the first part of this project. It also states the main characteristics of the Arabic language that affects this work.
Dynamic information visualization
Authors: Ioannidis Yannis E.
Published: November 2005

Dynamic queries
constitute a very powerful mechanism for information visualization; some universe of data is visualized, and this visualization is modified on-the-fly as users modify the range of interest within the domains of the various attributes of the visualized information. In this paper, we analyze dynamic queries and offer some natural generalizations of the original concept by establishing a connection to SQL. We also discuss some implementation ideas that should make these generalizations efficient as well.
A framework for information visualisation
Authors: Kennedy Jessie B. , Mitchell Kenneth J. , Barclay Peter J.
Published: November 2005

In this paper we examine the issues involved in developing information visualisation systems and present a framework for their construction. The framework addresses the components which must be considered in providing effective visualisations. The framework is specified using a declarative object oriented language; the resulting object model may be mapped to a variety of graphical user interface development platforms. This provides general support to developers of visualisation systems. A prototype system exists which allows the investigation of alternative visualisations for a range of data sources.
Pixel-oriented database visualizations
Authors: Keim Daniel A.
Published: November 2005

In this paper, we provide an overview of several pixel-oriented visualization techniques which have been developed over the last years to support an effective querying and exploration of large databases. Pixel-oriented techniques use each pixel of the display to visualize one data value and therefore allow the visualization of the largest amount of data possible. The techniques may be divided into query-independent techniques which directly visualize the data (or a certain portion of it) and query-dependent techniques which visualize the relevance of the data with respect to a specific query. An example for the class of query-independent techniques is the recursive pattern technique which is based on a generic recursive scheme generalizing a wide range of pixel-oriented arrangements for visualizing large databases. Examples for the class of query-dependent techniques are the generalized spiral and circle-segments techniques, which visualize the distance with respect to a database query and arrange the most relevant data items in the center of the display.
New programs at DARPA and NSF
Authors: Qian Xiolai
Published: November 2005

We will share with readers some good news on NSF and Defense budget, and report on several interesting new programs at DARPA and NSF.
More commentary on missing information in relational databases (applicable and inapplicable information)
Authors: Codd E F
Published: November 2005

My earlier paper TRI/EFC-4 from The Relational Institute on this subject was published in ACM SIGMOD Record, December 1986. As a result, I have received several comments and proposed changes. The purpose of this paper is to respond to these items, while continuing to place heavy emphasis on the semantic aspects of missing information. The response is principally further explanation, but a few changes of a quite minor character are proposed. In this paper the reader is assumed to have read TRI/EFC-4.