空間數(shù)據(jù)庫課件：第三講 空間查詢與索引

1、第三講 空間查詢與索引Data retrievalTo retrieve data from a databases we may perform a query:Retrieve names and addresses of all opencast coal mines in StaffordshireData may be retrieved by a simple look up and matchRetrieve names and addresses of all employees of Wedgwood Pottery who earn more than half the s

2、um earned by the managing directorNumerical comparisonSpatial data retrievalQuery: is there any correlation between:The location of vehicle accidents (as recorded on a hospital database); andDesignated “accident black spots” for the area?Satisfying this query will require the integration of both spa

3、tial and non-spatial informationPerformanceSpatial data is notoriously large and often hierarchically structuredGeospatial data is often embedded in the Euclidean plane, therefore spatial storage structures and access methods are required空間查詢策略 Processing a spatial query QFilter step : find a supers

4、et S of object in answer to QUsing approximate of spatial data type and operatorRefinement step : find exact answer to Q reusing a GIS to process SUsing exact spatial data type and operation空間查詢策略Approximate Spatial Data typesApproximating spatial data typesMinimum bounding rectangle/box (MBR or MBB

5、)approximates line string, polygon, MBRs are used by spatial indexes, e.g. R-treeAlgorithms for spatial operations MBRs are simple凸包（Convex Hull）一個(gè)最小凸多邊形，點(diǎn)或在多邊形邊上或在其內(nèi)部?？臻g查詢類型Point query: retrieve all records with spatial references located at a particular pointRange query: retrieve all records with

6、spatial references located within a given range (spatial ranges may be any shape, but are often rectangular)（M. Worboys)Non spatial query: Retrieve the point location of Trentham GardensSpatial point query: Retrieve any site at location (37, 43)Spatial range query: Retrieve any site in the rectangle

7、 defined by (20, 20)(40, 50)Example空間查詢特征B樹索引空間索引網(wǎng)格索引網(wǎng)格索引Grid Structures: Fixed GridPartition of planar region into equal sized cellsPoints sharing the same cell (bucket) are stored togetherImproves range query performancePartition size depends on: Number of points; and Magnitude of average range qu

8、ery.Poor performance with non-uniform point distribution均勻網(wǎng)格索引算法計(jì)算機(jī)圖形學(xué)中圖元生成算法Grid Structures: Grid FileExtends fixed grid with arbitrary subdivision positions, accounting for point distribution網(wǎng)格排序與編碼RowPeano-HilbertMortonSpiralCantor DiagonalRow-PrimeMorton CodeFrom WikipediaMorton CodeCode & Decod

9、e Algorithm:陳述彭等，地理信息系統(tǒng)概論，P77R樹R樹R樹R樹R樹R樹Spatial Query with SQL Simple SQL SELECT_FROM_WHERE examplesSpatial analysis operations Unary operator: AreaBinary operator: DistanceBoolean Topological spatial operations - WHERE clauseTouchCrossUsing spatial analysis and topological operationsBuffer, overla

10、pFunction From PostGISDistance(geometry, geometry) : numberEquals(geometry, geometry) : booleanDisjoint(geometry, geometry) : booleanIntersects(geometry, geometry) : booleanTouches(geometry, geometry) : booleanCrosses(geometry, geometry) : booleanOverlaps(geometry, geometry) : booleanContains(geomet

11、ry, geometry) : booleanLength(geometry) : numberArea(geometry) : numberCentroid(geometry) : geometryUsing spatial operation in SELECT clauseQuery: List the name, population, and area of each country listed in the Country table.SELECT C.Name,C.Pop, Area(C.Shape)AS Area” FROM Country CNote: This query

12、 uses spatial operation, Area().Note the use of spatial operation in place of a column in SELECT clause.Using spatial operator DistanceQuery: List the GDP and the distance of a countrys capital city to the equator for all countries.SELECT Co.GDP, Distance(Point(0,Ci.Shape.y),Ci.Shape) AS DistanceFRO

13、M Country Co,City CiWHERE Co.Name = Ci.Country AND Ci.Capital =Y Using Spatial Operation in WHERE clauseQuery: Find the names of all countries which are neighbors of the United States (USA) in the Country table.SELECT C1.Name AS Neighbors of USAFROM Country C1,Country C2WHERE Touch(C1.Shape,C2.Shape

14、)=1 AND C2.Name =USA Note: Spatial operator Touch() is used in WHERE clause to join Country table with itself. This query is an example of spatial self join operation.Spatial Query with multiple tablesQuery: For all the rivers listed in the River table, find the countries through which they pass.SEL

15、ECT R.Name, C.NameFROM River R, Country CWHERE Cross(R.Shape,C.Shape)=1Note: Spatial operation “Cross” is used to join River and Country tables. This query represents a spatial join operation.Example Spatial QueryBuffer and OverlapQuery: The St. Lawrence River can supply water to cities that are wit

16、hin 300 km. List the cities that can use water from the St. Lawrence.SELECT Ci.NameFROM City Ci, River RWHERE Overlap(Ci.Shape, Buffer(R.Shape,300)=1 AND R.Name =St.Lawrence Note: This query uses spatial operation of Buffer.GeoSVDM邏輯模型基于關(guān)系模型，設(shè)計(jì)核心邏輯結(jié)構(gòu)GeoSVDM數(shù)據(jù)檢索基于空間位置與空間關(guān)系的視頻檢索拓?fù)潢P(guān)系運(yùn)算；方位關(guān)系運(yùn)算；空間分析運(yùn)算檢索對

17、象被檢索對象PointPolylinePolygonFramePointEqual/Distance/DirectionBuffer/ContainsContainsVideoLineWithinEqual/Buffer/CrossCross/ContainsFOVPolygonWithinCross/WithinContains/Within/Intersect基于空間位置與空間關(guān)系的視頻檢索方法檢索與點(diǎn)q的距離小于d、且q在場景內(nèi)的視頻對象Select FrameID, VID, RectFrame, SVideo from Frame, Video, FramePoint where d

18、istance(q.Geometry,FramePoint.FPoint)=d and (abs(azimuth(FramePoint.FPoint,q.Geometry)-FramePoint.FYaw)=0.5*) and (Frame.FrameID=FramePoint.FrameID) and (Frame.VID=Video.VID)GeoSVDM數(shù)據(jù)檢索基于線性參照系統(tǒng)的視頻檢索：根據(jù)點(diǎn)線事件檢索檢索某一道路上的視頻片段與視頻幀檢索某一點(diǎn)處的視頻幀與視頻片段檢索兩點(diǎn)間的視頻片段與視頻幀基于點(diǎn)事件檢索給定路徑l上點(diǎn)q處的視頻對象Select FrameID,RectFrame,VID,SVideo from PointEvents,Frame,Video,(Select Route from Route where RID=l.RID) r where(PointEvents.RID=l.RID) and (abs(Measure(q,r.Route) -PointEvents.MP)=d) and (PointEven