bluuebunny/crossref_metadata_2025 huggingface dataset:
Efficiently updating materialized views
Authors: Blakeley Jose A. , Larson Per-Ake , Tompa Frank Wm
Published: November 2005

Query processing can be sped up by keeping frequently accessed users' views materialized. However, the need to access base relations in response to queries can be avoided only if the materialized view is adequately maintained. We propose a method in which all database updates to base relations are first filtered to remove from consideration those that cannot possibly affect the view. The conditions given for the detection of updates of this type, called
irrelevant updates
, are necessary and sufficient and are independent of the database state. For the remaining database updates, a
differential
algorithm can be applied to re-evaluate the view expression. The algorithm proposed exploits the knowledge provided by both the view definition expression and the database update operations.
Abstraction in recovery management
Authors: Moss J. Eliot B , Griffeth Nancy D. , Graham Marc H.
Published: November 2005

There are many examples of actions on abstract data types which can be correctly implemented with nonserializable and nonrecoverable schedules of reads and writes. We examine a model of multiple layers of abstraction that explains this phenomenon and suggests an approach to building layered systems with transaction oriented synchronization and roll back. Our model may make it easier to provide the high data integrity of reliable database transaction processing in a broader class of information systems. We concentrate on the recovery aspects here, a technical report [Moss et al 85] has a more complete discussion of concurrency control.
R* optimizer validation and performance evaluation for local queries
Authors: Mackert Lothar F. , Lohman Guy M.
Published: November 2005

Few database query optimizer models have been validated against actual performance. This paper presents the methodology and results of a thorough validation of the optimizer and evaluation of the performance of the experimental distributed relational database management system R
*
, which inherited and extended to a distributed environment the optimization algorithms of System R. Optimizer estimated costs and actual R
*
resources consumed were written to database tables using new SQL commands, permitting automated control from SQL application programs of test data collection and reduction. A number of tests were run over a wide variety of dynamically-created test databases, SQL queries, and system parameters. The results for single-table access, sorting, and local 2-table joins are reported here. The tests confirmed the accuracy of the majority of the I/O cost model, the significant contribution of CPU cost to total cost, and the need to model CPU cost in more detail than was done in System R. The R
*
optimizer now retains cost components separately and estimates the number of CPU instructions, including those for applying different kinds of predicates. The sensitivity of I/O cost to buffer space motivated the development of more detailed models of buffer utilization unclustered index scans and nested-loop joins often benefit from pages remaining in the buffers, whereas concurrent scans of the data pages and the index pages for multiple tables during joins compete for buffer share. Without an index on the join column of the inner table, the optimizer correctly avoids the nested-loop join, confirming the need for merge-scan joins. When the join column of the inner is indexed, the optimizer overestimates the cost of the nested-loop join, whose actual performance is very sensitive to three parameters that are extremely difficult to estimate (1) the join (result) cardinality, (2) the outer table's cardinality, and (3) the number of buffer pages available to store the inner table. Suggestions are given for improved database statistics, prefetch and page replacement strategies for the buffer manager, and the use of temporary indexes and Bloom filters (hashed semijoins) to reduce access of unneeded data.
Load balancing in a locally distributed DB system
Authors: Carey Michael J. , Lu Hongjun
Published: November 2005

Most previous work on query optimization in distributed database systems has focused on finding optimal or near-optimal processing plans based solely on static system characteristics, and few researchers have addressed the problem of copy selection when data is replicated. This paper describes a new approach to query processing for locally distributed database systems. Our approach uses load information to select the processing site(s) for a query, dynamically choosing from among those sites that have copies of relations referenced by the query. Query compilation is used to produce a statically-optimized
logical plan
for the query, and then a dynamic optimization phase converts this logical plan into an executable
physical plan
at runtime. This paper motivates the separation of static and dynamic optimization, presents algorithms for the various phases of the optimization process, and describes a simulation study that was undertaken to investigate the performance of this approach. Our simulation results indicate that load-balanced query processing can provide improvements in both query response times and overall system throughput as compared to schemes where execution sites are either statistically or randomly selected.
Principles of an icons-based language
Authors: Frasson C. , Er-radi M.
Published: November 2005

Improvements both in technology and in user-oriented software have shown the feasibility of new kinds of non-procedural languages. However, interaction between end-user and data should rely more and more on graphical languages and, particularly, on 'iconic” languages. In the following we review and analyze the forces which are at the origin of changes in the user environment. We give the main specifications of an iconic interface and a command language based on icons. Examples are given in a medical environment.
Traversal recursion: a practical approach to supporting recursive applications
Authors: Rosenthal Arnon , Heiler Sandra , Dayal Umeshwar , Manola Frank
Published: November 2005

