scientific article; zbMATH DE number 1402212

Authors Y. Manolopoulos, Vassilis Tsotras, Yannis Theodoridis

Publication date 10 February 2000

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Database theory (68P15)

The book offers a comprehensive survey of indexing methods in connection with database architectures. In a brighter context, the book describes various access methods including e.g. sorting and concurrency control for some data structures etc. The main accent is put on advanced methods appropriate for special purpose databases, such as multidimensional, spatial, temporal, multimedia, text, object-oriented, www databases, or databases for data mining or OLAP. The book is structured into 13 Chapters. In Introduction the authors briefly discuss issues related to storage systems. Chapter 2 contains an overview of external sorting methods and introduces notions useful for Chapter 10 devoted to parallel external sorting. The third chapter summarizes fundamental access methods such as index-sequential files, \(\text{B}'\)-trees, external dynamic hashing, and two popular multiattribute access methods -- grid file and \(k\)-\(d\) trees. From the Chapter 4, the reader is introduced into more advanced methods. Chapter 4 is devoted to some structures, which are used not to store integers but ranges of integers, e.g. intervals. These data structures include segment indices interval B-trees and external segment trees. In Chapter 5 the authors discuss the issues related to temporal databases. Among appropriate structures for these databases we can find snapshot index, time-split B-trees, multiversion B-trees, and overlapping B-trees. Chapter 6 is devoted to spatial data structures, i.e. well-known R-trees and their variants, quadtrees, and more recent structures such as LSD-trees. Chapter 7 introduces the reader to spatiotemporal databases, i.e. data, it is spatial and changes in time. Related data structures cover both the discrete and the continuous spatiotemporal environment. A direction of ongoing interest in databases is represented by image databases. Chapter 8 introduces spatial similarity retrieval, indexing based on R-trees, and visual similarity retrieval. The latter uses advanced data structures such as X-trees and M-trees. Chapter 9 contains material based on hashing. Two external perfect methods are presented here. Chapter 10 continues the sorting issues describing in new hardware architectures. Chapter 11 introduces the notion of declustering, i.e. techniques used to distribute a single file structure in several disks. In the context, B-trees, R-trees, quadtree, and linear hashing are examined. In Chapter 12, the authors examine how different locking techniques can be used on B-trees, R-trees, and linear hashing, to provide correct concurrent execution and deadlock-free concurrent transactions. Finally, latest data structures developments in new application spheres are discussed. The book uses a simple algorithmic pseudo-language for describing some methods. Unfortunately, it is applied rarely, most of the methods are explained only verbally. Rich lists of references including recommended further reading accompany particular chapters. The structuring of the book can be found little unusual. The numbering is local in particular chapters. The book can be recommended as a textbook for graduate level courses in database systems, but it could serve as an important reading for database professionals, which find information about the recent development in indexing.

Recommendations

Cited in

(13)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4937698)