bluuebunny/crossref_metadata_2025 huggingface dataset:
Information management directions: the integration challenge
Authors: Fong E. N. , Goldfine A. H.
Published: November 2005

On October 31 - November 2, 1988, the National Computer Systems Laboratory of the National Institute of Standards and Technology, formerly the National Bureau of Standards, in cooperation with the Association for Computing Machinery Special Interest Group on Management of Data, the IEEE Computer Society Technical Committee on Database Engineering, and the Federal Data Management Users Group, held the fifth in the series of Information Management Directions (formerly called Data Base Directions) workshops. The purpose of these workshops is to examine in depth key trends and strategies that affect the future of the information management profession. The focus of Workshop 5 was on issues related to integration and productivity.

The complete workshop report, INFORMATION MANAGEMENT DIRECTIONS: THE INTEGRATION CHALLENGE, has been published by the National Institute of Standards and Technology as Special Publication 500-167, and can be ordered from the Superintendent of Documents, U.S. Government Printing Office, Washington, DC 20402.
Closing the key loophole in MLS databases
Authors: Jukic Nenad , Nestorov Svetlozar , Vrbsky Susan
Published: November 2005

There has been an abundance of research within the last couple of decades in the area of multilevel secure (MLS) databases. Recent work in this field deals with the processing of multilevel transactions, expanding the logic of MLS query languages, and utilizing MLS principles within the realm of E-Business. However, there is a basic flaw within the MLS logic, which obstructs the handling of clearance-invariant aggregate queries and physical-entity related queries where some of the information in the database may be gleaned from the outside world. This flaw stands in the way of a more pervasive adoption of MLS models by the developers of practical applications. This paper clearly identifies the cause of this impediment -- the cover story dependence on the value of a user-defined key -- and proposes a practical solution.
Towards a database body of knowledge
Authors: Calero Coral , Piattini Mario , Ruiz Francisco
Published: November 2005

Databases, the center of today's information systems, are becoming more and more important judging by the huge volume of business they generate. In fact, database related material is included in a variety of curricula proposed by international organizations and prestigious universities. However, a systemized database body of knowledge (DBBOK), analogous to other works in Software Engineering (SWEBOK) or in Project Management (PMBOK) is needed. In this paper, we propose a first draft for this DBBOK based on degree programs from a variety of universities, the most relevant international curricula and the contents of the latest editions of principle books on databases.
Time management for new faculty
Authors: Ailamaki Anastassia , Gehrke Johannes
Published: November 2005

In this article, we describe techniques for time management for new faculty members, covering a wide range of topics ranging from advice on scheduling meetings, email, to writing grant proposals and teaching.
Practical selectivity estimation through adaptive sampling
Authors: Lipton Richard J. , Naughton Jeffrey F. , Schneider Donovan A.
Published: November 2005

Recently we have proposed an adaptive, random sampling algorithm for general query size estimation. In earlier work we analyzed the asymptotic efficiency and accuracy of the algorithm, in this paper we investigate its practicality as applied to selects and joins. First, we extend our previous analysis to provide significantly improved bounds on the amount of sampling necessary for a given level of accuracy. Next, we provide “sanity bounds” to deal with queries for which the underlying data is extremely skewed or the query result is very small. Finally, we report on the performance of the estimation algorithm as implemented in a host language on a commercial relational system. The results are encouraging, even with this loose coupling between the estimation algorithm and the DBMS.
IDLOG: extending the expressive power of deductive database languages
Authors: Shen Yeh-Heng
Published: November 2005

The expressive power of pure deductive database languages, such as
DATALOG
and
stratified DATALOGS
, is limited in a sense that some useful queries such as functions involving
aggregation
are not definable in these languages. Our concern in this paper is to provide a uniform logic framework for deductive databases with greater expressive power. It has been shown that with a linear ordering on the domain of the database, the expressive power of some database languages can be enhanced so that some functions involving aggregation can be defined. Yet, a direct implementation of the linear ordering in deductive database languages may seem unintuitive, and may not be very efficient to use in practice. We propose a logic for deductive databases which employs the notion of “identifying each tuple in a relation”. Through the use of these
tuple-identifications
, different linear orderings are defined as a result. This intuitively explains the reason why our logic has greater expressive power. The proposed logic language is
non-deterministu
in nature. However, non-determinism is not the real reason for the enhanced expressive power. A deterministic subset of the programs in this language is
computational complete
in the sense that it defines all the
computable deterministic queries
. Although the problem of deciding whether a program is in this subset is in general undecidable, we do provide a rather general sufficient test for identifying such programs. Also discussed in this paper is an extended notion of queries which allows both the input and the output of a query to contain
interpreted constants
of an infinite domain. We show that extended queries involving aggregation can also be defined in the language.
Hard problems for simple logic programs
Authors: Saraiya Yatin P.
Published: November 2005

