Spatial Queries

 

First we describe some very basic spatial queries and then we will define relatively complex queries. One or more basic queries may be issued to answer these complex queries. Let $A$ and $B$ be two multidimensional spatial data objects (points, lines or regions), below we define some very basic spatial queries.

• LENGTH($A$ ). Return the length of a spatial object (line) $A$ .
• AREA($A$ ). Return the area of any 2D region $A$ .
• CENTROID($A$ ). Return the centroid of a spatial object $A$ . Centroid of an $n$ -dimensional object is the intersection of all hyperplanes that divide it into two parts of equal moment about the hyperplane. Informally, it is the ``average" of all points of $A$ .
• DISTANCE($A,B$ ). Find the distance between $A$ and $B$ . If $A$ and/or $B$ are not points, the distance definitions may be needed to be defined by the user. For example, possible definitions of distance between the two objects may be the minimum or maximum distance between them. Some other definition can also be applied. For example, find the distance between the centroids of the two objects.
• EQUALS($A,B$ ). If $A$ and $B$ have same spatial extent, return true.
• DISJOINT($A,B$ ). Return true if $A$ and $B$ are disjoint (they do not have any point in common).
• INTERSECTS($A,B$ ). Return true if $A$ and $B$ intersect each other. Note that this is exactly opposite operation to the disjoint operation.
• CONTAINS($A,B$ ). If the object $B$ is fully contained in $A$ , return true.

Note that for all of the above queries, the database system does not need to access any other object from the spatial index. These operations involve geometrical computation based on the information of the two spatial objects $A$ and $B$ . Next we briefly describe the queries that are more advanced and in order to answer these queries, the database system may need to traverse spatial indexes or it may need to call few of the basic operations described above.

1. Spatial Range Query($Q,dist$ ). Find all the objects that lie within a given distance $dist$ from the query object $Q$ . In other words, find all objects $X$ such that DISTANCE($Q,X$ )$\leq dist$ . For example, find all the restaurants that are within $10$ km from my current location.
2. Containment Query($Reg$ ). Find all the data objects that lie within the query region $Reg$ . Formally, return all the objects $X$ for which CONTAINS($Reg,X$ ) returns true. For example, find all the aeroplanes that are currently in New York.
3. Exact Match Query($Q$ ): Find all objects that have same spatial extent as the object $Q$ has. More specifically, find all the spatial objects $X$ for which EQUALS($Q,X$ ) returns true. Consider, for an example, a query may be issued to find a house that has same structure as my house.
4. Nearest Neighbor Query($Q$ ). Find the closest object to the query object $Q$ . The problem may also be extended to $k$ nearest neighbor ($k$ NN) query, that is to find $k$ closest objects to the query object. More specifically, a $k$ nearest neighbor query is to find a set of objects $R$ that contains $k$ objects such that for all $A\in R$ and for all other objects $B$ , $DISTANCE(Q,A)\leq DISTANCE(Q,B)$ . Note that the answer may change depending on the distance definition. Fig.  illustrates this. The nearest neighbor of $A$ is $B$ if the distance between two points is defined as the minimum distance between them. If the distance is defined as the maximum distance between the two objects, $C$ becomes the nearest neighbor of $A$ .

   Figure: Effect of Different Distance Definitions on Nearest Neighbors
   One example of such queries is to find $10$ closest gas stations to my current location. Also note that other metrics than Euclidean distance may also be used. In above example, the road distance may be used to find the nearest neighbors.

5. Spatial Join Query($R,S$ ). Let $R$ and $S$ be two sets of objects, a spatial join query is to find object pairs from these sets so that they satisfy some specified join predicate. The examples of possible join predicates may include INTERSECTS, DISJOINT, DISTANCE and CONTAINS operations defined above. An example of such queries is to find all hotel-cinema pairs so that distance between them is less that $1$ km.