Spatial DB

Question 1

Spatial DB vs Image/Multimedia DB

Answer 1

Image/multimedia DB:

• are purely raster data with not structure to queries
• contain complex spatial objects

Spatial DB:

• contain raster data only as a means for visualizing the other data
• contains a large collection of relatively simple objects

Question 2

3 types of structures in spatial DBs

Answer 2

point
line
region

Question 3

what is ROSE Algebra

Answer 3

Robust Spatial Extension Algebra

Question 4

The 2 spatial domains?

Answer 4

EXT = {line, region}
GEO = {point, line, region}

Question 5

3 ROSE operations to evaluate topological relationships

Answer 5

“inside” (geo x region) = bool (returns a bool)
“intersect” (ext1 x ext2) = bool
“adjacent” (region x region) = bool

Question 6

4 ROSE operations returning atomic spatial data types

Answer 6

“intersection” (line x line) = point
“intersection” (region x region) = region
“plus, minus” (geo x geo) = geo
“countour” (region) = line

Question 7

2 ROSE operations returning numbers

Answer 7

“dist” (geo1 x geo2) = real

“perimeter, area” (region) = real

Question 8

2 ROSE operations on object sets

Answer 8

“sum” (set(obj) x (obj -> geo)) = geo

-for all objects in a set (ie. an object could be a city)
-choose a given spatial attribute of the object “(obj -> geo)” (ie. the ‘slums’ of the city is an attribute of the object that is a region)
-we then perform the geometric union of all these attributes to form a single geo
(Remember that the geometric union of two rays can form an angle. The union of two regions forms a region)

“closest” (set(obj) x (obj -> geo1) x geo2 = set(obj)
-returns the set of objects whose spatial attribute value is closest to some spatial reference value

Question 9

3 types of spatial relationships

Answer 9

topological relationships
direction relationships
metric relationships

Question 10

Examples topological relationships

Answer 10

adjacent
inside
disjoint

these are invariant under topological transformations such as translation, scaling, and rotation

Question 11

Examples of direction relationships

Answer 11

above
below
north_of

Question 12

Example of metric relationship

Answer 12

distance

Question 13

8 Properties of B tree

Answer 13

‘m’ is the order of the tree

all leaf nodes are at the same level
if the root is not a leaf, it must have at least 2 children

All other internal nodes have at least m//2 children and at most m children

all internal nodes have at least (#children- 1) keys and at most m-1 Keys.

all leaf nodes have at least m//2 Keys and at most m-1 keys

all key values must be in ascending order

all keys point to data somewhere in the system

Question 14

Differences in B+ tree from B tree

Answer 14

the keys that point to data somewhere in the system are all leaves in the bottom level

each key in an internal node will be the lower bound key of one of its child nodes

ex) (3,7)

left child = […,3)
middle child = [3,7)
right child = [7,…]
Notice how 3 and 7 are repeated in their children

all leaves are linked by pointers for rapid in order traversal

Question 15

inserting a B/B+ tree

Answer 15

find node to add key

if node has room for key simply add it

if node does not have room split the node and send the middle value to the parent.

repeat the previous two steps for the parent if necessary

Question 16

deleting from B/B+ tree

Answer 16

remove key

if #keys falls below ceiling(M/2) then see if a key can be borrowed from the left sibling/cousin

if yes, take the largest key value and readjust the key in the parent node

if left is not able to give a key merge node with its left sibling/cousin

on parent where node was merged from, shift the remaining leaf nodes over, readjust the parent key to be the min value from the right child, and bubble up the extra key up a level

(we can also borrow entire children from the left if needed as well. We only borrow from the right if the entity does not have a left sibling/cousin)

Question 17

3 Query types for points

Answer 17

range query: all points within a query rectangle

nearest neighbor query: point closest to query point

distance scan: enumerate points in increasing distance from a query point

Question 18

2 query types for rectangles

Answer 18

intersection query

containment query

Question 19

What is a k-d tree

Answer 19

partitions a space of points into buckets. These buckets can be indexed and thus finding a certain point is much faster because we only have to check a certain bucket as opposed to all the points in the space

Question 20

Whats the idea of spatial indexing?

Answer 20

it organizes space and the objects in it in some fashion such that only parts the space and a subset of the objects in the space need to be considered to answer a query

Question 21

How to build an R-tree for spatial data

Answer 21

1) add spatial element to node
2) if node has <= m or (M/2 keys) proceed with another insertion
3) if node does not have space split it into 2 MBRs
4) for splitting (aka a “Quadratic Split”) , pick a spatial element to act as the seed (not the one that is to be inserted though)
5) calculate the inefficiency of pairing between the seed element and every other element in the MBR [d = area(MBR) - area(seed) - area(element)]
6) the elements composing the pair with the largest d value will go in separate MBRs
7) for the two newly created MBRs, calculate how much increase in area these MBRs would need to accommodate each spatial element in the old MBR
8) For each element, you should calculate two values (the area increase needed for each of the two MBRs). Select the spatial element with the greatest difference between these two values. Place that element in the MBR with which the area would increase THE LEAST
9) resize the MBR to include the newly added element
10) Repeat steps 7-9 until all elements in the original not split MBR have been added to one of the two new MBRs

