Efficient Allocation in Distributed Object Oriented Databases.
Jonathan Pietarila Graham, Jim Alves-Foss · Parallel and Distributed Computing Systems (ISCA) · 2003
Abstract Efficient distribution of data is a major challenge indistributed databases. The problem is even more se-vere for distributed object oriented databases becauseof inheritance, encapsulation and the more complexproblem involved when methods invoke other meth-ods. This problem is a harder version of the relationaldatabase allocation problem(DAP), a problem knownto be NP-hard.We looked at the problem of developing an efficientheuristic for allocating object fragments in a distrib-uted object oriented database. To accomplish this wecreated a genetic algorithm which produced more fa-vorable results as compared to the graphical algorithmof Barker and Bhar [2].Our results show near optimal allocation for thoseconfigurations in which the optimal could be com-puted, improvement over the graphical algorithm andhas a linear running time.Keywords: distributed object oriented database, ob-ject fragments, genetic algorithm, optimal allocation 1 Introduction. Advances in hardware have encouraged more data in-tensive applications. These applications include Mul-timedia, CAD/CAM/CIM and complex financial sys-tems. These applications have processing require-ments that are often beyond the capabilities of typicalRelational Database Management Systems (RDBMS).RDBMS were developed primarily for managerial andadministrative functions and as a result these sys-tems have very little expressive power. The datastored in the majority of these new applications can-not be mapped directly onto the tabular form of aRDBMS. For these new applications, it is importantthat the database system be able to define its owntype of data and operations. These shortcomings ofRDBMS have provided an impetus for the develop-ment of object-oriented database systems (OODBS).OODBS are based on the object-oriented paradigmand their main function is to add persistence to ob-jects. One immediate consequence is that OODBSstore not only data but also the operations which oper-ate on that data. OODBS therefore support a modeldescribing both the representation and manipulationof data within the database model. Evidence suggeststhat these types of databases will continue to grow inimportance and that they provide superior capabilitiesfor processing complex data.Distributed databases have been developed to meetthe needs of businesses. These enterprises, such asbanks and airlines, have thousands of sites locatedacross the world, some sites being geographically farapart. Nevertheless, information services are expectedto collect, store, retrieve, process, aggregate and dis-tribute timely information from data generated atthese geographically remote and dispersed sites [6].Gavish and Sheng-Liu [6] suggest that because of thisseparation of sites, communication delays will be a ma-jor problem. Although query optimization can be usedto reduce communication costs, it is only optimal withrespect to a specified allocation and hence is subjectto the efficiency of that allocation. To achieve minimalcost, proper placement of data is required, the objectallocation problem(OAP), and thiswas our major goalin this study.The remainder of this document is organized as fol-lows. In section 2 we discuss related work on data al-location. We describe the database model we used insection 3 and provide the problem formulation. In thissection we describe the terminology used and expressthe problem goals. Section 4 describes our approachof using genetic algorithms to solve the OAP and wecompare our approach with the approaches appearingin the literature as well as to the optimal allocation.Section 5 analyzes the results obtained from our exper-iments, shows the theoretical soundness of our resultsand discusses the implications of our results and itsposition in the wider literature. Section 6 is our con-clusion and where we discuss our future work.