3
Querying Spatial Data

This chapter describes how the structures of a Spatial Cartridge layer are used to resolve spatial queries and spatial joins. For the sake of clarity, the examples all use fixed-size tiling.

3.1 Query Model

Spatial Cartridge uses a two-tier query model to resolve spatial queries and spatial joins. The term is used to indicate that two distinct operations are performed in order to resolve queries. The output of both operations yields the exact result set.

The two operations are referred to as primary and secondary filter operations.

The primary filter permits fast selection of a small number of candidate records to pass along to the secondary filter. The primary filter uses approximations in order to reduce computational complexity and is considered a lower cost filter.
The secondary filter applies exact computational geometry to the result set of the primary filter. These exact computations yield the final answer to a query. The secondary filter operations are computationally more expensive, but they are only applied to the relatively small result set from the primary filter.

Figure 3-1 illustrates the relationship between the primary and secondary filters.

Figure 3-1 Query Model

Spatial Cartridge uses a spatial index to implement the primary filter. This is described in detail in following sections.

A function used as a secondary filter is SDO_GEOM.RELATE(), which determines the spatial relationship between two given geometries, such as whether they touch, overlap, or if one is inside the other.

Spatial Cartridge does not require the use of both the primary and secondary filters. In some cases, just using the primary filter is sufficient. For example, a zoom feature in a mapping application queries for data that overlaps a rectangle representing visible boundaries. The primary filter very quickly returns a superset of the query. The mapping application can then apply clipping routines to display the target area.

3.2 Spatial Data Model

An important concept in the spatial data model is that each element is represented in the <layername>_SDOINDEX table by a set of exclusive and exhaustive tiles. This means that the tiles fully cover the object (exhaustive) and that no tiles overlap each other (exclusive).

