空间数据库课件：第三讲 空间查询与索引

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）一个最小凸多边形，点或在多边形边上或在其内部。空间查询类型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树索引空间索引网格索引网格索引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均匀网格索引算法计算机图形学中图元生成算法Grid Structures: Grid FileExtends fixed grid with arbitrary subdivision positions, accounting for point distribution网格排序与编码RowPeano-HilbertMortonSpiralCantor DiagonalRow-PrimeMorton CodeFrom WikipediaMorton CodeCode & Decod

9、e Algorithm:陈述彭等，地理信息系统概论，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逻辑模型基于关系模型，设计核心逻辑结构GeoSVDM数据检索基于空间位置与空间关系的视频检索拓扑关系运算；方位关系运算；空间分析运算检索对

17、象被检索对象PointPolylinePolygonFramePointEqual/Distance/DirectionBuffer/ContainsContainsVideoLineWithinEqual/Buffer/CrossCross/ContainsFOVPolygonWithinCross/WithinContains/Within/Intersect基于空间位置与空间关系的视频检索方法检索与点q的距离小于d、且q在场景内的视频对象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数据检索基于线性参照系统的视频检索：根据点线事件检索检索某一道路上的视频片段与视频帧检索某一点处的视频帧与视频片段检索两点间的视频片段与视频帧基于点事件检索给定路径l上点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