An algebraic transformation framework for multidatabase queries

Existence of semantic conflicts between component databases severely impacts query processing in a multidatabase system. In this paper, we describe two types of semantic conflicts that have to be dealt with in the integration of databases modeling information about related sets of real-world entities. These are the entityidentification problem and theattribute value conflict problem. While thetwo-way outerjoin operation has been commonly used for resolving entity identification problem between two component relations, outerjoins using regular equality comparisons between component relation keys is shown to produce counter-intuitive entity identification result. We remedy this by defining a newkey-equality comparator in place of regular equality comparator, for outerjoins. For the attribute value conflict problem, we define aGeneralized Attribute Derivation (GAD) operation which allows user-defined attribute derivation functions to be used to compute new attributes from the component relations' attributes. By adding two-way outerjoin andGAD to the set of relational operations, the traditional algebraic transformation framework for relational queries is no longer adequate for multidatabase query processing and optimization. As a result, we introduceconstrained query tree as the multidatabase query representation. We show that some knowledge about query predicates and attribute derivation functions can be used to simplify queries. Such knowledge is modeled as an outerjoin graph attached to every outerjoin operation in the query tree. Based on this, we further extend the traditional algebraic transformation framework to include two-way outerjoins andGAD operations. Our framework demonstrates that properties of selection/join predicates and attribute derivation functions can be used to provide interesting transformation alternatives. This framework also serves as a formal ground for developing optimization strategies for multidatabase queries. Recommended by: Clement Yu     

Efficient algorithms for mining maximal valid groups

A valid group is defined as a group of moving users that are within a distance threshold from one another for at least a minimum time duration. Unlike grouping of users determined by traditional clustering algorithms, members of a valid group are expected to stay close to one another during their movement. Each valid group suggests some social grouping that can be used in targeted marketing and social network analysis. The existing valid group mining algorithms are designed to mine a complete set of valid groups from time series of user location data, known as the user movement database. Unfortunately, there are considerable redundancy in the complete set of valid groups. In this paper, we therefore address this problem of mining the set of maximal valid groups. We first extend our previous valid group mining algorithms to mine maximal valid groups, leading to AMG and VGMax algorithms. We further propose the VGBK algorithm based on maximal clique enumeration to mine the maximal valid groups. The performance results of these algorithms under different sets of mining parameters are also reported.     

Transaction recovery in federated autonomous databases

Transaction management for federated database systems (FDBSs), where each participating DBMS is autonomous, supports global transactions that can access more than one database. A number of concurrency control algorithms exist for the failure-free environment. Handling transaction failure, due to concurrency control or site related reasons, becomes especially difficult in the presence of autonomy. Due to local autonomy, carrying out 2-phase commit may not be possible. This can be simulated by providing a server on top of the pre-existing DBMS at each site, which is responsible for submitting the local operations to the associated DBMS and communicating with the transaction's originating site. In this paper we formalize the problem of ensuring transaction consistency in an FDBS environment in the presence of failure. The key problem is that due to autonomy, the local DBMS and FDBS may have different views of an execution sequence generated at a site.Local recoverability is identified as the property of local execution sequences necessary for correctness. The other main problem is of guaranteeing that the various locally recoverable histories are consistent with each other. These identified properties are necessary and sufficient conditions for the correctness of FDBS recovery algorithms, and can be used to evaluate the correctness of the proposed algorithms. This paper also presents an FDBS recovery algorithm that has been proved to be correct. Formal proofs of all properties and a comparison of different algorithms are provided. Recommended by: Y. BreitbartThis work was supported in part by sub-contract #B09530013 from Honeywell SSDC, under contract #F30602-91-C-0128 from Rome Laboratory of the US Air Force.On leave from Computer Science Department, Heilongjiang University, People's Republic of China.     

Myriad: Design and implementation of a federated database prototype