Consider the following layer containing several objects in Figure 3-2. Each object is labeled with its SDO_GID. The relevant tiles are labeled with `Tn'.

Figure 3-2 Tessellated Layer with Multiple Objects

The Spatial Cartridge layer tables would have the following information stored in them for these geometries as shown in Table 3-1, Table 3-2, and Table 3-3.

SDO_ORDCNT (number)	SDO_LEVEL (number)	SDO_NUMTILES (number)
4	2	NULL

SDO_GID (number)	SDO_ESEQ (number)	SDO_ETYPE (number)	SDO_SEQ (number)	SDO_X1 (number)	SDO_Y1 (number)	SDO_X2 (number)	SDO_Y2 (number)
1013	0	3	0	P1(X)	P1(Y)	P2(X)	P2(Y)
1013	0	3	1	P2(X)	P2(Y)	P3(X)	P3(Y)
1013	0	3	2	P3(X)	P3(Y)	P4(X)	P4(Y)
1013	0	3	3	P4(X)	P4(Y)	P5(X)	P5(Y)
1013	0	3	4	P5(X)	P5(Y)	P6(X)	P6(Y)
1013	0	3	5	P6(X)	P6(Y)	P7(X)	P7(Y)
1013	0	3	6	P7(X)	P7(Y)	P8(X)	P8(Y)
1013	0	3	7	P8(X)	P8(Y)	P1(X)	P1(Y)
1013	1	3	0	G1(X)	G1(Y)	G2(X)	G2(Y)
1013	1	3	1	G2(X)	G2(Y)	G3(X)	G3(Y)
1013	1	3	2	G3(X)	G3(Y)	G4(X)	G4(Y)
1013	1	3	3	G4(X)	G4(Y)	G1(X)	G1(Y)
501	0	3	0	A1(X)	A1(Y)	A2(X)	A2(Y)
501	0	3	1	A2(X)	A2(Y)	A3(X)	A3(Y)
501	0	3	2	A3(X)	A3(Y)	A4(X)	A4(Y)
501	0	3	3	A4(X)	A4(Y)	A1(X)	A1(Y)
1243	0	3	0	B1(X)	B1(Y)	B2(X)	B2(Y)
1243	0	3	1	B2(X)	B2(Y)	B3(X)	B3(Y)
1243	0	3	2	B3(X)	B3(Y)	B1(X)	B1(Y)
12	0	2	0	D1(X)	D1(Y)	D2(X)	D2(Y)
61	0	3	0	C1(X)	C1(Y)	C2(X)	C2(Y)
61	0	3	1	C2(X)	C2(Y)	C3(X)	C3(Y)
61	0	3	2	C3(X)	C3(Y)	C4(X)	C4(Y)
61	0	3	3	C4(X)	C4(Y)	C5(X)	C5(Y)
61	0	3	4	C5(X)	C5(Y)	C1(X)	C1(Y)

SDO_GID (number)	SDO_CODE (raw)
1013	T1
1013	T2
1013	T3
1013	T4
501	T2
501	T7
1243	T3
1243	T4
1243	T5
1243	T6
12	T3
12	T4
61	T8
61	T9

Table 3-1 <layername>_SDOLAYER

SDO_ORDCNT (number) SDO_LEVEL (number) SDO_NUMTILES
(number)

4

2

NULL

Table 3-2 <layername>_SDOGEOM

SDO_GID (number) SDO_ESEQ (number) SDO_ETYPE (number) SDO_SEQ (number) SDO_X1 (number) SDO_Y1 (number) SDO_X2 (number) SDO_Y2 (number)

1013

0

3

0

P1(X)

P1(Y)

P2(X)

P2(Y)

1013

0

3

1

P2(X)

P2(Y)

P3(X)

P3(Y)

1013

0

3

2

P3(X)

P3(Y)

P4(X)

P4(Y)

1013

0

3

3

P4(X)

P4(Y)

P5(X)

P5(Y)

1013

0

3

4

P5(X)

P5(Y)

P6(X)

P6(Y)

1013

0

3

5

P6(X)

P6(Y)

P7(X)

P7(Y)

1013

0

3

6

P7(X)

P7(Y)

P8(X)

P8(Y)

1013

0

3

7

P8(X)

P8(Y)

P1(X)

P1(Y)

1013

1

3

0

G1(X)

G1(Y)

G2(X)

G2(Y)

1013

1

3

1

G2(X)

G2(Y)

G3(X)

G3(Y)

1013

1

3

2

G3(X)

G3(Y)

G4(X)

G4(Y)

1013

1

3

3

G4(X)

G4(Y)

G1(X)

G1(Y)

501

0

3

0

A1(X)

A1(Y)

A2(X)

A2(Y)

501

0

3

1

A2(X)

A2(Y)

A3(X)

A3(Y)

501

0

3

2

A3(X)

A3(Y)

A4(X)

A4(Y)

501

0

3

3

A4(X)

A4(Y)

A1(X)

A1(Y)

1243

0

3

0

B1(X)

B1(Y)

B2(X)

B2(Y)

1243

0

3

1

B2(X)

B2(Y)

B3(X)

B3(Y)

1243

0

3

2

B3(X)

B3(Y)

B1(X)

B1(Y)

12

0

2

0

D1(X)

D1(Y)

D2(X)

D2(Y)

61

0

3

0

C1(X)

C1(Y)

C2(X)

C2(Y)

61

0

3

1

C2(X)

C2(Y)

C3(X)

C3(Y)

61

0

3

2

C3(X)

C3(Y)

C4(X)

C4(Y)

61

0

3

3

C4(X)

C4(Y)

C5(X)

C5(Y)

61

0

3

4

C5(X)

C5(Y)

C1(X)

C1(Y)

Table 3-3 <layername>_SDOINDEX

SDO_GID (number) SDO_CODE (raw)

1013 T1

1013 T2

1013 T3

1013 T4

501 T2

501 T7

1243 T3

1243 T4

1243 T5

1243 T6

12 T3

12 T4

61 T8

61 T9

3.3 Spatial Query

A typical spatial query is to request all objects that lie within a defined fence or window. A query window is shown in Figure 3-3 by the dotted line box. A dynamic query window refers to a fence that is not defined in the database, but that must be defined and indexed prior to using it.

Figure 3-3 Tessellated Layer with a Query Window

3.3.1 Dynamic Query Window

If a query window does not already exist in the database, you must first insert it and create an index for it. Because not all Oracle users necessarily have insert privileges, Spatial Cartridge includes the SDO_WINDOW PL*SQL package. See Chapter 8, "Window Functions" for more information.

The SDO_WINDOW package is not automatically installed when you install Spatial Cartridge. This allows a DBA to control the schema under which this package operates. Choose an Oracle user who has insert privilege and compile the SDO_WINDOW package under that user. For example, you could choose the mdsys Oracle user:

sqlplus mdsys/password

SQL> @$ORACLE_HOME/md/admin/sdowin.sql 
SQL> @$ORACLE_HOME/md/admin/prvtwin.plb

After compiling, the routines are available for use. When you call a routine in this package, and the routine performs an INSERT operation, the insert will occur under the mdsys schema. Note that it is not a requirement to use the mdsys account. You can select any Oracle user with insert privileges.

If you need to perform other INSERT, UPDATE, or DELETE operations, and you cannot guarantee that the user of your application has those privileges, you can write your own PL*SQL package similar to the SDO_WINDOW package. You will have to compile your package under a user with the required database privileges.

3.3.2 Primary Filter

To resolve the window query shown in Figure 3-3, build a layer for the query fence if it is not already defined:

SQL> EXECUTE MDSYS.SDO_WINDOW.CREATE_WINDOW_LAYER (fencelayer, DIMNUM1, LB1, 
UB1, TOLERANCE1, DIMNAME1, DIMNUM2, LB2, UB2, TOLERANCE2, DIMNAME2);

Next, insert the ordinates for the query fence into the layer tables:

SQL> EXECUTE DBMS_OUTPUT.PUTLINE(TO_CHAR(MDSYS.SDO_WINDOW.BUILD_WINDOW_FIXED 
(comp_user, fencelayer, SDO_ETYPE, TILE_SIZE, X1, Y1, X2, Y2, X3, Y3, X4, Y4, 
X1, Y1)));

Query SDO_LEVEL from the <fencelayer>_SDOLAYER table to pass the correct TILE_SIZE to the SDO_WINDOW.BUILD_WINDOW_FIXED() procedure.

Now you can construct a query that joins the index of the query window to the appropriate layer index and determines all elements that have these tiles in common. The following SQL query form is used:

SELECT DISTINCT A.SDO_GID

FROM <layer1>_SDOINDEX A, <fencelayer>_SDOINDEX B

WHERE	 		A.SDO_CODE = B.SDO_CODE
  AND B.SDO_GID = {GID returned from SDO_WINDOW.BUILD_WINDOW_FIXED};

The result set of this query is the primary filter set. In this case, the result set is:

 { 1013,501,1243,12 }

3.3.3 Secondary Filter

The secondary filter performs exact geometry calculations of the tiles selected by the primary filter. The following example shows the primary and secondary filters:

SELECT SDO_X1, SDO_Y1, SDO_X2, SDO_Y2, SDO_X3, SDO_Y3, SDO_X4, SDO_Y4
FROM <layer1>_SDOGEOM,
(
SELECT SDO_GID GID1
   FROM (
          SELECT DISTINCT A.SDO_GID
             FROM <layer1>_SDOINDEX A,
                  <fencelayer>_SDOINDEX B
             WHERE A.SDO_CODE = B.SDO_CODE    
              AND B.SDO_GID = {GID returned from SDO_WINDOW.BUILD_WINDOW_FIXED}

     
         )
   WHERE SDO_GEOM.INTERACT('<layer1>', GID1, '<fence>', 1) = 'TRUE'
   )
WHERE SDO_GID = GID1;

This query would return all the geometry IDs that lie within or overlap the window. In this example, the results of the secondary filter would be:

{1243,1013}

The example in this section uses the SDO_GEOM.INTERACT() secondary filter. Both the INTERACT() and RELATE() secondary filters are overloaded functions. For better performance, use the versions that explicitly list the coordinates of the query window whenever possible. See Chapter 7, "Geometry Functions" for details on using these functions.

3.4 Spatial Join

A spatial join is the same as a regular join except that the predicate involves a spatial operator. In Spatial Cartridge, a spatial join takes place between two layers; specifically, two <layername>_SDOINDEX tables are joined.

Spatial joins can be used to answer questions such as, "which highways cross national parks?"

This query could be resolved by joining a layer that stores national park geometries with one that stores highway geometries.Figure 3-4 illustrates how the join would be accomplished for this example.

Figure 3-4 Spatial Join of Two Layers

The PRIMARY filter would identify pairs of park GIDs and highway GIDs that cross in the index. The query that performs the primary filter join (assuming fixed-size tile indexing) is as follows:

SELECT DISTINCT A.SDO_GID,B.SDO_GID 
     FROM PARKS_SDOINDEX A, HIGHWAYS_SDOINDEX B 
     WHERE A.SDO_CODE = B.SDO_CODE

The result set of the primary filter must be passed through the secondary filter to get the exact set of parks/highways GID pairs that cross. The full query is shown in the following example:

Suppose the original query had asked, "which 4-lane highways cross national parks?" You could modify the preceding SQL statement to join back to the HIGHWAYS table where HIGHWAYS.WIDTH=4. This combination of spatial and relational attributes in a single query is one of the essential reasons for using Spatial Cartridge.

3 Querying Spatial Data