Question 22

Querying Algorithm for R-Tree

Answer 22

1) is node a leaf?
2) if yes search each entry of leaf to see if overlaps with object
3) if it does then the query will pull that record potentially containing object X
4) if not a leaf, check each subtree to see if it overlaps with object
5) if no overlap, ignore the subtree, if it does overlap, repeat steps 1-4

Question 23

In order to search for an object in R-Tree, you might have to go through
several rectangles or the entire database in the worst case. Explain why?
How does R+-Tree address this problem?

Answer 23

An object could overlap with all MBRs in the worst case and thus the entire database would have to be searched. However, with an R-tree, just because the element overlaps with a given MBR, does not mean that it will be indexed under that MBR. So, therefore, we are forced to search through every MBR with which the object overlaps to find it.

The R+-tree solves this problem by indexing all objects that intersect with a given MBR under that MBR. Thus we can find the object under any MBR where the intersection occurs.

Question 24

What is a Region Quadtree? How do you construct it?

Answer 24

the idea is to index a (non-curved) region on a grid-like structure such that the collection of the grid indices help “store” the shape of the region

1) create bounding square around the region
2) split the square into 4 equal sub-regions
3) if a sub-region is either “totally empty” or “totally filled” index it with a value.
4) if a sub-region is partially filled, divide that sub-region into 4 equal sub-regions
5) continue this process of partitioning the sub-region into 4s until all sub-regions meet the criterion in (3)
6) To construct the tree, each indexed region should be a leaf node. The depth of a given leaf should be equal to the number of recursive partitions required to satisfy (3) (if we presume the root is at depth of 1)

Question 25

What is a PR Quadtree? How do you construct it?

Answer 25

the idea is to index points in a grid-like structure such that each grid index refers to a single point

1) create bounding square around all points
2) split the square into 4 equal sub-regions
3) if a sub-region is either “totally empty” or has “exactly 1 point inside of it”, index that sub-region with a value
4) if the sub-region contains 2 or more points, divide that sub-region into 4 equal sub-regions
5) continue this process of partitioning the sub-region into 4s until all sub-regions meet the criterion in (3)
6) To construct the tree, each indexed region should be a leaf node. The depth of a given leaf should be equal to the number of recursive partitions required to satisfy (3) (if we presume the root is at depth of 1)

Question 26

What is a PM Quadtree? How do you construct it?

Answer 26

Polygonal-Map quadtree. Used to index points and lines (remember the intersection or meeting of two lines forms a vertex which IS A POINT! Also remember that the ends of a line segment ARE BOTH POINTS! or (vertices))

The following is the criteria for a PM1 Quadtree!

1) create bounding square around all lines and points
2) split the square into 4 equal sub-regions
3) if a sub-region falls into one of the following categories:
-it contains 1 vertex and only the partial line segments that form that vertex
-it contains just one partial line segment (neither of the endpoints)
-it’s completely empty
index that region with a value
4) if the sub-region contains 2 or more points, divide that sub-region into 4 equal sub-regions
5) continue this process of partitioning the sub-region into 4s until all sub-regions meet the criterion in (3)
6) To construct the tree, each indexed region should be a leaf node. The depth of a given leaf should be equal to the number of recursive partitions required to satisfy (3) (if we presume the root is at depth of 1)

Question 27

What is z-ordering? How is it accomplished?

Answer 27

z-ordering (or bit-interleaving is a technique for mapping spatial objects into a 1-d space that can be indexed by standard techniques (like a B-tree)

1) K represents the precision in bits
2) generate a 2^K x 2^K array space. The x and y axes should be numbered from 0 to the max value
[ex. if K=3, number x and y each from 000 to 111]
3) a value in this array space (a point (x,y))at x=aaa and y=bbb have a z-value of ‘ababab’
4) the values in the array space to which a spatial element is mapped can stored in a B-tree

Question 28

Decomposing shape over a grid into a minimal number of cells

Answer 28

The same bit interleaving pattern applies to this.

We can look at the precision of our grid as such. Each recursive partition of the space into 4 equal sub-regions, adds 2 bits to the z-value.

If a sub-region is partitioned into 4 smaller sub-regions each fully containing the shape of interest, then those 4 sub-regions can be indexed as one larger region represented by 2 fewer bits.
(It turns out the first 4 bits for each of the smaller sub-regions will be identical, so the last 2 bits can be dropped)