A key problem in providing ‘enterprise-wide’ information is the integration of databases that have been independently developed. An important requirement is to accommodate heterogeneity and maintain the autonomy of component databases. Myriad is a federated database prototype developed at the University of Minnesota, to provide a testbed for investigating alternatives in architecture and algorithms for database integration, query processing and optimization, and concurrency control and recovery. The system incorporates our group's research results in these areas. This paper describes our experiences in the design and implementation of Myriad, and in the project management. Special emphasis is given to discussing design alternatives and their impact on Myriad. This paper also presents the software engineering principles and the project management techniques we used in developing Myriad and the lessons we learned. We believe these lessons would be useful for practitioners who wish to develop a similar system. Handling heterogeneity and autonomy were prime objectives throughout the prototyping effort. We are convinced that a prototype federated database is an important infrastructural requirement for the overall goal of ‘enterprise-integration’, and believe Myriad to be a significant contribution towards this.     

A probabilistic approach to modeling and estimating the QoS of web-services-based workflows

Web services promise to become a key enabling technology for B2B e-commerce. One of the most-touted features of Web services is their capability to recursively construct a Web service as a workflow of other existing Web services. The quality of service (QoS) of Web-services-based workflows may be an essential determinant when selecting constituent Web services and determining the service-level agreement with users. To make such a selection possible, it is essential to estimate the QoS of a WS workflow based on the QoSs of its constituent WSs. In the context of WS workflow, this estimation can be made by a method called QoS aggregation. While most of the existing work on QoS aggregation treats the QoS as a deterministic value, we argue that due to some uncertainty related to a WS, it is more realistic to model its QoS as a random variable, and estimate the QoS of a WS workflow probabilistically. In this paper, we identify a set of QoS metrics in the context of WS workflows, and propose a unified probabilistic model for describing QoS values of a broader spectrum of atomic and composite Web services. Emulation data are used to demonstrate the efficiency and accuracy of the proposed approach.     

Parallel Array Object I/O Support on Distributed Environments

This paper presents a parallel file object environment to support distributed array store on shared-nothing distributed computing environments. Our environment enables programmers to extend the concept of array distributions from memory levels to file levels. It allows parallel I/O that facilitates the distribution of objects in an application. When objects are read and/or written by multiple applications using different distributions, we present a novel scheme to help programmers to select the best data distribution pattern according to a minimum amount of remote data movements for the store of array objects on distributed file systems. Our selection scheme, to the best of our knowledge, is the first work to attempt to optimize the distribution patterns in the secondary storage for HPF-like programs with inter-application cases. This is especially important for a class of problems called multiple disciplinary optimization (MDO) problems. Our test bed is built on an 8-node DEC Farm connected with an ethernet, FDDI, or ATM switch. Our experimental results with scientific applications show that not only our parallel file system can provide aggregate bandwidths, but also our selection scheme effectively reduces the communication traffic for the system.     

A word embedding-based approach to cross-lingual topic modeling

Knowledge and Information Systems - The cross-lingual topic analysis aims at extracting latent topics from corpora of different languages. Early approaches rely on high-cost multilingual resources...     

Efficient mining of group patterns from user movement data

In this paper, we present a new approach to derive groupings of mobile users based on their movement data. We assume that the user movement data are collected by logging location data emitted from mobile devices tracking users. We formally define group pattern as a group of users that are within a distance threshold from one another for at least a minimum duration. To mine group patterns, we first propose two algorithms, namely AGP and VG-growth. In our first set of experiments, it is shown when both the number of users and logging duration are large, AGP and VG-growth are inefficient for the mining group patterns of size two. We therefore propose a framework that summarizes user movement data before group pattern mining. In the second series of experiments, we show that the methods using location summarization reduce the mining overheads for group patterns of size two significantly. We conclude that the cuboid based summarization methods give better performance when the summarized database size is small compared to the original movement database. In addition, we also evaluate the impact of parameters on the mining overhead.