This work focuses on increasing the network coverage for stream traffic in disaster scenarios, which is often critical for preventing damages to property and, most importantly, loss of life. The technique described here, based on the so-called virtual access points (VAPs), and increases the network coverage in a non intrusive and transparent way. It creates a distributed and cooperative cache among the mobile nodes in the affected area. When using the VAP technique, nodes cooperatively work as virtual access points rebroadcasting messages they have in their own cache helping nodes that didn't have access to those pieces of message. The main advantages include that the proposed technique does not rely on any specific characteristic of the network, is transparent, and achieves highly improves the efficiency of stream traffic dissemination resulting in much lower message loss. Our results show that VAPs greatly enhance network coverage. In fact, for some of the scenarios presented, it allows the system to remain operational under conditions it would otherwise be inadequate for stream traffic.

In this paper we consider the problem of dissemination of stream based traffic using access points as roadside equipment. We consider how areas outside direct coverage can still be reached by means of other vehicles acting as virtual access points (VAPs). The developed technique, allows transparently extending the reach of roadside access points to uncovered road areas. VAPs are designed to avoid interference, operating in regions bounded outside any AP. The simulations show the presented mechanism to exhibit gain, in terms of received messages, of 30% and perhaps more significantly, that streaming data delivery becomes feasible.

In the near future, we will be surrounded by ubiquitous wireless networks and so information dissemination for mobile users is a key issue. Hybrid push-pull constitutes a very effective and scalable solution. Our contribution is twofold. First we provide a new analysis that takes into account the user mobility. We argue that in a highly mobile setting, analysis and optimization goals discussed in past papers become irrelevant, since the most important aspect of the system is not delay, but rather the ability to answer as many queries as possible. As we show, the optimal pull-push bandwidth ratio depends on the mobility patterns of the users. Second, we use our findings to build Mobile-Cache, a system that can efficiently answer multiple queries over a wireless environment.

Several studies have demonstrated the effectiveness of the Haar wavelet decomposition as a tool for reducing large amounts of data down to compact wavelet synopses that can be used to obtain fast, accurate approximate answers to user queries. Although originally designed for minimizing the overall mean-squared (i.e., L 2 -norm) error in the data approximation, recently proposed methods also enable the use of Haar wavelets in minimizing other error metrics, such as the relative error in data value reconstruction, which is arguably the most important for approximate query answers. Relatively little attention, however, has been paid to the problem of using wavelet synopses as an approximate query answering tool over complex tabular datasets containing multiple measures , such as those typically found in real-life OLAP applications. Existing decomposition approaches will either operate on each measure individually, or treat all measures as a vector of values and process them simultaneously. As we demonstrate in this article, these existing individual or combined storage approaches for the wavelet coefficients of different measures can easily lead to suboptimal storage utilization, resulting in drastically reduced accuracy for approximate query answers. To address this problem, in this work, we introduce the notion of an extended wavelet coefficient as a flexible, efficient storage method for wavelet coefficients over multimeasure data. We also propose novel algorithms for constructing effective (optimal or near-optimal) extended wavelet-coefficient synopses under a given storage constraint, for both sum-squared error and relative-error norms. Experimental results with both real-life and synthetic datasets validate our approach, demonstrating that our techniques consistently obtain significant gains in approximation accuracy compared to existing solutions.

Aggregated information regarding implicated entities is critical for online applications like network management, traffic characterization or identifying patters of resource consumption. Recently there has been a flurry of research for online aggregation on streams (like quantiles, hot items, hierarchical heavy hitters) but surprisingly the problem of summarizing implicated information in stream data has received no attention. As an example, consider an IP-network and the implication source /spl rarr/ destination. Flash crowds - such as those that follow recent sport events (like the Olympics) or seek information regarding catastrophic events - or denial of service attacks direct a large volume of traffic from a huge number of sources to a very small number of destinations. In this paper we present novel randomized algorithms for monitoring such implications with constraints in both memory and processing power for environments like network routers. Our experiments demonstrate several factors of improvements over straightforward approaches.

