Date of Publication

4-1995

Document Type

Master's Thesis

Degree Name

Master of Science in Computer Science

Subject Categories

Computer Sciences | Databases and Information Systems

College

College of Computer Studies

Department/Unit

Computer Science

Thesis Adviser

Roshan Zamir Tarar

Defense Panel Chair

Arnulfo P. Azcarraga

Defense Panel Member

Harry Joson
Lloyd Espiritu

Abstract/Summary

The design of algorithms for distributed databases should involve the design of a distributed data structure. However, it is assumed that arising from the distribution of any entity are problems on data consistency and efficiency. Efforts on the solution to these problems in the context of distributed data structures have been quite few. As a contribution to this area, a distributed B-tree is designed to index a distributed database. The distributed structure includes two logical processors, namely, the tree manager and the subtree managers, in addition to the features of the sequential B-tree. In order to allow more concurrency, the design and verification of the algorithms on the structure are based on the semantics of a dictionary abstract data type. A link technique, which operated in the context of the semantic approach, is used to provide data consistency without involving large updates on the structure. A maintenance process, which covers the split and merge operations, is conceived to reorganize the structure during idle periods. Since a B-tree is always balanced and large updates to not occur, the operations on the distributed structure are efficient. No node is replicated so that extra space requirement is only incurred by the logical processors.

Abstract Format

html

Language

English

Format

Electronic

Accession Number

TG02585

Shelf Location

Archives, The Learning Commons, 12F Henry Sy Sr. Hall

Physical Description

100, [4] leaves; 28 cm.

Keywords

Electronic data processing--Distributed processing; Trees (Graph theory); Algorithms; Data structures (Computer science); Databases

Upload Full Text

wf_yes

Share

COinS