An Overview of the SAND spatial Database SystemWhat is SAND?IssuesSpatial DataStoring Spatial DataSpatial IndexingQuadtreeSAND system requirementsSAND KernelSlide 10Open Table Storage modelTable TypesTable typesAttribute typesPowerPoint PresentationSAND InterpreterSlide 17SAND BrowserConclusionsSlide 20Spatial QueriesAn Overview of the SAND spatial Database SystemClaudio EsperancaHanan SametPresented ByGautam ShanbhagWhat is SAND?SAND=Spatial + Nonspatial data.Spatial Data=points,lines,regions… example: rivers,city…Nonspatial Data=height,name.. example: city-name…Issues As spatial and nonspatial data are intimately connected a number of issues exist.One issue is how to obtain an answer to a queryExample:Find all cities within 100 miles of mississippi river having population greater than XThere are number of possible query plans..If x=small 1st spatial then nonspatial queryingElse if x=large 1st non-spatial then spatial queryingSpatial DataWhen Queries involve the space occupied by the data then we need to be able to retrieve data based on some spatial properties which are not explicitly stored in a database.Problem of storing spatial properties in databaseVolume of information is too highCost of preprocessing it is too highType of queries is not known beforehandIt is reasonable to compute queries on the fly if the spatial data is stored in an appropriate mannerStoring Spatial DataIn order to deal with proximity and range queries,the data must be sorted.Data is sorted on the space occupied by the dataConventional DBMS use other keys such as distance from a location to sort the data.This is useless for spatial data.Spatial IndexingR-treeBucket the data from MBRGrouped by hierarchy(proximity)Stored into structure like B treeDrawback: In worst case we have to search entire databaseR+ treeDecompose space into disjoint cells which are mapped to bucketsPartitioning is arbitraryDrawback:Decomposition is data dependentUniform GridSpace is decomposed into blocks of uniform sizeIdeal for uniformly distributed dataQuadtreeSpace is decomposed by adapting to distribution of dataIdeal for arbitrarily distributed dataQuadtreeSAND system requirementsA database engine capable of storing and retrieving both conventional and spatial dataAccess methods suitable for indexing and sorting conventional and spatial dataA software library for computing spatial operations,such as distance between two pointsA GUI toolkit for displaying the queriesA way of combining these into query evaluation plansSAND KernelSAND adopts an extended relational modelSAND KernelTables are handled as regular disk files.Once a table is open, a memory buffer is created for holding one tuple which is read or written to the table.This is called the Tuple BufferAll data pertaining to a table is stored in a single file,except when attribute is a container attributeContainer attribute is stored in a separate file and a summary of it’s value and an identifier with its disk location is stored with the regular attributes.Attributes with complex spatial features are often stored using containers.Open Table Storage modelTable TypesAll open tables support a minimal common set of operators like open,close,get first tuple,get next tuple.There are 3 table types:Relations,Linear indices,Spatial IndicesRelations are tables supporting direct access by tuple id(tid)Goto tid may be used to jump to any existing tidLinear indices are implemented as B-trees.Tuples in a linear index are scanned by the order determined by their contentsSpatial indices are implemented as Quadtrees.The spatial indexing is designed to permit the full contents of the table as soon as possible.Table typesAttribute typesSAND implements common non-spatial types(int,float,string..) and also 2-D geometric types(point,line,segment,polygon..)Non-spatial attributes support the compare operator which is used to establish a total ordering among attribute values of same type.Spatial values support operators such as distance,intersect etc.Some spatial features support additional features like expand and coarsen.SAND InterpreterSAND Interpreter is implemented in Tcl which provides integration with tk a toolkit for graphical user interfaces.Most aspects of SAND can be controlled and programmed by means of commands to SAND interpreterThe system can be extended by writing new methods or strategies that are stored in a library of SAND scriptsThe interpreter can be viewed as the unifying element of the SAND systemSAND BrowserSAND browser provides GUI to the facilities of SANDVisualization is done by specifying two types of controls:scan order in which tuples are retrieved and an arbitrary selection predicate.Current implementations support only selections and semi spatial joins.SAND browser provides prompt visual feedback due to incremental query processing capabilitiesConclusionsSAND is an ongoing project and new features are being added.The table and attribute classes are being redesigned so that addition of new attribute or table does not require modification of interpreter command interface.A full featured query optimizer would be incorporated into SAND in the near future.SAND has been used as a prototype of an image database system.Spatial QueriesThe processing of spatial queries is supported by interpreter commands associated with spatial attributes and spatial indices.Spatial indices support ranking wrt a given spatial object.Ranking in SAND is performed incrementally.This means that once the parameters for a ranking operation are given,the first tuple is returned as soon as possible.Having computed the first k elements,to get the (k+1)st element we need not sort k+1 elements but we can start from the point at which we obtain the kth
View Full Document
Unlocking...