We are inevitably moving into a realm where small and inexpensive wireless devices would be seamlessly embedded in the physical world and form a wireless sensor network in order to perform complex monitoring and computational tasks. Such networks pose new challenges in data processing and dissemination because of the limited resources (processing, bandwidth, energy) that such devices possess. In this paper we propose a new technique for compressing multiple streams containing historical data from each sensor. Our method exploits correlation and redundancy among multiple measurements on the same sensor and achieves high degree of data reduction while managing to capture even the smallest details of the recorded measurements. The key to our technique is the base signal, a series of values extracted from the real measurements, used for encoding piece-wise linear correlations among the collected data values. We provide efficient algorithms for extracting the base signal features from the data and for encoding the measurements using these features. Our experiments demonstrate that our method by far outperforms standard approximation techniques like Wavelets. Histograms and the Discrete Cosine Transform, on a variety of error metrics and for real datasets from different domains.

The data cube operator exemplifies two of the most important aspects of OLAP queries: aggregation and dimension hierarchies. In earlier work we presented Dwarf, a highly compressed and clustered structure for creating, storing and indexing data cubes. Dwarf is a complete architecture that supports queries and updates, while also including a tunable granularity parameter that controls the amount of materialization performed. However, it does not directly support dimension hierarchies. Rollup and drilldown queries on dimension hierarchies that naturally arise in OLAP need to be handled externally and are, thus, very costly. In this paper we present extensions to the Dwarf architecture for incorporating rollup data cubes, i.e. cubes with hierarchical dimensions. We show that the extended Hierarchical Dwarf retains all its advantages both in terms of creation time and space while being able to directly and efficiently support aggregate queries on every level of a dimension's hierarchy.

Peer-to-peer networks are gaining increasing attention from both the scientific and the large Internet user community. Popular applications utilizing this new technology offer many attractive features to a growing number of users. At the heart of such networks lies the search algorithm. Proposed methods either depend on the network-disastrous flooding and its variations or utilize various indices too expensive to maintain. We describe an adaptive, bandwidth-efficient algorithm for search in unstructured peer-to-peer networks, the adaptive probabilistic search method (APS). Our scheme utilizes feedback from previous searches to probabilistically guide future ones. It performs efficient object discovery while inducing zero overhead over dynamic network operations. Extensive simulation results show that APS achieves high success rates, increased number of discovered objects, very low bandwidth consumption and adaptation to changing topologies.

While work in recent years has demonstrated that wavelets can be efficiently used to compress large quantities of data and provide fast and fairly accurate answers to queries, little emphasis has been placed on using wavelets in approximating datasets containing multiple measures. Existing decomposition approaches will either operate on each measure individually, or treat all measures as a vector of values and process them simultaneously. We show in this paper that the resulting individual or combined storage approaches for the wavelet coefficients of different measures that stem from these existing algorithms may lead to suboptimal storage utilization, which results to reduced accuracy to queries. To alleviate this problem, we introduce in this work the notion of an extended wavelet coefficient as a flexible storage method for the wavelet coefficients, and propose novel algorithms for selecting which extended wavelet coefficients to retain under a given storage constraint. Experimental results with both real and synthetic datasets demonstrate that our approach achieves improved accuracy to queries when compared to existing techniques. UMIACS-TR-2003-32

Dwarf is a highly compressed structure for computing, storing, and querying data cubes. Dwarf identifies prefix and suffix structural redundancies and factors them out by coalescing their store. Prefix redundancy is high on dense areas of cubes but suffix redundancy is significantly higher for sparse areas. Putting the two together fuses the exponential sizes of high dimensional full cubes into a dramatically condensed data structure. The elimination of suffix redundancy has an equally dramatic reduction in the computation of the cube because recomputation of the redundant suffixes is avoided. This effect is multiplied in the presence of correlation amongst attributes in the cube. A Petabyte 25-dimensional cube was shrunk this way to a 2.3GB Dwarf Cube, in less than 20 minutes, a 1:400000 storage reduction ratio. Still, Dwarf provides 100% precision on cube queries and is a self-sufficient structure which requires no access to the fact table. What makes Dwarf practical is the automatic discovery,in a single pass over the fact table, of the prefix and suffix redundancies without user involvement or knowledge of the value distributions.This paper describes the Dwarf structure and the Dwarf cube construction algorithm. Further optimizations are then introduced for improving clustering and query performance. Experiments with the current implementation include comparisons on detailed measurements with real and synthetic datasets against previously published techniques. The comparisons show that Dwarfs by far out-perform these techniques on all counts: storage space, creation time, query response time, and updates of cubes.