Many capabilities that are needed for recursive applications in engineering and project management are not well supported by the usual formulations of recursion. We identify a class of recursions called “traversal recursions” (which model traversals of a directed graph) that have two important properties they can supply the necessary capabilities and efficient processing algorithms have been defined for them. First we present a taxonomy of traversal recursions based on properties of the recursion on graph structure and on unusual types of metadata. This taxonomy is exploited to identify solvable recursions and to select an execution algorithm. We show how graph traversal can sometimes outperform the more general iteration algorithm. Finally we show how a conventional query optimizer architecture can be extended to handle recursive queries and views.
Evaluation of database recursive logic programs as recurrent function series
Authors: Gardarin Georges , de Maindreville Christophe
Published: November 2005

The authors introduce a new method to compile queries referencing recursively defined predicates. This method is based on an interpretation of the query and the relations as functions which map one column of a relation to another column. It is shown that a large class of queries with associated recursive rules, including mutually recursive rules, can be computed as the limit of a series of functions. Typical cases of series of functions are given and solved. The solutions lend themselves towards either extended relational algebra or SQL optimized programs to compute the recursive query answers. Examples of applications are given.
Panel: Extensible database systems
Authors: Batory D. S. , Mannino M.
Published: November 2005

New implementation techniques and new capabilities for database systems are being developed and proposed at a rapid rate. Novel file structures and improved algorithms for query optimization, buffer and recovery management, and transaction management have the potential of realizing significant gains in DBMS performance. The proposed integration of design objects, voice, text, rules, vector graphics, and images into databases promises exciting new capabilities for DBMSs. To accommodate advances in database technology and to support new classes of database applications, DBMSs must be extensible (i.e., customizable).

To achieve extensibility forces a fundamental rethinking about how DBMSs are built, and how special-purpose features can be integrated into a DBMS with little effort and expense. Customizing DBMSs implies the availability of extensible data models, to allow for the introduction of new object types and operations, and extensible storage structures, to take advantage of special properties of stored data or operations to enhance performance.

Although research on extensible DBMSs is still in its infancy, a fundamental concept underlying their construction is now evident. This is the standardization of interfaces and the plug-compatibility of modules. An extensible DBMS will be a 'software bus' whereby new modules (and hence new DBMS capabilities) can be added, exchanged, or removed by plugging or unplugging modules. Extensible DBMSs will thus rely on extensive software libraries, where new modules can be added as needed. Furthermore, changes to DBMSs can be made in months rather than years, and the reinvention of established technology is kept to a minimum because of the reusability of modules.

The perception of DBMSs as monolithic entities that are difficult to modify will change as extensible DBMS technology becomes better understood. The use of database systems will not change, the ANSI/SPARC roles of database users, who write and execute transactions, and the database administrator (DBA), who designs and writes database schemas, will remain. Extensible DBMSs will require the introduction of an additional party, the
database architecture administrator (DDA)
, who is responsible for the construction and customization of a DBMS.

A growing number of researchers are developing extensible DBMSs. The purpose of this panel is to explain and discuss some of the approaches that are now being taken (and those that can be taken), and to survey the problems that confront extensible database technology. Descriptions of the systems and research represented at this panel are given in the following sections.
Global query optimization
Authors: Sellis Timos K.
Published: November 2005

In some recently proposed extensions to relational database systems as well as in deductive databases, a database system is presented with a collection of queries to process instead of just one. It is an interesting problem then, to come up with algorithms that process these queries together instead of one query at a time. We examine the problem of multiple (global) query optimization in this paper. A hierarchy of algorithms that can be used for global query optimization is exhibited and analyzed. These algorithms range from an arbitrary serial execution without any sharing of common results among the queries to an exhaustive search of all possible ways to process all queries.
Rule-based transformation of relational queries into iterative programs
Authors: Freytag Johann Christoph , Goodman Nathan
Published: November 2005

Over the last decade many techniques for optimizing relational queries have been developed. However, the problem of translating these set-oriented query specifications into other forms for efficient execution has received little attention.

This paper presents an algorithm that translates algebra-based query specifications into iterative programs for an efficient execution. While the source level operates on sets of tuples, the generated programs manipulate tuples as their basic objects. The algorithm incorporates techniques which have been developed in the areas of functional programming and program transformation.
Multiattribute hashing using Gray codes
Authors: Faloutsos Christos
Published: November 2005