A number of optimizations have been proposed for Datalog programs involving a single intensional predicate (“single-IDB programs”). Examples include the detection of
commutativity
and
separability
([Naug88],[RSUV89], [Ioan89a]) in linear logic programs, and the detection of
ZYT-linearizability
([ZYT88], [RSUV89], [Sara89], [Sara90]) in nonlinear programs. We show that the natural generalizations of the commutativity and ZYT-linearizability problems (respectively, the
sequencability
and
base-case linearizability
problems) are undecidable. Our constructions involve the simulation of context-free grammars using single-IDB programs that have a bounded number of initialisation rules. The constructions may be used to show that containment (or equivalence) is undecidable for such programs, even if the programs are linear, or if each program contains a single recursive rule. These results tighten those of [Shmu87] and [Abit89].
Efficient updates to independent schemes in the weak instance model
Authors: Atzeni Paolo , Torlone Riccardo
Published: November 2005

The weak instance model is a framework to consider the relations in a database as a whole, regardless of the way attributes are grouped in the individual relations. Queries and updates can be performed involving any set of attributes. The management of updates is based on a lattice structure on the set of legal states, and inconsistencies and ambiguities can arise

In the general case, the test for inconsistency and determinism may involve the application of the chase algorithm to the whole database. In this paper it is shown how, for the highly significant class of independent schemes, updates can be handled efficiently, considering only the relevant portion of the database
.
FastSort: a distributed single-input single-output external sort
Authors: Salzberg Betty , Tsukerman Alex , Gray Jim , Stuewart Michael , Uren Susan , Vaughan Bonnie
Published: November 2005

External single-input single-output sorts can use multiple processors each with a large tournament replacement-selection in memory, and each with private disks to sort an input stream in linear elapsed time. Of course, increased numbers of processors, memories, and disks are required as the input file size grows. This paper analyzes the algorithm and reports the performance of an implementation.
A new paradigm for parallel and distributed rule-processing
Authors: Wolfson Ouri , Ozeri Aya
Published: November 2005

This paper is concerned with the parallel evaluation of datalog rule programs, mainly by processors that are interconnected by a communication network. We introduce a paradigm, called data-reduction, for the parallel evaluation of a general datalog program. Several parallelization strategies discussed previously in [CW, GST, W, WS] are special cases of this paradigm. The paradigm parallelizes the evaluation by partitioning among the processors the instantiations of the rules. After presenting the paradigm, we discuss the following issues, that we see fundamental for parallelization strategies derived from the paradigm properties of the strategies that enable a reduction in the communication overhead, decomposability, load balancing, and application to programs with negation. We prove that decomposability, a concept introduced previously in [WS, CW], is undecidable.
A framework for the parallel processing of Datalog queries
Authors: Ganguly Sumit , Silberschatz Avi , Tsur Shalom
Published: November 2005

This paper presents several complementary methods for the parallel, bottom-up evaluation of Datalog queries. We introduce the notion of a
discriminating predicate
, based on hash functions, that partitions the computation between the processors in order to achieve parallelism. A parallelization scheme with the property of non-redundant computation (no duplication of computation by processors) is then studied in detail. The mapping of Datalog programs onto a network of processors, such that the results is a non-redundant computation, is also studied. The methods reported in this paper clearly demonstrate the trade-offs between redundancy and interprocessor-communication for this class of problems.
Performance evaluation of semantics-based multilevel concurrency control protocols
Authors: Badrinath B. R. , Ramamritham Krithi
Published: November 2005

For next generation information systems, concurrency control mechanisms are required to handle high level abstract operations and to meet high throughput demands. The currently available single level concurrency control mechanisms for
reads
and
writes
are inadequate for future complex information systems. In this paper, we will present a new
multilevel
concurrency protocol that uses a semantics-based notion of conflict, which is weaker than commutativity, called
recoverability
. Further, operations are scheduled according to
relative conflict
, a conflict notion based on the structure of operations.

Performance evaluation via extensive simulation studies show that with our multilevel concurrency control protocol, the performance improvement is significant when compared to that of a single level two-phase locking based concurrency control scheme or to that of a multilevel concurrency control scheme based on commutativity alone. Further, simulation studies show that our new multilevel concurrency control protocol performs better even with resource contention.
Querying database knowledge
Authors: Motro Amihai , Yuan Qiuhui
Published: November 2005