MOCHA is a novel middleware system for integrating distributed data sources that we have developed at the University of Maryland. MOCHA is based on the idea that the code that implements user-defined types and functions should be automatically deployed to remote sites by the middleware system itself. To this end, we have developed an XML-based framework to specify metadata about data sites, data sets, and user-defined types and functions. XRoaster is a graphical tool that we have developed to help the user create all the XML metadata elements to be used in MOCHA.

Materialized aggregate views represent a set of redundant entities in a data warehouse that are frequently used to accelerate On-Line Analytical Processing (OLAP). Due to the complex structure of the data warehouse and the different profiles of the users who submit queries, there is need for tools that will automate and ease the view selection and management processes. In this article we present DynaMat, a system that manages dynamic collections of materialized aggregate views in a data warehouse. At query time, DynaMat utilizes a dedicated disk space for storing computed aggregates that are further engaged for answering new queries. Queries are executed independently or can be bundled within a multiquery expression. In the latter case, we present an execution mechanism that exploits dependencies among the queries and the materialized set to further optimize their execution. During updates, DynaMat reconciles the current materialized view selection and refreshes the most beneficial subset of it within a given maintenance window. We show how to derive an efficient update plan with respect to the available maintenance window, the different update policies for the views and the dependencies that exist among them.

A WebView is a web page automatically created from base data typically stored in a DBMS. Given the multi-tiered architecture behind database-backed web servers, we have the option of materializing a WebView inside the DBMS, at the web server, or not at all, always computing it on the fly (virtual). Since WebViews must be up to date, materialized WebViews are immediately refreshed with every update on the base data. In this paper we compare the three materialization policies (materialized inside the DBMS, materialized at the web server and virtual) analytically, through a detailed cost model, and quantitatively, through extensive experiments on an implemented system. Our results indicate that materializing at the web server is a more scalable solution and can facilitate an order of magnitude more users than the virtual and materialized inside the DBMS policies, even under high update workloads.

Article Free Access Share on MOCHA: a database middleware system featuring automatic deployment of application-specific functionality Authors: Manuel Rodríguez-Martínez Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College Park Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College ParkView Profile , Nick Roussopoulos Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College Park Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College ParkView Profile , John M. McGann Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College Park Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College ParkView Profile , Stephen Kelley Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College Park Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College ParkView Profile , Vadim Katz Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College Park Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College ParkView Profile , Zhexuan Song Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College Park Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College ParkView Profile , Joseph JáJá Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College Park Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College ParkView Profile Authors Info & Claims SIGMOD '00: Proceedings of the 2000 ACM SIGMOD international conference on Management of dataMay 2000 https://doi.org/10.1145/342009.336575Published:16 May 2000Publication History 5citation34DownloadsMetricsTotal Citations5Total Downloads34Last 12 Months11Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We present MOCHA, a new self-extensible database middleware system designed to interconnect distributed data sources. MOCHA is designed to scale to large environments and is based on the idea that some of the user-defined functionality in the system should be deployed by the middleware system itself. This is realized by shipping Java code implementing either advanced data types or tailored query operators to remote data sources and have it executed remotely. Optimized query plans push the evaluation of powerful data-reducing operators to the data source sites while executing data-inflating operators near the client's site. The Volume Reduction Factor is a new and more explicit metric introduced in this paper to select the best site to execute query operators and is shown to be more accurate than the standard selectivity factor alone. MOCHA has been implemented in Java and runs on top of Informix and Oracle. We present the architecture of MOCHA, the ideas behind it, and a performance study using scientific data and queries. The results of this study demonstrate that MOCHA provides a more flexible, scalable and efficient framework for distributed query processing compared to those in existing middleware solutions.