Multiattribute hashing and its variations have been proposed for partial match and range queries in the past. The main idea is that each record yields a bitstring @@@@ (“record signature”), according to the values of its attributes. The binary value (@@@@)
2
of this string decides the bucket that the record is stored. In this paper we propose to use Gray codes instead of binary codes, in order to map record signatures to buckets. In Gray codes, successive codewords differ in the value of exactly one bit position, thus, successive buckets hold records with similar record signatures. The proposed method achieves better clustering of similar records and avoids some of the (expensive) random disk accesses, replacing them with sequential ones. We develop a mathematical model, derive formulas giving the average performance of both methods and show that the proposed method achieves 0% - 50% relative savings over the binary codes. We also discuss how Gray codes could be applied to some retrieval methods designed for range queries, such as the grid file [Nievergelt84a] and the approach based on the so-called
z
-ordering [Orenstein84a].
Good worst-case algorithms for inserting and deleting records in dense sequential files
Authors: Willard Dan E.
Published: November 2005

Consider a file which arranges records in sequential order, and stores them with possible empty spaces in M consecutive pages of memory. We develop an insertion-deletion algorithm which runs in a worst-case time approximately proportional to log
2
M divided by the page-size when the set of manipulated records has cardinality O(M).
Query processing in deductive databases with incomplete information
Authors: Imielinski Tomasz
Published: November 2005

We study here automated deduction in databases in the presence of various types of inference rules of the form of Horn Clauses with Skolem functions. These inference rules are typical for databases with incomplete information. We demonstrate a number of results related to processing of conjunctive queries for different types of database intensions. In particular, we show that when a database intension is built from possibly cyclic inclusion dependencies and view definitions any conjunctive query can be translated to the an equivalent form which can be evaluated directly over the database extension (disregarding inference rules). We also demonstrate that the complexity of query processing significantly grows when we mix incomplete information with recursive rules. In particular, we demonstrate here that even the power of least fixpoint extension of first order logic may be not sufficient to process queries in the presence of incomplete data and recursive rules. The same is demonstrated in case disjunctive information is allowed in the database.
An object-oriented approach to multimedia databases
Authors: Woelk Darrell , Kim Won , Luther Willis
Published: November 2005

This paper identifies data modelling and data access and sharing requirements which multimedia applications impose on a database system. It shows the capabilities of an object-based data model and indicates extensions which are needed to meet the data modelling aspects of these requirements. A logical implementation of the operations on the model is described. The model generalizes the notions of instantiation and generalization in the standard object-oriented paradigm, and augments it with the notions of aggregation and relationships which are specialized for a multimedia application environment. Objects may exist in aggregation hierarchies which provide the capability to integrate diverse types of multimedia information such as text, sound, bit-mapped images, and complex graphics drawings. Objects may also be linked through other user-defined relationships to capture such application functions as voice annotation and referencing of one document by another. Using this model, the semantics of aggregation and relationships in a multimedia application environment can be understood and efficiently supported by a database system.
Spatial query processing in an object-oriented database system
Authors: Orenstein Jack A.
Published: November 2005

DBMSs must offer spatial query processing capabilities to meet the needs of applications such as cartography, geographic information processing and CAD. Many data structures and algorithms that process grid representations of spatial data have appeared in the literature. We unify much of this work by identifying common principles and distilling them into a small set of constructs. (Published data structures and algorithms can be derived as special cases.) We show how these constructs can be supported with only minor modifications to current DBMS implementations. The ideas are demonstrated in the context of the range query problem. Analytical and experimental evidence indicates that performance of the derived solution is very good (e.g., comparable to performance of the kd tree.)
A DBMS prototype to support extended NF2 relations: an integrated view on flat tables and hierarchies
Authors: Dadam P. , Kuespert K. , Andersen F. , Blanken H. , Erbe R.
Published: November 2005

Recently, extensions for relational database management systems (DBMS) have been proposed to support also hierarchical structures (complex objects). These extensions have been mainly implemented on top of an existing DBMS. Such an approach leads to many disadvantages not only from the conceptual point of view but also from performance aspects. Thus paper reports on a 3-year effort to design and prototype a DBMS to support a generalized relational data model, called extended NF
2
(
N
on
F
irst
N
ormal
F
orm) data model which treats flat relations, lists, and hierarchical structures in a uniform way. The logical data model, a language for this model, and alternatives for storage structures to implement generalized relations are presented and discussed.
On the evaluation strategy of EDUCE
Authors: Bocca Jorge
Published: November 2005