The role of database knowledge is usually limited to the evaluation of data queries. In this paper we argue that when this knowledge is of substantial volume and complexity, there is genuine need to query this repository of information. Moreover, since users of the database may not be able to distinguish between information that is data and information that is knowledge, access to knowledge and data should be provided with a single, coherent instrument. We provide an informal review of various kinds of knowledge queries, with possible syntax and semantics. We then formalize a framework of knowledge-rich databases, and a simple query language consisting of a pair of retrieve and describe statements. The retrieve statement is for querying the data (it corresponds to the basic retrieval statement of various knowledge-rich database systems). The describe statement is for querying the knowledge. Essentially, it inquires about the meaning of a concept under specified circumstances. We provide algorithms for evaluating sound and finite knowledge answers to describe queries, and we demonstrate them with examples.
Reliable transaction management in a multidatabase system
Authors: Breitbart Yuri , Silberschatz Avi , Thompson Glenn R.
Published: November 2005

A model of a multidatabase system is defined in which each local DBMS uses the two-phase locking protocol Locks are released by a global transaction only after the transaction commits or aborts at each local site. Failures may occur during the processing of transactions. We design a fault tolerant transaction management algorithm and recovery procedures that retain global database consistency. We also show that our algorithms ensure freedom from global deadlocks of any kind.
Randomized algorithms for optimizing large join queries
Authors: Ioannidis Y. E. , Kang Younkyung
Published: November 2005

Query optimization for relational database systems is a combinatorial optimization problem, which makes exhaustive search unacceptable as the query size grows. Randomized algorithms, such as Simulated Annealing (SA) and Iterative Improvement (II), are viable alternatives to exhaustive search. We have adapted these algorithms to the optimization of project-select-join queries. We have tested them on large queries of various types with different databases, concluding that in most cases SA identifies a lower cost access plan than II. To explain this result, we have studied the shape of the cost function over the solution space associated with such queries and we have conjectured that it resembles a 'cup' with relatively small variations at the bottom. This has inspired a new Two Phase Optimization algorithm, which is a combination of Simulated Annealing and Iterative Improvement. Experimental results show that Two Phase Optimization outperforms the original algorithms in terms of both output quality and running time.
Access support in object bases
Authors: Kemper Alfons , Moerkotte Guido
Published: November 2005

In this work
access support relations
are introduced as a means for optimizing query processing in object-oriented database systems. The general idea is to maintain redundant separate structures (disassociated from the object representation) to store object references that are frequently traversed in database queries. The proposed access support relation technique is no longer restricted to relate an object (tuple) to an atomic value (attribute value) as in conventional indexing. Rather, access support relations relate objects with each other and can span over reference chains which may contain collection-valued components in order to support queries involving path expressions. We present several alternative extensions of access support relations for a given path expression, the best of which has to be determined according to the application-specific database usage profile. An analytical cost model for access support relations and their application is developed. This analytical cost model is, in particular, used to determine the best access support relation extension and decomposition with respect to the specific database configuration and application profile.
Random sampling from hash files
Authors: Olken Frank , Rotem Doron , Xu Ping
Published: November 2005

In this paper we discuss simple random sampling from hash files on secondary storage. We consider both iterative and batch sampling algorithms from both static and dynamic hashing methods. The static methods considered are open addressing hash files and hash files with separate overflow chains. The dynamic hashing methods considered are Linear Hash files [Lit80] and Extendible Hash files [FNPS79]. We give the cost of sampling in terms of the cost of successfully searching a hash file and show how to exploit features of the dynamic hashing methods to improve sampling efficiency.
The INA: a simple query language with only attribute names
Authors: Blum Bruce I. , Semmel Ralph D.
Published: November 2005

Current query languages, such as SQL, assume that the user is familiar with the database schema including the attribute names, types, and relation associations. When a user has imperfect knowledge of this information (or when he balks at the data-processing orientation of the required statements), he normally asks an experienced analyst to perform his and hoc query. The Intelligent Navigational Assistant (INA) was developed for the U S Army as a prototype query tool that permits the users to specify requests using only domain terms familiar to them. Once a request is made, it is converted into SQL for processing
1,2

To facilitate query formulation, the INA supports an interface that allows the user to identify attributes without relation associations (i.e., treats the data model as a universal relation). Because an attribute may appear in many relations, one of the principal tasks of the INA is the determination of the appropriate relation bindings. To aid in the selection of terms, the INA maintains a user vocabulary and provides facilities for browsing the vocabulary and examining term definitions. Thus, the INA has two primary functions it provides an easy-to-use interface for query definition, and it converts a request into SQL.

