Transcription
Review: DBMS ComponentsDatabase Management System ComponentsCMPT 454: Database Systems II – Advanced Queries (1)1 / 17
Research Topics in DatabasesSystem Oriented How to implement a DBMS?How to manage the data in the storage?How to construct the index structures for the data?How to implement the different SQL operators? Application Oriented What kind of database queries can be answered?What kind of index structures can be used to support thedatabase queries?What kind of techniques can be used to improved thedatabase queries? CMPT 454: Database Systems II – Advanced Queries (1)2 / 17
A Typical Database Research ProjectFind an interesting database research topic: e.g., an useful database queryNN querySkyline queryKeyword search query Design “efficient” and “effective” methods to answer the database queryIndex structure?Query answering algorithm?Speed-up techniques?Scalability?ImplementationAn executable demoHow to maintain the data? How to access data via a database API? How to construct indices?.Conduct experiments on a real datasetPublicationWrite a research paperPublish in major database conferences, e.g., SIGMOD, VLDB, ICDE, EDBT Apply for a patentStart-up / Commercial softwareCMPT 454: Database Systems II – Advanced Queries (1)3 / 17
Next to DiscussDatabase ResearchData Mining ResearchWeb Search and Information Retrieval ResearchCMPT 454: Database Systems II – Advanced Queries (1)4 / 17
Query Processing and AdvancedQueriesAdvanced Queries (1): SpatialDatabases and kd-Tree
Spatial Database ApplicationsGIS (geographic information system)applications (e.g., maps):Urban planning, route optimization, fire orpollution monitoring, utility networks, etcOther applications:VLSI design, CAD/CAM, model of humanbrain, etc.Traditional applications:Multi-dimensional recordsCMPT 454: Database Systems II – Advanced Queries (1)6 / 17
What is a Spatial Database?A SDBMS is a DBMSIt offers spatial data types/data models/query languageSupport spatial properties/operationsIt supports spatial data types in itsimplementationSupport spatial indexing, algorithms forspatial selection and joinCMPT 454: Database Systems II – Advanced Queries (1)7 / 17
Spatial Data RepresentationRaster model:Vector model:CMPT 454: Database Systems II – Advanced Queries (1)8 / 17
Spatial Data TypespointlineregionPoint : 2 real numbersLine : sequence of pointsRegion : area includedinside n-pointsCMPT 454: Database Systems II – Advanced Queries (1)9 / 17
Spatial Data RelationshipsTopological relationships:adjacent, inside, disjoint, etcDirection relationships:Above, below, north of, etcMetric relationships:“distance 100”And operations to express the relationshipsCMPT 454: Database Systems II – Advanced Queries (1)10 / 17
Spatial QueriesSelection queries: “Find all objects inside queryq”Inside: intersects, north, etc.Nearest Neighbor queries: “Find the closetobject to a query point q”KNN: k-closest objectsSkyline queries: find all skyline points which arey (latitude)not dominated by some others.x (longitude)CMPT 454: Database Systems II – Advanced Queries (1)11 / 17
Access MethodsPoint Access Methods (PAMs):Index methods for 2 or 3-dimensional points(kd-tree)Spatial Access Methods (SAMs):Index methods for 2 or 3-dimensionalregions and points (R-tree)CMPT 454: Database Systems II – Advanced Queries (1)12 / 17
PAM: The problemGiven a point set and a rectangular query, findthe points enclosed in the queryWe allow insertions/deletions onlineQueryCMPT 454: Database Systems II – Advanced Queries (1)13 / 17
Tree-based PAMsMost of tree-based PAMs are based on kdtreekd-tree is a main memory binary tree forindexing k-dimensional pointsLevels rotate among the dimensions,partitioning the space based on a value forthat dimensionkd-tree is not necessarily balancedCMPT 454: Database Systems II – Advanced Queries (1)14 / 17
kd-TreeAt each level we use a different dimensionx 5CByAx 5Ex 5y 6y 3Dx 6xCMPT 454: Database Systems II – Advanced Queries (1)15 / 17
kd-Tree ExampleX 3X 5X 7y 6y 5Y 6x 3x 8x 7Y 5y 2Y 2X 5X 8Each leaf node can hold up to 2 points.CMPT 454: Database Systems II – Advanced Queries (1)16 / 17
Spatial IndexingPoint Access Methods can index onlypoints. What about regions?Use the transformation technique and aPAMNew methods: Spatial Access MethodsSAMsR-tree and variationsCMPT 454: Database Systems II – Advanced Queries (1)17 / 17
A SDBMS is a DBMS It offers spatial data types/data models/ query language Support spatial properties/operations It supports spatial data types in its implementation Support spatial indexing, algorithms for spatial selection and join. CMPT 454: Database Systems II -Advanced Queries (1) 8 / 17