Educe is a logic programming system for handling large knowledge bases. It was constructed by fully integrating the logic programming language Prolog and the relational data base management system Ingres. Educe uses a hybrid strategy for the evaluation of queries. This strategy is based on two contrasting strategies. The strategy known as
sets retrieval
, transforms recursive and non-recursive queries into a form suitable for evaluation by a relational data base management system. The other strategy, known as
one-tuple-at-a time
, evaluates queries by imitating the evaluation strategy of the programming language Prolog. In earlier versions of Educe, users selected the strategy by using two different query languages. In order to remove this responsibility from the user, algorithms to map expressions from either of the languages into the other were implemented and added to Educe. This paper briefly reviews the implementation of both evaluators and the mappings compares the basic strategies of evaluation, and then proceeds to explain Educe's own strategy.
Version modeling concepts for computer-aided design databases
Authors: Katz Randy H. , Chang Ellis , Bhateja Rajiv
Published: November 2005

We describe a semantic object-oriented data model for representing how a complex design database evolves over time. Structural relationships, introduced by the data management system, are imposed on the objects created by existing CAD tools. The relationships supported by the model are (1) version histories, (2) time-varying configurations, and (3) equivalences among objects of different types. We describe mechanisms for (1) identifying current versions, (2) supporting dynamic configuration binding, and (3) verifying equivalence relationships. The data model is being implemented in a
Version Server
, under development at the University of California, Berkeley.
A formal view integration method
Authors: Biskup Joachim , Convent Bernhard
Published: November 2005

The design of an appropriate conceptual database scheme is one of the most difficult tasks in usual database applications. Especially, the design of a common global database scheme for many different user groups requires a great amount of effort and skill, because the desired scheme should fit a great variety of requirements and expectations. Here, view integration is a natural method that should help to manage the complexity of such a design problem. For each user group the requirements and expectations are separately collected and specified as views, that are subsequently integrated into a global scheme supporting all those different views.

In this paper, we carefully develop a formal model, clarifying many notions and concepts, related to the view integration method. This formal model serves as a theoretical basis of our integration approach that uses equivalence preserving, local scheme transformations as the main integration operations.
Methods and rules
Authors: Abiteboul Serge , Lausen Georg , Uphoff Heinz , Waller Emmanuel
Published: November 2005

We show how classical datalog semantics can be used directly and very simply to provide semantics to a syntactic extension of datalog with methods, classes, inheritance, overloading and late binding. Several approaches to resolution are considered, implemented in the model, and formally compared. They range from resolution in C
++
style to original kinds of resolution suggested by the declarative nature of the language. We show connections to view specification and a further extension allowing runtime derivation of the class hierarchy.
Local verification of global integrity constraints in distributed databases
Authors: Gupta Ashish , Widom Jennifer
Published: November 2005

We present an optimization for integrity constraint verification in distributed databases. The optimization allows a global constraint, i.e. a constraint spanning multiple databases, to be verified by accessing data at a single database, eliminating the cost of accessing remote data. The optimization is based on an algorithm that takes as input a global constraint and data to be inserted into a local database. The algorithm produces a local condition such that if the local data satisfies this condition then, based on the previous satisfaction of the global constraint, the global constraint is still satisfied. If the local data does not satisfy the condition, then a conventional global verification procedure is required.
Partially preemptible hash joins
Authors: Pang Hwee Hwa , Carey Michael J. , Livny Miron
Published: November 2005

With the advent of real-time and goal-oriented database systems, priority scheduling is likely to be an important feature in future database management systems. A consequence of priority scheduling is that a transaction may lose its buffers to higher-priority transactions, and may be given additional memory when transactions leave the system. Due to their heavy reliance on main memory, hash joins are especially vulnerable to fluctuations in memory availability. Previous studies have proposed modifications to the hash join algorithm to cope with these fluctuations, but the proposed algorithms have not been extensively evaluated or compared with each other. This paper contains a performance study of these algorithms. In addition, we introduce a family of memory-adaptive hash join algorithms that turns out to offer even better solutions to the memory fluctuation problem that hash joins experience.
On optimal processor allocation to support pipelined hash joins
Authors: Lo Ming-Ling , Chen Ming-Syan Syan , Ravishankar C. V. , Yu Philip S.
Published: November 2005