Pre-computation and materialization of views with aggregate functions is a common technique in Data Warehouses. Due to the complex structure of the warehouse and the different profiles of the users who submit queries, there is need for tools that will automate the selection and management of the materialized data. In this paper we present DynaMat, a system that dynamically materializes information at multiple levels of granularity in order to match the demand (workload) but also takes into account the maintenance restrictions for the warehouse, such as down time to update the views and space availability. DynaMat unifies the view selection and the view maintenance problems under a single framework using a novel “goodness” measure for the materialized views. DynaMat constantly monitors incoming queries and materializes the best set of views subject to the space constraints. During updates, DynaMat reconciles the current materialized view selection and refreshes the most beneficial subset of it within a given maintenance window. We compare DynaMat against a system that is given all queries in advance and the pre-computed optimal static view selection. The comparison is made based on a new metric, the Detailed Cost Savings Ratio introduced for quantifying the benefits of view materialization against incoming queries. These experiments show that DynaMat's dynamic view selection outperforms the optimal static view selection and thus, any sub-optimal static algorithm that has appeared in the literature.

The Cubetree Storage Organization (CSO)1 logically and physically clusters materialized-views data, multi-dimensional indices on them, and computed aggregate values all in one compact and tight storage structure that uses a fraction of the conventional table-based space. This is a breakthrough technology for storing and accessing multi-dimensional data in terms of storage reduction, query performance and incremental bulk update speed. CSO has been extended with an Active MultiSync controller for synchronizing multiple concurrent access and continuous asynchronous online updates for a non-stop data warehouse.

The Relational On-Line Analytical Processing (ROLAP) is emerging as the dominant approach in data warehousing with decision support applications. In order to enhance query performance, the ROLAP approach relies on selecting and materializing in summary tables appropriate subsets of aggregate views which are then engaged in speeding up OLAP queries. However, a straight forward relational storage implementation of materialized ROLAP views is immensely wasteful on storage and incredibly inadequate on query performance and incremental update speed. In this paper we propose the use of Cubetrees, a collection of packed and compressed R-trees, as an alternative storage and index organization for ROLAP views and provide an efficient algorithm for mapping an arbitrary set of OLAP views to a collection of Cubetrees that achieve excellent performance. Compared to a conventional (relational) storage organization of materialized OLAP views, Cubetrees offer at least a 2-1 storage reduction, a 10-1 better OLAP query performance, and a 100-1 faster updates. We compare the two alternative approaches with data generated from the TPC-D benchmark and stored in the Informix Universal Server (IUS). The straight forward implementation materializes the ROLAP views using IUS tables and conventional B-tree indexing. The Cubetree implementation materializes the same ROLAP views using a Cubetree Datablade developed for IUS. The experiments demonstrate that the Cubetree storage organization is superior in storage, query performance and update speed.

The Client-Server computing paradigm has significantly influenced the way modern Database Management Systems are designed and built. In such systems, clients maintain data pages in their main-memory caches, originating from the server's database. The Enhanced Client-Server architecture takes advantage of all the available client resources, including their long-term memory. Clients can cache server data into their own disk units if these data are part of their operational spaces. However, when updates occur at the server, a number of clients may need to not only be notified about these changes, but also obtain portions of the updates as well. In this paper, we examine the problem of managing server imposed updates that affect data cached on client disk managers. We propose a number of server update propagation techniques in the context of the Enhanced Client-Server DBMS architecture, and examine the performance of these strategies through detailed simulation experiments. In addition, we study how the various settings of the network affect the performance of these policies.

The data cube is an aggregate operator which has been shown to be very powerful for On Line Analytical Processing (OLAP) in the context of data warehousing. It is, however, very expensive to compute, access, and maintain. In this paper we define the “cubetree” as a storage abstraction of the cube and realize in using packed R-trees for most efficient cube queries. We then reduce the problem of creation and maintenance of the cube to sorting and bulk incremental merge-packing of cubetrees. This merge-pack has been implemented to use separate storage for writing the updated cubetrees, therefore allowing cube queries to continue even during maintenance. Finally, we characterize the size of the delta increment for achieving good bulk update schedules for the cube. The paper includes experiments with various data sets measuring query and bulk update performance.