The INA prototype has been implemented as a PC-resident knowledge-based system linked to a host-based DBMS. Its knowledge base is the logical schema of the target database, and the query transformation relies on the dependencies implicit in that schema. Supporting the knowledge-processing functions are the query definition interface, various tools to manage the target data model description, and facilities for communicating with other computers. The system was developed using TEDIUM@@@@,
3
and the user interface and query resolution mechanism are extensions of earlier work with Tequila
4
(which accessed the semantically-richer TEDIUM@@@@ data model)

Work on the INA began in 1987 and was terminated in 1988. The system was demonstrated as a prototype with an Army-supplied logical model consisting of approximately 40 relations and 200 attributes. After query definition, reformation, and user acceptance, the SQL queries were submitted to the mainframe for processing. In those tests, the INA often produced better queries than those manually coded by analysts. The INA currently is undergoing a beta test with a much larger database schema. Its algorithms are described in reference 5, and reference 3 contains details regarding its implementation and semantic data model. Current research includes the development of improved query resolution algorithms based on an enriched semantic data model
Learning about data integration challenges from day one
Authors: Halevy Alon Y.
Published: November 2005

I describe the format of the new version of an introductory database course that I taught at the University ofWashington inWinter, 2003. The key idea underlying the course is to expose the students to some of the challenges that arise when working with and integrating data from
multiple
database systems and applications.
Exposing undergraduate students to database system internals
Authors: Ailamaki Anastassia , Hellerstein Joseph M.
Published: November 2005

In Spring 2003, Joe Hellerstein at Berkeley and Natassa Ailamaki at CMU collaborated in designing and running parallel editions of an undergraduate database course that exposed students to developing code in the core of a ful-function database system. As part of this exercise, our course teams developed new programming projects based on the PostgreSQL open-source DBMS. This report describes our experience with this effort.
DBGlobe
Authors: Pitoura Evaggelia , Abiteboul Serge , Pfoser Dieter , Samaras George , Vazirgiannis Michalis
Published: November 2005

The challenge of peer-to-peer computing goes beyond simple file sharing. In the DBGlobe project, we view the multitude of peers carrying data and services as a superdatabase. Our goal is to develop a data management system for modeling, indexing and querying data hosted by such massively distributed, autonomous and possibly mobile peers. We employ a service-oriented approach, in that data are encapsulated in services. Direct querying of data is also supported by an XML-based query language. In this paper, we present our research results along the following topics: (a) infrastructure support, including mobile peers and the creation of context-dependent communities, (b) metadata management for services and peers, including location-dependent data, (c) filters for efficiently routing path queries on hierarchical data, and (d) querying using the AXML language that incorporates service calls inside XML documents.
Power efficient data gathering and aggregation in wireless sensor networks
Authors: Tan Hüseyin Özgür , Körpeoǧlu Ibrahim
Published: November 2005

Recent developments in processor, memory and radio technology have enabled wireless sensor networks which are deployed to collect useful information from an area of interest. The sensed data must be gathered and transmitted to a base station where it is further processed for end-user queries. Since the network consists of low-cost nodes with limited battery power, power efficient methods must be employed for data gathering and aggregation in order to achieve long network lifetimes.In an environment where in a round of communication each of the sensor nodes has data to send to a base station, it is important to minimize the total energy consumed by the system in a round so that the system lifetime is maximized. With the use of data fusion and aggregation techniques, while minimizing the total energy per round, if power consumption per node can be balanced as well, a near optimal data gathering and routing scheme can be achieved in terms of network lifetime.So far, besides the conventional protocol of direct transmission, two elegant protocols called LEACH and PEGASIS have been proposed to maximize the lifetime of a sensor network. In this paper, we propose two new algorithms under name PEDAP (Power Efficient Data gathering and Aggregation Protocol), which are near optimal minimum spanning tree based routing schemes, where one of them is the power-aware version of the other. Our simulation results show that our algorithms perform well both in systems where base station is far away from and where it is in the center of the field. PEDAP achieves between 4x to 20x improvement in network lifetime compared with LEACH, and about three times improvement compared with PEGASIS.
Implementation of character string pattern matching on a multiprocessor
Authors: Vineberg Maniel
Published: November 2005