In this paper, we develop algorithms to achieve optimal processor allocation for pipelined hash joins in a multiprocessor-based database system. A pipeline of hash joins is composed of several stages, each of which is associated with one join operation. The whole pipeline is executed in two phases: (1) the table-building phase, and (2) the tuple-probing phase. We focus on the problem of allocating processors to the stages of a pipeline to minimize the query execution time. We formulate the processor allocation problem as a two-phase mini-max optimization problem, and develop three optimal allocation schemes under three different constraints. The effectiveness of our problem formulation and solution is verified through a detailed tuple-by-tuple simulation of pipelined hash joins. Our solution scheme is general and applicable to any optimal resource allocation problem formulated as a two-phase mini-max problem.
Using the co-existence approach to achieve combined functionality of object-oriented and relational systems
Authors: Ananthanarayanan R. , Gottemukkala V. , Kaefer W. , Lehman T. J. , Pirahesh H.
Published: November 2005

Once considered a novelty, object oriented systems have now entered the mainstream. Their impressive performance and rich type systems have created a demand for object oriented features in other areas, such as relational database systems. We believe the current efforts to combine object oriented and relational features into a single hybrid system will fall short of the mark, whereas our approach, the
co-existence
approach, has the distinction of requiring far less work, but at the same time promising both the desired functionality and performance. We describe the attributes of our co-existing systems, an object oriented system (C++) and a relational system (Starburst), and show how this combination supports the desired features of both object-oriented and relational systems.
Design and implementation of the glue-nail database system
Authors: Derr Marcia A. , Morishita Shinichi , Phipps Geoffrey
Published: November 2005

We describe the design and implementation of the Glue-Nail database system. The Nail language is a purely declarative query language; Glue is a procedural language used for non-query activities. The two languages combined are sufficient to write a complete application. Nail and Glue code both compile into the target language IGlue. The Nail compiler uses variants of the magic sets algorithm, and supports well-founded models. Static optimization is performed by the Glue compiler using techniques that include peephole methods and data flow analysis. The IGlue code is executed by the IGlue interpreter, which features a run-time adaptive optimizer. The three optimizers each deal with separate optimization domains, and experiments indicate that an effective synergism is achieved. The Glue-Nail system is largely complete and has been tested using a suite of representative applications.
Predicate migration
Authors: Hellerstein Joseph M. , Stonebraker Michael
Published: November 2005

The traditional focus of relational query optimization schemes has been on the choice of join methods and join orders. Restrictions have typically been handled in query optimizers by “predicate pushdown” rules, which apply restrictions in some random order before as many joins as possible. These rules work under the assumption that restriction is essentially a zero-time operation. However, today's extensible and object-oriented database systems allow users to define time-consuming functions, which may be used in a query's restriction and join predicates. Furthermore, SQL has long supported subquery predicates, which may be arbitrarily time-consuming to check. Thus restrictions should not be considered zero-time operations, and the model of query optimization must be enhanced.

In this paper we develop a theory for moving expensive predicates in a query plan so that the total cost of the plan — including the costs of both joins and restrictions — is minimal. We present an algorithm to implement the theory, as well as results of our implementation in POSTGRES. Our experience with the newly enhanced POSTGRES query optimizer demonstrates that correctly optimizing queries with expensive predicates often produces plans that are orders of magnitude faster than plans generated by a traditional query optimizer. The additional complexity of considering expensive predicates during optimization is found to be manageably small.
Experiences building the open OODB query optimizer
Authors: Blakeley José A. , McKenna William J. , Graefe Goetz
Published: November 2005

This paper reports our experiences building the query optimizer for TI's Open OODB system. To the best of our knowledge, it is the first working object query optimizer to be based on a complete extensible optimization framework including logical algebra, execution algorithms, property enforcers, logical transformation rules, implementation rules, and selectivity and cost estimation. Our algebra incorporates a new
materialize
operator with its corresponding logical transformation and implementation rules that enable the optimization of path expressions. Initial experiments on queries obtained from the object query optimization literature demonstrate that our optimizer is able to derive plans that are as efficient as, and often substantially more efficient than, the plans generated by other query optimization strategies. These experiments demonstrate that our initial choices for populating each part of our optimization framework are reasonable. Our experience also shows that having a complete optimization framework is crucial for two reasons. First, it allows the optimizer to discover plans that cannot be revealed by exploring only the alternatives provided by the logical algebra and its transformations. Second, it helps and forces the database system designer to consider all parts of the framework and to maintain a good balance of choices when incorporating a new logical operator, execution algorithm, transformation rule, or implementation rule. The Open OODB query optimizer was constructed using the Volcano Optimizer Generator, demonstrating that this second-generation optimizer generator enables rapid development of efficient and effective query optimizers for non-standard data models and systems.
Comparing rebuild algorithms for mirrored and RAID5 disk arrays
Authors: Hou Robert Y. , Patt Yale N.
Published: November 2005