In many modern database applications, there is an emerging need for interactive environments where users directly manipulate the contents of the database. Graphical user interfaces (GUIs) display images of the database which must reflect a consistent up-to-date state of the data with minimum perceivable delay to the user. Moreover, the possibility of several applications concurrently displaying different views of the same database increases the overall system complexity. In this paper, we show how design, performance and concurrency issues can be addressed by adapting existing database techniques. We propose the use of suitable display schemas whose instances compose active views of the database, an extended client caching scheme which is expected to yield significant performance benefits, and a locking mechanism that maintains consistency between the GUIs and the database.

A frequently encountered type of query in Geographic Information Systems is to find the k nearest neighbor objects to a given point in space. Processing such queries requires substantially different search algorithms than those for location or range queries. In this paper we present an efficient branch-and-bound R-tree traversal algorithm to find the nearest neighbor object to a point, and then generalize it to finding the k nearest neighbors. We also discuss metrics for an optimistic and a pessimistic search ordering strategy as well as for pruning. Finally, we present the results of several experiments obtained using the implementation of our algorithm and examine the behavior of the metrics and the scalability of the algorithm.

The client-server DBMS model has emerged as the main paradigm in database computing. The enhanced client-server architecture takes advantage of all the available client resources including their disk managers. Clients can cache server data into their own disk units if data are part of their operational space. However, when updates occur at the server, some of the client data managers may need to not only be notified about them but also obtain portions of the updates as well. In this paper, we examine the problem of managing server-imposed updates that affect client cached data. We propose a number of server update propagation techniques in the context of the enhanced client-server DBMS architecture and examine the performance of these strategies through detailed simulation experiments.>

In this paper, we propose a novel approach for estimating the record selectivities of database queries. The real attribute value distribution is adaptively approximated by a curve-fitting function using a query feedback mechanism. This approach has the advantage of requiring no extra database access overhead for gathering statistics and of being able to continuously adapt the value distribution through queries and updates. Experimental results show that the estimation accuracy of this approach is comparable to traditional methods based on statistics gathering.

There has been a growing demand for the development of tools to manage enterprise communication networks. A management information database is the heart of a network management system-it provides the interface between all functions of the network management system and, therefore, has to provide sophisticated functionality allied with high performance. The authors introduce the design of MANDATE (MAnaging Networks using DAtabase TEchnology), a proposed database system for effectively supporting the management of large enterprise networks. The MANDATE design makes a conscious attempt to take advantage of the special characteristics of network data and transactions, and of advances in database technology, to efficiently derive some of the required management functionality.>

ADMS is an advanced database management system developed-to experiment with incremental access methods for large and distributed databases. It has been developed over the past eight years at the University of Maryland. The paper provides an overview of ADMS, and describes its capabilities and the performance attained by its incremental access methods. This paper also describes an enhanced client-server architecture that allows an incremental gateway access to multiple heterogeneous commercial database management systems.>

The introduction of powerful workstations connected through local area networks (LANs) inspired new database management system (DBMS) architectures that offer high performance characteristics. The authors examine three such software architecture configurations: client-server (CS), the RAD-UNIFY type of DBMS (RU), and enhanced client-server (ECS). Their specific functional components and design rationales are discussed. Three simulation models are used to provide a performance comparison under different job workloads. Simulation results show that the RU almost always performs slightly better than the CS, especially under light workloads, and that ECS offers significant performance improvement over both CS and RU. Under reasonable update rates, the ECS over CS (or RU) performance ratio is almost proportional to the number of participating clients (for less than 32 clients). The authors also examine the impact of certain key parameters on the performance of the three architectures and show that ECS is more scalable that the other two.>

