Spatial Data Databases can store data types such as lines,polygons,in addition to raster images allows relational databases to store and retrieve spatial information Queries can use spatial conditions (e.g.contains or overlaps). queries can mix spatial and nonspatial conditions ■ Nearest neighbor queries,given a point or an object,find the nearest object that satisfies given conditions. Range queries deal with spatial regions.e.g.,ask for objects that lie partially or fully inside a specified region. Queries that compute intersections or unions of regions. Spatial join of two spatial relations with the location playing the role of join attribute. Database System Concepts-7th Edition 24.17 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 24.17 ©Silberschatz, Korth and Sudarshan th Edition Spatial Data ▪ Databases can store data types such as lines, polygons, in addition to raster images • allows relational databases to store and retrieve spatial information • Queries can use spatial conditions (e.g. contains or overlaps). • queries can mix spatial and nonspatial conditions ▪ Nearest neighbor queries, given a point or an object, find the nearest object that satisfies given conditions. ▪ Range queries deal with spatial regions. e.g., ask for objects that lie partially or fully inside a specified region. ▪ Queries that compute intersections or unions of regions. ▪ Spatial join of two spatial relations with the location playing the role of join attribute
Indexing of Spatial Data 3 3 k-d tree-early structure used for indexing in multiple dimensions. Each level of a k-d tree partitions the space into two. 2 choose one dimension for partitioning at the root level of the tree. choose another dimensions for partitioning in nodes at the next level and so on,cycling through the dimensions. In each node,approximately half of 3 3 the points stored in the sub-tree fall on one side and half on the other. The k-d-B tree extends the k- d tree to allow multiple child Partitioning stops when a node has nodes for each internal node; less than a given number of points. well-suited for secondary storage. Database System Concepts-7th Edition 24.18 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 24.18 ©Silberschatz, Korth and Sudarshan th Edition Indexing of Spatial Data ▪ k-d tree - early structure used for indexing in multiple dimensions. ▪ Each level of a k-d tree partitions the space into two. • choose one dimension for partitioning at the root level of the tree. • choose another dimensions for partitioning in nodes at the next level and so on, cycling through the dimensions. ▪ In each node, approximately half of the points stored in the sub-tree fall on one side and half on the other. ▪ Partitioning stops when a node has less than a given number of points. 3 1 3 2 3 3 2 ▪ The k-d-B tree extends the kd tree to allow multiple child nodes for each internal node; well-suited for secondary storage