Several disk array architectures have been proposed to provide high throughput for transaction processing applications. When a single disk in a redundant array fails, the array continues to operate, albeit in a degraded mode with a corresponding reduction in performance. In addition, the lost data must be rebuilt to a spare disk in a timely manner to reduce the probability of permanent data loss. Several researchers have proposed and examined algorithms for rebuilding the failed disk in a disk array with parity.

We examine the use of these algorithms to rebuild a mirrored disk array and compare the rebuild time and performance of the RAID5 and mirrored arrays. Redirection of Reads provides comparable average response times and better rebuild times than Piggybacking for a mirrored array, whereas these two algorithms perform similarly for a RAID5 array. In our experiments comparing the two architectures, a mirrored array has more disks than a RAID5 array and can sustain 150% more I/Os per second during the rebuild process. Even if the size of the RAID5 array is increased to match the mirrored array, the mirrored array reduces response times by up to 60% and rebuild times by up to 45%.
LH
Authors: Litwin Witold , Neimat Marie-Anne , Schneider Donovan A.
Published: November 2005

LH* generalizes Linear Hashing to parallel or distributed RAM and disk files. An LH* file can be created from objects provided by any number of distributed and autonomous clients. It can grow gracefully, one bucket at a time, to virtually any number of servers. The number of messages per insertion is one in general, and three in the worst case. The number of messages per retrieval is two in general, and four in the worst case. The load factor can be about constant, 65-95%, depending on the file parameters. The file can also support parallel operations. An LH* file can be much faster than a single site disk file, and/or can hold a much larger number of objects. It can be more efficient than any file with a centralized directory, or a static parallel or distributed hash file.
Lazy updates for distributed search structure
Authors: Johnson Theodore , Krishna Padmashree
Published: November 2005

Very large database systems require distributed storage, which means that they need distributed search structures for fast and efficient access to the data. In this paper, we present an approach to maintaining distributed data structures that uses
lazy updates
, which take advantage of the semantics of the search structure operations to allow for scalable and low-overhead replication. Lazy updates can be used to design distributed search structures that support very high levels of concurrency. The alternatives to lazy update algorithms (eager updates) use synchronization to ensure consistency, while lazy update algorithms avoid blocking. Since lazy updates avoid the use of synchronization, they are much easier to implement than eager update algorithms. We demonstrate the application of lazy updates to the dB-tree, which is a distributed
B
+
tree that replicates its interior nodes for highly parallel access. We develop a correctness theory for lazy updates so that our algorithms can be applied to other distributed search structures.
Algorithms for loading parallel grid files
Authors: Li Jianzhong , Rotem Doron , Srivastava Jaideep
Published: November 2005

The paper describes three fast loading algorithms for grid files on a parallel shared nothing architecture. The algorithms use dynamic programming and sampling to effectively partition the data file among the processors to achieve maximum parallelism in answering range queries. Each processor then constructs in parallel its own portion of the grid file. Analytical results and simulations are given for the three algorithms.
Towards a unified visual database access
Authors: Vadaparty K. , Aslandogan Y. A. , Ozsoyoglu G.
Published: November 2005

Since the development of QBE, over fifty visual query languages have been proposed to facilitate easy database access. Although these languages have introduced some very useful paradigms, a number of these have some severe limitations, such as: (a) not extending beyond the relational model (b) not considering negation and safety, formally (c) using
ad hoc
constructs, with no analysis of expressivity or complexity done, etc. Note that visual database access is an important issue being revisted, with the emergence of different flavors of object-oriented databases. We believe that there is a need for developing a unified visual query language.

Specifically, our goal is to develop a visual query language that has the following properties: (i) It has a few core constructs using which “expert-users” can define new (
derived
) constructs easily (ii) “Normal users” can use easily either the core or the derived constructs for database querying (iii) It can implement representative constructs of other (textual or visual) query language straightforwardly, and (iv) It has formal semantics, with its theoretical properties, such as complexity, analyzed.

We believe that we make a first step towards the above goal by introducing a new logical construct called restricted universal quantifier and combining it with the hierarchical structure of windows to develop a
V
isual
Q
uery
L
anguage, called
VQL.
The core constructs of
VQL
can encode easily a number of
representative
constructs of different (about six visual and four non-visual) relational, nested and object-oriented query languages. We also study the theoretical aspects such as safety, complexity, etc., of
VQL.
Interpreting a reconstructed relational calculus (extended abstract)
Authors: Watters Aaron
Published: November 2005