Abstract An incrementally maintained mapping from a network to a relational database is presented. This mapping may be established either to support the efficient retrieval of data from a network database through a relational interface, or as the first step in a gradual conversion of data and applications from a network to a relational database system. After the mapping has been established, the only data mapped from the network to the relational database are the increments resulting from updates on the network database. The mapping is therefore an efficient alternative to mappings that repeatedly map the results of retrievals through the relational interface from the network database to the relational database. This is in particular the case when the two databases reside on different hosts. Applications on the network database may, under certain restrictions, gradually be moved to the relational database, while the mapping incrementally maintains the relational database for the applications that remain on the network database. A detailed, but generic, account of how to build such a mapping from a network to a relational database is given, including all the algorithms needed and examples of their use.

An implementation model for the standard relational data model extended with transaction time is presented. The implementation model integrates techniques of view materialization, differential computation, and deferred update into a coherent whole. It is capable of storing any view (reflecting past or present states) and subsequently using stored views as outsets for incremental and decremental computations of requested views, making it more flexible than previously proposed partitioned storage models. The working and the expressiveness of the model are demonstrated by sample queries that show how historical data are retrieved.>

The semijoin has been used as an effective operator in reducing data transmission and processing over a network that allows forward size reduction of relations and intermediate results generated during the processing of a distributed query. The authors propose a relational operator, two-way semijoin, which enhanced the semijoin with backward size reduction capability for more cost-effective query processing. A pipeline N-way join algorithm for joining the reduced relations residing on N sites is introduced. The main advantage of this algorithm is that it eliminates the need for transferring and storing intermediate results among the sites. A set of experiments showing that the proposed algorithm outperforms all known conventional join algorithms that generate intermediate results is included.>

A ViewCache is a stored collection of pointers pointing to records of underlying relations needed to materialize a view. This paper presents an Incremental Access Method (IAM) that amortizes the maintenance cost of ViewCaches over a long time period or indefinitely. Amortization is based on deferred and other update propagation strategies. A deferred update strategy allows a ViewCache to remain outdated until a query needs to selectively or exhaustively materialize the view. At that point, an incremental update of the ViewCache is performed. This paper defines a set of conditions under which incremental access to the ViewCache is cost effective. The decision criteria are based on some dynamically maintained cost parameters, which provide accurate information but require inexpensive bookkeeping. The IAM capitalizes on the ViewCache storage organization for performing the update and the materialization of the ViewCaches in an interleaved mode using one-pass algorithms. Compared to the standard technique for supporting views that requires reexecution of the definition of the view, the IAM offers significant performance advantages. We will show that under favorable conditions, most of which depend on the size of the incremental update logs between consecutive accesses of the views, the incremental access method outperforms query modification. Performance gains are higher for multilevel ViewCaches because all the I/O and CPU for handling intermediate results are avoided.

Trie hashing (TH), a primary key access method for storing and accessing records of dynamic files, is discussed. The key address is computed through a trie. A key search usually requires only one disk access when the trie is in core and two disk accesses for very large files when the trie must be on disk. A refinement to trie hashing, trie hashing with controlled load (THCL), is presented. It is designed to control the load factor of a TH file as tightly as that of a B-tree file, allows high load factor of up to 100% for ordered insertions, and increases the load factor for random insertions from 70% to over 85%. It is shown that these properties make trie hashing preferable to a B-tree.>

Commercially available database systems do not meet the information and processing needs of design and manufacturing environments. A new generation of systems-engineering information systems-must be built to meet these needs. The architectural and computational aspects of such systems are addressed, and solutions are proposed. The authors argue that a mainframe-workstation architecture is needed to provide distributed functionality while ensuring high availability and low communication overhead, that explicit control of metaknowledge is needed to support extendibility and evolution, that large rule bases are needed to make the knowledge of the systems active, and that incremental computation models are needed to achieve the required performance of such engineering information systems.>

Pictorial databases require efficient and direct spatial search based on the analog form of spatial objects and relationships instead of search based on some cumbersome alphanumeric encodings of the pictures. A description is given of PSQL, a query language that allows pictorial domains to be presented to the user in their analog form and allows him or her to do direct manipulation on the objects found on those domains. Direct spatial search and computation on the pictures is done using efficient data structures, R- and R/sup +/-trees (multidimensional B-trees), which are excellent devices for searching spatial objects and relationships found on pictures.>