An algorithm to do pattern matching, a basic character string operation, is presented. The Programmable Algorithm Machine (PAM), a proposed special-purpose computer which will feature multiple processing elements and operate efficiently over a wide class of applications, is described. It is shown that the multiple processing elements of the PAM allow concurrent execution of independent operations both in a special case of the pattern matching algorithm, where the string sizes (lengths) are known at compile time, and in the general case, where the sizes are not known.
Associative/parallel processors for searching very large textual data bases
Authors: Bird R. M. , Tu J. C. , Worthy R. M.
Published: November 2005

This paper describes an approach to solving a major problem in the information processing sciences— that of searching very large (5-50 billion characters) data bases of unstructured free-text for random queries within a reasonable time and at an affordable price.

The need by information specialists and knowledge workers for large, fast low-cost text and document retrieval systems is growing rapidly. Conventional approaches to the problem have usually depended upon expensive, general purpose computers, upon special pre-preprocessing of the textual data (e.g. file inverting, indexing, abstracting, etc.), and upon elaborate, costly software. The resulting retrieval systems often cost hundreds of dollars per query and the full scanning of an uninverted, unstructured billion byte textual data base could take hours of computer services. However, in spite of these restrictions, such full text search systems have proved useful and even indispensible for many applications.

Computer technology of the late 1960's and the 1970's, in both hardware and software (e.g., minicomputers, low-cost, high density disk storage, “chip” electronics, natural language query systems, etc.), have made i t practical to build special purpose, low-cost text retrieval systems. Such a system has been built, tested, and is now in a production stage. The system called the Associative File Processor (AFP), utilizes a conventional minicomputer (DEC's PDP-11/45) for control, off-the-shelf high density disks for storage, a special purpose parallel search module as a text term detector, and query and retrieval software. The AFP is currently being field tested at two sites. Full text, parallel searches on un-preprocessed textual data bases are being performed at the effective matching rates of 4 billion bytes per second (8K byte key memory times 500 Kbyte/second data stream). Estimated costs are 10 to 25 cents per query for a one billion byte data base. The costs per query and the time for searching increase in a linear fashion as data base increases. A basic architecture for the AFP is described and an implemented version is discussed. A more powerful term detector module is also under development. This system is designed around a finite state automaton algorithm.
On imaginary fields, token transfers and floating codes in intelligent secondary memories
Authors: Lipovski G. J.
Published: November 2005

In analyzing two implemented intelligent secondary memories, CASSM and RAP, we recognize a common mechanism which is here called an imaginary field. The mechanism can be generalized to suggest further design possibilities. It further explains the complex and controversial CASSM mechanism, “pointer transfer” in terms of separate but related principles—imaginary fields, token transfers, and floating codes—such that further designs can utilize some or all of the techniques.
The architecture of a database computer - a summary
Authors: Hsiao David K. , Kannan Krishnamurthi
Published: November 2005

The motivation for seeking hardware solutions to database management functions traditionally carried out by software has been apparent to data-base designers for sometime now. Firstly, database management software has grown in complexity and size over the years. This growth is prompted by the increase in user requirements, by the formulation of sophisticated models and by the change in data processing mode from an off-line, batched, single user environment to an on-line, concurrent and multi-user environment. Large and complex software systems tend to be failure-prone. Further-more, practical verification methods for software systems are still not in sight. On the other hand, methods for verifying hardware functionality, design and production have long been available. Advanced technology has also overcome some of the problems of the logic complexity and capacity requirements, making the construction of relatively large and complex computers viable. By incorporating basic database management functions into hardware, not only can we provide more reliable basic functions, but we can also improve the software reliability since the software requirements will be less complex and the system software will be smaller in size.
A comparison of sequential and associate computing of priority queues
Authors: Landson Barry M. , Sargent Robert G.
Published: November 2005

A comparison of priority queues on four different types of computer memories are made by ring a model to determine the total time to do comparable tasks. The four types of memories compared are random access (RAM), associate (AM), hybrid consisting of an associate memory and a random access memory (AM/RAM), and the hybrid memory with an auxiliary memory having the @@@@pability to perform Lewin's Associate algorithm @@@@], (AM/RAM/AML).

The model used for the comparisons is an extension of the MIX model developed by Knuth [1]. The MIX model was extended to include the four types of memories and the instruction set expanded include @@@@ instructions for the memories added. This @@del allows direct comparisons to be made of the different architectures and different software algorithms in performing the same tasks.
On merging partitioned databases
Authors: Wright David D.
Published: November 2005

Partitioning of a distributed data base requires either that update activity be restricted or that a strategy for conflict resolution and partition merging be used once communication is restored. The graph-theoretic approach used by Davidson follows the latter approach and can be used to show that finding an optimum solution to the general problem is NP-complete. We give several methods of reducing the size of the graphs involved. Two open subproblems are shown to be NP-complete, while an extension of a known polynomial-time subproblem is given. Simulation results are used to study both the amount of compression achieved by the graph reduction techniques and their effects on heuristics for the problem. In addition, some modifications are made to existing heuristics to improve their performance. A simple probabilistic model is developed and compared to the simulation results.
Fragments of relations
Authors: Maier David , Ullman Jeffrey D.
Published: November 2005

We develop a theory of relations that are constructed by the union and selection operations from fragment relations.
Algorithms for inserting and deleting from relations that are composed of physical fragments are
discussed, and we show when such insertions and deletions are meaningful. We also show how to find an access set for a relation, that is, a set of fragments sufficient to produce the relation, and we apply the test to the question of how the fragmentation of relations interacts with a query on the relation, showing that a selection on the relation can be implemented by retrieving a set of physical fragments that forms an access set for another particular relation.
Estimating block transfers and join sizes
Authors: Christodoulakis Stavros
Published: November 2005

In this paper we provide estimates of the number of sequential and random block accesses required for retrieving a number of records of a file when the distribution of records in blocks of secondary storage is not uniform. We show how these results apply to estimating sizes of joins and semi-joins. We prove that when the uniformity of placement assumption is not satisfied it often leads to pessimistic estimates of performance. Finally we show a recursive estimation of the probability distribution of the number of blocks containing a given number of records.
A new characterization of independence
Authors: Honeyman Peter , Sciore Edward
Published: November 2005

We introduce a restriction on the structure of a database scheme, called the
primary key condition,
and show that this condition characterizes independent database schemes when constraints are presented as keys. The primary key condition provides added insight into the structure of independent schemes, and leads to a general design methodology. We describe a linear-time algorithm for recognizing independent schemes.
Top-down statistical estimation on a database
Authors: Rowe Neil C.
Published: November 2005

The size of data sets subjected to statistical analysis is increasing as computer technology develops. Quick estimates of statistics rather than exact values are becoming increasingly important to analysts. We propose a new technique for estimating statistics on a database, a "top-down" alternative to the "bottom-up" method of sampling. This approach precomputes a set of general-purpose statistics on the database, a "database abstract", and then uses a large set of inference rules to make bounded estimates of other, arbitrary statistics requested by users. The inference rules form a new example of an artificial-intelligence "expert system". There are several important advantages of this approach over sampling methods.
Answering queries in relational databases
Authors: D'Atri Alessandro , Moscarini Marina , Spyratos Nicolas
Published: November 2005

This paper concerns query answering in relational databases. We assume a universe U of attributes and a set of values associated with each attribute. A database scheme is a given collection R = {1, 2, ..., n} of subsets of U, called relation schemes. A query in R is any subset of U. We call "context" any joinable subset of R. An unambiguous context is one in which a query receives the same answer independently of the subcontext used for the computation. A formal treatment of unambiguous contexts is presented and it is shown that they provide a suitable basis for discussing the universal relation assumption, the relationship uniqueness assumption, maximal objects, and other related concepts.
Designing globally consistent network schemas
Authors: Kuck Sharon M. , Sagiv Yehoshua
Published: November 2005

In this paper we address several problems relating to functional dependencies and network schemas. We investigate properties of the functional dependencies that are implicitly defined in a network schema. A definition for the satisfaction of functional dependencies by a network database is proposed, and then we give a sufficient condition for the global consistency of a network schema. A network schema is globally consistent if all its databases satisfy the functional dependencies that are implicitly defined in the schema. Finally, we describe a design methodology for producing a network schema whose set of implicitly defined functional dependencies implies a set of functional dependencies specified by the user.
Implementation techniques for main memory database systems
Authors: DeWitt David J , Katz Randy H , Olken Frank , Shapiro Leonard D , Stonebraker Michael R , Wood David A.
Published: November 2005

With the availability of very large, relatively inexpensive main memories, it is becoming possible keep large databases resident in main memory In this paper we consider the changes necessary to permit a relational database system to take advantage of large amounts of main memory We evaluate AVL vs B+-tree access methods for main memory databases, hash-based query processing strategies vs sort-merge, and study recovery issues when most or all of the database fits in main memory As expected, B+-trees are the preferred storage mechanism unless more than 80--90% of the database fits in main memory A somewhat surprising result is that hash based query processing strategies are advantageous for large memory situations
Design and implementation of an extendible integrity subsystem
Authors: Simon Eric , Valduriez Patrick
Published: November 2005

Tnls paper presents a powerful integrrty subsystem, which is implemented in the SABRE database system. The specification language is simple. Tne enforcement algorithm is general, in particular, it handles referential dependency and temporal assertions. Specialized strategies efficiently treat each class of assertions. The system automatically manages integrity checkpoints. Also, an efficient method is described for processing assertions involving aggregates. An analysis exhibits the value of the algorithms. It 1s shown that, in general, this method is better than the query modification method for domain assertions. Measures have also been done for giving the cost added for controlling integrity in comparison with the cost of the request itself.
Towards a self-adapting centralized concurrency control algorithm
Authors: Boral Haran , Gold Israel
Published: November 2005

We introduce the notion of self-adapting concurrency control algorithms --- concurrency control algorithms that consist of several rw and several ww synchronization techniques, and employ combinations of the techniques in a manner that attains a performance objective. We Consider synchronization techniques that use locking and certification. A general proof method for such algorithms is outlined and applied.
R-trees
Authors: Guttman Antonin
Published: November 2005

In order to handle spatial data efficiently, as required in computer aided design and geo-data applications, a database system needs an index mechanism that will help it retrieve data items quickly according to their spatial locations However, traditional indexing methods are not well suited to data objects of non-zero size located m multi-dimensional spaces In this paper we describe a dynamic index structure called an R-tree which meets this need, and give algorithms for searching and updating it. We present the results of a series of tests which indicate that the structure performs well, and conclude that it is useful for current database systems in spatial applications
Data management facilities of an operating system kernel
Authors: Diel Hans , Kreissig Gerald , Lenz Norbert , Scheible Michael , Schoener Bernd
Published: November 2005

The paper describes the part of a general operating system Kernel supporting data management functions The operating system Kernel can be imbedded into microcode and viewed as an extended hardware interfaceFour Kernel instructions are defined to support data management They provide a powerful basis for the implementation of different kinds of access methods and file systems, including data base systems Advanced transaction processing concepts such as concurrency control, support of backout, commit and a variety of share options are included.
Lessons from a "living in a database" graphical query interface
Authors: Fogg Dennis
Published: November 2005

The Living In a Database system (LID) is a user-friendly interface to an entity-relationship database Its underlying ideas are similar to Cattell's PDB [Cattell 80], but its presentation is significantly different LID uses a bit-mapped graphics terminal with mouse pointer to create an attractive interaction environment. Experience from the implementation suggests that dynamic graphic displays --- those which have graphic symbols that change as the data they present change --- are an important feature in user interfaces but are difficult to implement with current technology The implementation also uncovers an important inadequacy in the PDB/LID idea the inability to operate on sets of data instances in the same way as individual data instances An extension to LID is suggested to alleviate the problem.
Efficient processing of relational calculus expressions using range query theory
Authors: Willard Dan E
Published: November 2005

In this paper we define a language based on a broad subset of the relational calculus and show all expressions in this language can be evaluated in space O(N) and time O(N log
d
N), where d is a small constant whose value depends on the particular predicate and where N is the number of records stored in the data base. We currently have no hard statistics, but a reasonable guess seems to be that a standard sequential random access machine can handle 95% or more of commercial requests in time O(N log N) and memory O(N) using this technique.
A methodology for database system performance evaluation
Authors: Boral Haran , DeWitt David J
Published: November 2005

This paper presents a methodology for evaluating the performance of database management systems and database machines in a multiuser environment. Three main factors that affect transaction throughput in a multiuser environment are identified: multiprogramming level, degree of data sharing among simultaneously executing transactions, and transaction mix. We demonstrate that only four basic query types are needed to construct a benchmark that will evaluate the performance of a system under a wide variety of workloads. Finally, we present the results of applying our techniques to the Britton-Lee IDM 500 database machine
QUEL as a data type
Authors: Stonebraker Michael , Anderson Erika , Hanson Eric , Rubenstein Brad
Published: November 2005

This paper explores the use of commands in a query language as an abstract data type (ADT) in data base management systems Basically, an ADT facility allows new data types, such as polygons, lines, money, time, arrays of floating point numbers, bit vectors, etc, to supplement the built-in data types in a data base system. In this paper we demonstrate the power of adding a data type corresponding to commands in a query language We also propose three extensions to the query language QUEL to enhance its power in this augmented environment.
An active mail system
Authors: Hogg John , Gamvroulas Stelios
Published: November 2005

Conventional electronic mail is
passive
text that is created, sent and read. Any further actions must be initiated by the recipient. By contrast, an "intelligent message" (
imessage
) is an active program that carries on a dialogue with the recipient. The imessage may subsequently route itself to other users as a result of the responses it receives, and it eventually returns these responses to the original sender.This paper describes a prototype intelligent mail system and discusses some of the problems involved in implementing such a system in a distributed environment.
Accurate estimation of the number of tuples satisfying a condition
Authors: Piatetsky-Shapiro Gregory , Connell Charles
Published: November 2005

We present a new method for estimating the number of tuples satisfying a condition of the type
attribute rel constant,
where
rel
is one of "=", ">", "<", "≥", "≤". Our method gives highly accurate, yet easy to compute, estimates. We store information about attribute values as a list of
distribution steps
(histograms where buckets, instead of having equal width, have equal height). These distribution steps provide an upper bound on the error when estimating the number of tuples satisfying a condition. The estimation error can be arbitrarily reduced by increasing the number of steps. We analyze desirable conditions that such estimates should satisfy. Based on the distribution steps, we derive a set of estimation formulas which minimize the worst-case error. We also present another set of formulas which reduce the average-case error. Finally, we show how to use sampling to compute a close approximation of the distribution steps very quickly. The major applications of our method are in query optimization and in answering statistical queries.
The use of extended Boolean logic in information retrieval
Authors: Salton Gerard
Published: November 2005

An extended Boolean retrieval strategy has previously been introduced in which the individual Boolean operators can be treated more or less strictly, depending on the perceived strength of association of the query terms. The extended Boolean system is illustrated by examples and evaluation output is used to demonstrate the effectiveness of the operations.
An implementation of GEM
Authors: Tsur Shalom , Zaniolo Carlo
Published: November 2005

This paper presents a simple approach for extending the relational system INGRES into one supporting a semantic data model it describe a DBMS consisting of (i) a user-friendly front-end, supporting the GEM semantic data model and query language under the UNIX time-sharing system, and (ii) a dedicated back-end processor providing efficient support for database transactions, concurrency control and recovery GEM extends the relational model to support the notions of entities with surrogates, the relationships of aggregation and generalization, null values and set-valued attributes, and provides simple extensions of QUEL to handle these new constructs in this proposed implementation of GEM, the relational database processor IDM 500 by Britton-Lee is used as the back-end machine
Relational algebras, logic, and functional programming
Authors: Hall Patrick A. V.
Published: November 2005

Relational algebras as developed by Codd and his followers are extended by noting an equivalence with functional languages. This leads to higher order relations, recursive definitions of relations, and the use of higher order relations as recursive data structures. This equivalence on the one hand enables the technology of databases to be used within the context of applicative languages, and on the other hand removes the adhoc mechanisms used for higher order operations in relational databases. This leads from 4th to 5th generation data management, exploiting the mathematical foundations of functional languages and logic programming, and the technology of relational database.
Transaction management in an object-oriented database system
Authors: Garza Jorge F. , Kim Won
Published: November 2005

In this paper, we describe transaction management in ORION, an object-oriented database system. The application environments for which ORION is intended led us to implement the notions of sessions of transactions, and hypothetical transactions (transactions which always abort). The object-oriented data model which ORION implements complicates locking requirements. ORION supports a concurrency control mechanism based on extensions to the current theory of locking, and a transaction recovery mechanism based on conventional logging.
A sound and complete query evaluation algorithm for relational databases with null values
Authors: Yuan Li Yan , Chiang Ding-An
Published: November 2005

Reiter has proposed extended relational theory to formulate relational databases with null values and presented a query evaluation algorithm for such databases. However, due to indefinite information brought in by null values, Reiter's algorithm is sound but not complete. In this paper, we first propose an extended relation to represent indefinite information in relational databases. Then, we define an extended relational algebra for extended relations. Based on Reiter's extended relational theory, and our extended relations and the extended relational algebra, we present a sound and complete query evaluation algorithm for relational databases with null values
A case for redundant arrays of inexpensive disks (RAID)
Authors: Patterson David A. , Gibson Garth , Katz Randy H.
Published: November 2005

Increasing performance of CPUs and memories will be squandered if not matched by a similar performance increase in I/O. While the capacity of Single Large Expensive Disks (SLED) has grown rapidly, the performance improvement of SLED has been modest. Redundant Arrays of Inexpensive Disks (RAID), based on the magnetic disk technology developed for personal computers, offers an attractive alternative to SLED, promising improvements of an order of magnitude in performance, reliability, power consumption, and scalability. This paper introduces five levels of RAIDs, giving their relative cost/performance, and compares RAID to an IBM 3380 and a Fujitsu Super Eagle.