This paper describes a method for answering all relational calculus queries under the assumption that the domain of data values is sufficiently large. The method extends recent theoretical results that use extended relation representations to answer domain dependent queries, without the use of auxilliary variables or invented constants or an explicit enumeration of the active domain. The method is shown to be logically correct and to have polynomial data complexity. By identifying relational algebra operations with relational calculus queries this approach extends relational algebra to a full boolean algebra, where intersection, union, and difference are defined between any two relations, whether or not they are union compatible. An example illustrates that this approach can be useful in distributed query optimization.
Database system issues in nomadic computing
Authors: Alonso Rafael , Korth Henry F.
Published: November 2005

Mobile computers and wireless networks are emerging technologies that will soon be available to a wide variety of computer users. Unlike earlier generations of laptop computers, the new generation of mobile computers can be an integrated part of a distributed computing environment, one in which users change physical location frequently. The result is a new computing paradigm,
nomadic computing
. This paradigm will affect the design of much of our current systems software, including that of database systems.

This paper discusses in some detail the impact of nomadic computing on a number of traditional database system concepts. In particular, we point out how the reliance on short-lived batteries changes the cost assumptions underlying query processing. In these systems, power consumption competes with resource utilization in the definition of cost metrics. We also discuss how the likelihood of temporary disconnection forces consideration of alternative transaction processing protocols. The limited screen space of mobile computers along with the advent of pen-based computing provides new opportunities and new constraints on database interfaces and languages. Lastly, we believe that the movement of computers and data among networks potentially belonging to distinct, autonomous organizations creates serious security problems.
Incremental database systems
Authors: Zdonik Stanley B.
Published: November 2005

This paper discusses a new approach to database management systems that is better suited to a wide class of new applications such as scientific, hypermedia, and financial applications. These applications are characterized by their need to store large amounts of raw, unstructured data. Our premise is that, in these situations, database systems need a way to store data without imposing a schema, and a way to provide a schema incrementally as we process the data. This requires that the raw data be mapped in complex ways to an evolving schema.
Issues in multimedia databases
Authors: Jagadish H. V.
Published: November 2005

Multimedia is a popular term these days, and the database community, naturally, is talking about multimedia databases. The reason multimedia is getting so much attention is clear: technology trends are now beginning to make it possible to store and display, at a reasonable price, audio and still images through a computer. It is expected that video storage will also be affordable in the near future. The purpose of this panel is to explore what new challenges this multimedia explosion brings to the database community.
Intelligent integration of information
Authors: Wiederhold Gio
Published: November 2005

This paper describes and classifies methods to transform data to information in a three-layer, mediated architecture. The layers can be characterized from the top down as information-consuming applications, mediators which perform intelligent integration of information (I3), and data, knowledge and simulation resources.

The objective of modules in the I3 architecture is to provide end users' apoplications with information obtained through selection, abstraction, fusion, caching, extrapolation, and pruning of data. The data is obtained from many diverse and heterogeneous sources. The I3 objective requires the establishment of a consensual information system architecture, so that many participants and technologies can contribute. An attempt to provide such a range of services within a single, tightly integrated system is unlikely to survive technological or environmental change.

This paper focuses on the computational models needed to support the mediating functions in this architecture and introduces initial applicatiions. The architecture has been motivated in [Wied:92C].
A deductive and object-oriented database system
Authors: Vieille Laurent
Published: November 2005

This talk will outline the
principles, the architecture and the potential target applications
of a Deductive and Object-Oriented Database System (DOOD). Such systems combine the novel functionalities (relying on the associated technology) developed in deductive database projects, the ability to manipulate the complex objects appearing in many applications and the architectural advances achieved by Object-Oriented DBMS's.
The Miro DBMS
Authors: Stonebraker Michael
Published: November 2005

This short paper explains the key object-relational (OR) DBMS technology used by the Miro DBMS.
Single logical view over enterprise-wide distributed databases
Authors: Wade Andrew E.
Published: November 2005

Two trends in today's corporate world demand distribution: downsizing from centralized mainframe single database environments; and wider integration, connecting finance, engineering, manufacturing information systems for enterprise-wide modeling and operations optimization. The resulting environment consists of multiple databases, at the group level, department level, and corporate level, with the need to manage dependencies among data in all of them. The solution is full distribution, providing a single logical view to objects anywhere, from anywhere. Users see a logical model of objects connected to objects, with atomic transactions and propagating methods, even if composite objects are split among multiple databases, each under separate administrative control, on multiple, heterogeneous platforms, operating systems, and network protocols. Support for production environments includes multiple schemas, which may be shared among databases, private, or encrypted, dynamic addition of schemas, and schema evolution. Finally, the logical view must remain valid, and applications must continue to work, as the mapping to the physical environment changes, moving objects and databases to new platforms.
Concurrency control and recovery of multidatabase work flows in telecommunication applications
Authors: Jin W. Woody , Rusinkiewicz Marek , Ness Linda , Sheth Amit
Published: November 2005