In distributed query processing, the semijoin has been used as an effective operator in reducing relations referenced in the query to reduce the total amount of data transmission. In this paper, we propose a new relational algebra operator, 2-way semijoin, which is an extended version of the semijoin, for more cost-effective distributed query processing. The 2-way semijoin is compared to the semijoin in terms of the reduction power and the propagation of reduction effects. We show that the 2-way semijoin has more reduction power than the semijoin and that the propagation of reduction effects by the 2-way semijoin is further than by the semijoin.

This paper provides an analysis of R-trees and a variation (R+-trees) that avoids overlapping rectangles in intermediate nodes of the tree. The main contributions of the paper are the following. We provide the first known analysis of R-trees. Although formulas are given for objects in one dimension (line segments), they can be generalized for objects in higher dimensions as well. We show how the transformation of objects to higher dimensions [HINR83] can be effectively used as a tool for the analysis of R- and R+- trees. Finally, we derive formulas for R+-trees and compare the two methods analytically. The results we obtained show that R+-trees require less than half the disk accesses required by a corresponding R-tree when searching files of real life sizes R+-trees are clearly superior in cases where there are few long segments and a lot of small ones.

Pictorial databases require efficient and duect spatml search based on the analog form of spatial obJects and relatlonshlps instead of search based on some cumbersome alphanumeric encodings of the pmtures R-trees (two-dimensional B-trees) are excellent devices for indexing spatial ObJects and relationships found on pictures Their most important feature 1s that they provide high level ObJect onented search rather than search based on the low level elements of spatial ObJects This paper presents an efficient initial packing technique for creatmg R-trees to index spatial ObJects Since pictorial databases are not update mtensive but rather static, the beneflts of this technique are very significant 1.

SEES is a database system to support program testing. The program database is automatically created during the compilation of the program by a compiler built using the YACC compiler-compiler.

We propose a software life cycle which consists of two phases: rapid prototyping and automatic program generation. Software reusability holds the biggest leverage for both phases. This paper outlines the requirements for supporting this two-phase life-cycle using a software-base as an advanced software management system.

A methodology for the statement of timing requirements is presented for a class of embedded computer systems. The notion of a "time-driven" system is introduced which is formalized using a Petri net model augmented with timing information. Several subclasses of time-driven systems are defined with increasing levels of complexity. By deriving the conditions under which the Petri net model can be proven to be safe in the presence of time, timing requirements for modules in the system can be obtained. Analytical techniques are developed for proving safeness in the presence of time for the net constructions used in the defined subclasses of time-driven systems.

The design and maintenance of a useful database system require efficient optimization of the logical access paths which demonstrate repetitive usage patterns. Views (classes of queries given by a query model) are an appropriate intermediate logical representation for database. Frequently accessed views of databases need to be supported by indexing to enhance retrieval. This paper investigates the problem of selecting an optimal index set of views and describes an efficient algorithm for this selection.

A new schema which models the usage of the logical access paths of the database is proposed. The schema models all database activities (i.e., retrievals and updates), and integrates their logical access paths by recognizing common subpaths and increasing the "weight" of the shared subpaths. The logical access path schema provides a comprehensive picture of the logical access paths, and the cumulative usage of the shared subpaths and/or intermediate results. The schema serves a dual purpose. Firstly, it is used as a model of the access requirements during the database design, and secondly, as the basis for optimization during the operation of the database.

A language to support the incremental design of the conceptual schemata of data bases is presented. Abstractions are expressed in terms of high-evel constructs and operations on these abstractions allow the definition of other abstractions. Both abstractions and operations on them are totally independent from the underlying internal representation of the schema, which is created consistently by applying the operators of the language. In addition, the language offers a. number of support facilities for type checking of relationships and graphical displays of the conceptual schemata for easier understanding.

This paper presents a semantic model of data bases. The model assumes the availability of a semantic network storing knowledge about a data base and a set of attributes for the data base. The use of the semantic net in generating a relational schema for the data base, in defining a set of semantic operators and in maintaining the data base consistent is then demonstrated.