CS 599 – Spatial and Temporal DatabasesSpatial data types or algebras for database systems should satisfy the following criteria:Realm concepts:Realm for points, lines and regionsWhy use a realm as a basis for spatial data typesTransforming to a realmA problem and a solutionA solutionA formal definition of realm based SDT’ sLayer 1: Robust geometric primitivesLayer 1 Continued:Realm based structuresSlide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Realm based Spatial data typesExamples of Spatial valuesSecond order signatureSlide 24The type of a partitionThe object model interfaceObject model interface conceptsConcept for embedding ROSE algebra into DBMS query langThe Rose algebra: Robust spatial extensionSpatial predicatesOperators returning Spatial data type valuesSpatial operators returning numbersSpatial operators on Sets of objectsIntegrating with a DBMS query languageExample queryConclusionCS 599 – Spatial and Temporal DatabasesRealm based Spatial data types:The Rose AlgebraRalf Hartmut GutingMarkus SchneiderSpatial data types or algebras for database systems should satisfy the following criteria: •Generality: Geometric objects used as SDT values should be as general as possible. The domains of data types points, lines and region should be closed under union, intersection and difference.•Rigorous definition: The semantics of SDT ’s, the possible values for the types and the functions associated with the operations, must be defined formally to avoid ambiguities.•Finite resolution : The formal definitions must take into account the finite representations available inside computers•Treatment of geometric consistency: The definition of SDT ’s must enforce geometric consistency •General object model interface: SDT definition should be based on abstract interface to the DBMS data modelRealm concepts:•A realm is a set of points and non intersecting lines segments over a discrete domain that is a grid.•Values of spatial data types can be composed from the objects present in a realm.Realm for points, lines and regionsRegions : A, BLines : CPoints : DWhy use a realm as a basis for spatial data types•It enforces geometric consistency of related spatial objects, For example, the common part of the borders of countries A and B is exactly the same for both objects.•It guarantees nice closure properties for computation with spatial databases•Shields geometric consistency in query processing from numeric correctness and robustness problemsTransforming to a realmMove the intersection point to the nearest point on the grid.Application data at the lowest level of abstraction can be viewed as a set of points and intersecting line segments.A problem and a solutionError in resolving the point of intersectionA solutionDefine an envelope as a collection of grid points that are immediately above, below or on the lineA formal definition of realm based SDT’ sIt is organized as a series of layers•Layer 1: Robust geometric primitives•Layer 2: Realms and realm based primitives•Layer 3: Spatial algebra primitives•Layer 4: Rose operationsLayer 1: Robust geometric primitives•Consists of a finite discrete space N X N •Points and line segments over this space•Simple predicates and operations over them•Defines an N point and an N segment• Primitives such as ‘meet’, ’overlap’, ’intersect’, ’disjoint’, ’on’, ‘in’ and ‘intersection’ are defined.Layer 1 Continued:We define a Realm over N•It represent a finite, user-defined set of points and non-intersecting line segments over a discrete domain.•We define R points and R segments for the realm•We have an added restriction over N•R segments don’t intersect and they don’t overlapRealm based structures•An R cycle is a cycle in the graph interpretation of a realm•It is a set of R segmentsRelations between a N point p and R cycle c• p on c, p in c, p out c• c partitions the set of all N points into Pin(c ) Pon(c ) Pout(c )Realm based structuresRelations between two cycles c1 and c2Possible relationships between two R cyclesRealm based structuresC1 and C2 adjacentC1 and c2 meetc1c2Realm based structuresWays an R segment s can lie within an R cycle cWays an R point p can lie within an R cycle cRealm based structuresAn R face f, consists of a cycle c and a possibly empty set of R cycles h such that•All cycles in h are edge-inside c•All cycles in h are edge-disjoint with respect to each other•Segments in f can either form a cycle c or one of the cycles in h and no other cycle •This is necessary in order to achieve closure under operationsRealm based structuresRealm based structuresRealm based structuresRealm based structuresAn R-block b connected sub graph in the graph interpretation of a realmRealm based Spatial data typesA flat view: A structured view:Examples of Spatial valuesSecond order signatureROSE algebra is a system of spatial data types together with operations between these types. Many of the operations are applicable to several types. Hence we need a framework and notations to describe polymorphic operations. A system of several sets and functions between these sets is called a many sorted algebraA many sorted signature describes the syntactic aspect of a many sorted algebraIt consists of two sets of symbols called sorts and operatorsSecond order signature is a system of two coupled many sorted signatures where the top level offers kinds as sorts and type constructors as operators.Second order signatureA second, bottom level signature uses the types defined by the top level signature as sorts.The type of a partitionThe partition is a disjoint subdivision of the plane into regions with associated attributes.•We would like to test conditions such as adjacency or overlayThe kind regions area-disjoint contains all types whose carriers are sets of regions values such that any two distinct values of the type are area-disjoint.The object model interface•The SDT definition should be based on an abstract interface to the DBMS data model. •There are basic concepts and operations in the object model that are needed to define the ROSE algebra•There are constructs and notations needed to embed the ROSE algebra into the query language that is to use the ROSE algebraObject model interface concepts•Object types/ classes•Collection of objects•Functions for accessing values from objects•Data types int, real, bool•A pool of names•Object
View Full Document
Unlocking...