In a research and technology application project at Bellcore, we used multidatabase transactions to model multisystem work flows of telecommunication applications. During the project a prototype scheduler for executing multi-database transactions was developed. Two of the issues addressed in this project were concurrent execution of multi-database transactions and their failure recovery. This paper discusses our use of properties of the application and the telecommunication systems to develop simple and efficient solutions to the concurrency control and recovery problems.
Architecture of the Encina distributed transaction processing family
Authors: Sherman Mark
Published: November 2005

This paper discusses how the Encina® family of distributed transaction processing software can be used to build reliable, distributed applications. We start with the toolkit components of Encina and how they are used for implementing ACID properties. We then consider how the toolkit can be applied in building higher level components in a DCE environment. We conclude with a discussion of the Encina Monitor, which provides a framework for organizing a collection of machines and servers.
Replicated data in a distributed environment
Authors: Colton Malcolm
Published: November 2005

Replication Server is a forthcoming Sybase product that dynamically maintains subsets of data in a distributed environment, providing several transaction models to maintain loose consistency. Replication Server is constrasted with existing products which provide location-transparent reads and high-consistency coordinated commits Replication Server makes it possible to build systems that are much more robust in the face of system component failures. By moving transactions rather than data, and by locating data at the point of processing, it maximizes the use of network bandwidth, enabling the deployment of robust, high-performance applications at a lower cost than with traditional approaches.
Interoperability using APPC
Authors: Mukhopadhyay Debajyoti
Published: November 2005

The complex and competitive business world of today needs to access data for various operations from different systems placed at different geographical locations. In order to fulfil this need, one should have a reliable distributed computing environment. Various components of that environment may be supplied by different vendors. This means that the computing environment not only needs to be distributed but also requires interoperability. Today, Interoperability is no more just an idea but a reality. There is also a growing need to support interactions among various systems in a dialog mode. Integrating distributed systems can only help to achieve the goal of developing a reliable distributed computing environment. In this paper, a conceptual framework for an architecture is described in conjunction with Advanced Program-to-Program Communications LU 6.2 protocol to handle that challenge. This architecture discusses the required contracting services for integrating distributed systems. This contracting service has three major components: the contract interaction services, the contract support services, and the communications infrastructure services.
Task scheduling using intertask dependencies in Carnot
Authors: Woelk Darrell , Attie Paul , Cannata Phil , Meredith Greg , Sheth Amit , Singh Munindar , Tomlinson Christine
Published: November 2005

The Carnot Project at MCC is addressing the problem of logically unifying physically-distributed, enterprise-wide, heterogeneous information. Carnot will provide a user with the means to navigate information efficiently and transparently, to update that information consistently, and to write applications easily for large, heterogeneous, distributed information systems. A prototype has been implemented which provides services for (a) enterprise modeling and model integration to create an enterprise-wide view, (b) semantic expansion of queries on the view to queries on individual resources, and (c) inter-resource consistency management. This paper describes the Carnot approach to transaction processing in environments where heterogeneous, distributed, and autonomous systems are required to coordinate the update of the local information under their control. In this approach, subtransactions are represented as a set of tasks and a set of intertask dependencies that capture the semantics of a particular relaxed transaction model. A scheduler has been implemented which schedules the execution of these tasks in the Carnot environment so that all intertask dependencies are satisfied.
Modeling battlefield sensor environments with an object database management system
Authors: Woyna Mark A. , Christiansen John H. , Hield Christopher W. , Simunich Kathy Lee
Published: November 2005

The Visual Intelligence and Electronic Warfare Simulation (VIEWS) Workbench software system has been developed by Argonne National Laboratory (ANL) to enable Army intelligence and electronic warfare (IEW) analysts at Unix workstations to conveniently build detailed IEW battlefield scenarios, or “sensor environments”, to drive the Army's high-resolution IEW sensor performance models. VIEWS is fully object-oriented, including the underlying database.
Persistence software
Authors: Keller Arthur M. , Jensen Richard , Agarwal Shailesh
Published: November 2005

Building object-oriented applications which access relational data introduces a number of technical issues for developers who are making the transition to C++. We describe these issues and discuss how we have addressed them in Persistence, an application development tool that uses an automatic code generator to merge C++ applications with relational data. We use client-side caching to provide the application program with efficient access to the data.