= Brief introduction to ADBMS ®@ Advance DBMS e@ NOSQL © Parallel DB i cari © Distributed DB @ Cloud DB © Spatial DB @ Multimedia DB @ Mobile DB CAT 2 Dr. [Link], VIT Vellore CS12004 Advance DBMS 1 Database System Concepts - 6 Edition 254 ‘@Silberschatz, Korth and SudarshanNOSQL DB @ Non-relational or Not only SQL DB Ability to handle large volume of unstructured data NOSQL DB are more scalable(Horizontal scaling) and provides high performance Flexible schema Geographically distributed architecture High availability (data replication) Supports CAP theorem Some NOSQL DB’s © Google — Big Table @ Amazon — Dynamo DB @ Facebook — Cassandra Dr SVengadesa OBO CC. E$12004 Advance DBMS 2 Database System Concepts - 6" Edition 25.2 ‘eSilberschatz, Korth and SudarshanDistributed DB B® A distributed database is a collection of multiple interconnected databases, which are spread physically across various locations that communicate via a computer network. B Distributed DBMS: It is used to create, retrieve, update and delete distributed databases. B® Advantages: © Modular Development, More Reliable, Better response @ Homogenous vs Heterogenous DB ® Data replication: Process of storing separate copies of the database at two of more sites © Fully Vs Partial Vs No replication @ Data Fragmentation: Task of dividing a table into a set of smaller tables (fragments) © Horizontal, vertical, and hybrid Dr. [Link], VIT Vellore C812004 Advance DBMS 3 Database System Concepts - 6” Edition 253 Silberschatz, Korth and SudarshanParallel DB ‘stem seeks to improve the performance of the system through parallelizing concept. + A parallel database s * Multiple resources like CPUs and Disks used in parallel. * Operations are performed simultaneously; Not like serial processing. + Advantages: + Performance Improvement » High availability Proper resource utilization + Increase Reliability Speed-Up: Adding more resources results in proportionally less running time for a fixed amount of data. Scale-Up: If resources are increased in proportion to an increase in data/problem size, the overall time should remain constant 3 main architectures for parallel DBMSs. ‘Ar10 MB/s 41000 x pacallet Shared Memory ee, see, Shared Disk ear Pr Shared Nothing , | 1 | Dr. $.Vengadeswaran, VIT Vellore CS12004 Advance DBMS | Wi. cntbaae oft conontepeaton sea y UD ox.= Cloud DB + Cloud database facilitates you to store, manage, and retrieve their structured, unstructured data via a cloud platform. + Accessible over the Internet. + Cloud databases are also called a database as service (DBaaS) + Methods to run a database in a cloud 1. Virtual Machines 2. Database as-a-service (DBaaS) + The cloud database system makes information sharing simple and convenient + Lower costs: Generally, company provider does not have to invest in databases. + Automated: Cloud databases are enriched with a variety of automated processes such as recovery, failover, and auto-scaling. + Increased accessibility: access your Cloud DB from any location, anytime. * SQL Services - * NoSQL Services 12004 Advance A Dynam 255 “[Be] The picture can't be displayed Spatial and Geographic Databases Database System Concepts, 6'" Ed. ©Silberschatz, Korth and Sudarshan ‘See [Link] for conditions on re-use= Spatial and Geographic Databases @ Spatial databases store information related to spatial locations, and support efficient storage, indexing and querying of spatial data. @ Special purpose index structures are important for accessing spatial data, and for processing spatial join queries. @ Computer Aided Design (CAD) databases store design information about how objects are constructed E.g.: designs of buildings, aircraft, layouts of integrated-circuits H@ Geographic databases store geographic information (e.g., maps): often called geographic information systems or GIS. Dr. [Link], VIT Vellore CS12004 Advance DBMS 7 Database System Concepts - 6" Edition 257 ‘@Silberschatz, Korth and SudarshanRepresented of Geometric Information H@ Various geometric constructs can be represented in a database in a normalized fashion. @ Represent a line segment by the coordinates of its endpoints. @ Approximate a curve by partitioning it into a sequence of segments © Create a list of vertices in order, or © Represent each segment as a separate tuple that also carries with it the identifier of the curve (2D features such as roads). Closed polygons © List of vertices in order, starting vertex is the same as the ending vertex, or © Represent boundary edges as separate tuples, with each containing identifier of the polygon, or © Use triangulation — divide polygon into triangles De. [Link] polygon idensificrauithiadh of its triangles. 8 Database System Concepts - 6" Edition 258 ‘@Silberschatz, Korth and SudarshanRepresentation of Geometric Constructs 2 line segment “ LO (Ly, 6232) 1 3 triangle LA {(<1,y1), (&2,y2), 03,y3)) 1 2 2 3 polygon 1 {OcLy1), (x2,y2), (x3,y3), (x4,y4), (5,y5)} 5 4 2 3 ((XLy1), (x2,y2), (x3,y3), ID1} polygon 1 {(x1y1), (x3,y3), (x4,y4), ID1} {(xLy1), (x4,y4), (x5,y5), ID1} 5 4 object representation. Dr. [Link], VIT Vellore CSI2004 Advance DBMS 9 Database System Concepts - 6" Edition 259 ‘@Silberschatz, Korth and SudarshanPolygons flat, two-dimensional (2D) shape with straight sides that is fully closed (all the sides are joined up) eed perry cores Pere rr Perey ed Seer ct Regular Polygons «allsides are equal lengthand allintemal angles are equal ‘Examples of Irregular Polygons ‘anypolygon thatisnot regular. Convex Polygons Complex Polygons ee mene ‘greater than 180° greater than 160° All era Dr. [Link], VIT Vellore a 10 Database System Concepts - 6" Edition ‘@Silberschatz, Korth and Sudarshan= Spatial Data Examples ® Examples of non-spatial data = Names, phone numbers, email addresses of people © Examples of Spatial data = NASA satellites imagery - terabytes of data per day = Weather and Climate Data = Rivers, Farms, ecological impact = Medical Imaging © Exercise: Identify spatial and non-spatial data items in = A phone book Dr. [Link], VIT Vellore CS12004 Advance DBMS n Database System Concepts - 6" Edition 25.11 ‘@Silberschatz, Korth and SudarshanSpatial Queries vs Non-spatial Queries ® Non-spatial queries: List the names of all bookstore with more than ten thousand titles. List the names of ten customers, in terms of sales, in the year 2001 Where is Building 78? = Which courses are meeting in GP Building? ® Spatial Queries: = List the names of all bookstores with ten miles of Minneapolis List all customers who live in Tennessee and its adjoining states Which buildings are adjacent to the lake? = Which building is adjacent to @ /ake? Dr. $.Vengadeswaran, VIT Vellore CS12004 Advance DBMS R Database System Concepts - 6" Edition 25.12 ‘@Silberschatz, Korth and SudarshanApplication Domains (1) * Many important application domains have spatial data and queries. — Army field commander: Has there been any significant enemy troop movement since last night? — Insurance risk manager: Which homes are most likely to be affected in the next great flood on the Mississippi? — Medical doctor: Based on this patient's MRI, have we treated somebody with a similar condition ? — Molecular biologist: Is the topology of the amino acid biosynthesis gene in the genome found in any other sequence feature map in the database ? quasars. S — Astronomer: Find all blue galaxies within 2 arcmin of Applied Computing Lab CSI2004 Advance DBMS 25.13 Dr. [Link], VIT Vellore B Database System Concepts - 6" Edition ‘@Silberschatz, Korth and SudarshanSDBMS Example * Consider a spatial dataset with: — County boundary (dashed white line) — Census block - name, area, population, boundary (dark line) — Water bodies (dark polygons) — Satellite Imagery (gray scale pixels) * Storage ina SDBMS table: create table census_blocks ( name string, area float, population number, A boundary polyline ); Fig 1.2 SF Applied Computing Lab Dr. [Link], VIT Vellore CS12004 Advance DBMS rT) Database System Concepts - 6" Edition 25.14 ‘@Silberschatz, Korth and SudarshanModeling Spatial Data in + A row in the table census_blocks (Figure 1.3) * Question: Is Polyline datatype supported in DBMS? Boundary Payline (0,9), (0,1), (1,1), (1.0) Figure 1.3 Applied Computing Lab Dr. [Link], VIT Vellore CSI2004 Advance DBMS 15 Database System Concepts - 6* Edition 25.15 siiberschatz, Korth and SudarshanSpatial Data in Traditional Databases ¢ Traditional relational DBMS — Support simple data types, e.g. number, strings, date — Modeling Spatial data types is tedious + Example: Figure 1.4 shows modeling of polygon using numbers — Three new tables: polygon, edge, points + Note: Polygon is a polyline where last point and first point are same — A simple unit square represented as 16 rows across 3 tables — Simple spatial operators, e.g. area(), require joining tables — Tedious and computationally inefficient 8 stop Dr. [Link], VIT Vellore CS12004 Advance DBMS 16 Database System Concepts - 6" Edition 25.16 ‘@Silberschatz, Korth and SudarshanMapping “census_table” into a | Relational Database Fig 1.4 A Computing Lab Dr. [Link], VIT Vellore CS12004 Advance DBMS 7 Database System Concepts - 6" Edition 25.17 ‘@Silberschatz, Korth and SudarshanmaRepresentation of Geometric Information (Cont.) @ Representation of points and line segment in 3-D similar to 2-D, except that points have an extra z component @ Represent arbitrary polyhedra by dividing them into triangulating polygons. @ Alternative: List their faces, each of which is a polygon, along with an indication of which side of the face is inside the polyhedron. ( Atetrahedron has: ) 4 Faces 4 Vertices 6 Edges L Dr. [Link], VIT Vellore CS12004 Advance DBMS 18 Database System Concepts - 6" Edition 25.18 ‘@Silberschatz, Korth and SudarshanDesign Databases @ Represent design components as objects (generally geometric objects); the connections between the objects indicate how the design is structured. @ Simple two-dimensional objects: points, lines, triangles, rectangles, polygons. @ Complex two-dimensional objects: formed from simple objects via union, intersection, and difference operations. @ Complex three-dimensional objects: formed from simpler objects such as spheres, cylinders, and cuboids, by union, intersection, and difference operations. Dr. [Link], VIT Vellore CS12004 Advance DBMS 19 Database System Concepts - 6" Edition 25.19 ‘eSilberschatz, Korth and SudarshanRepresentation of Geometric Constructs QO (a) Difference of cylinders (b) Union of cylinders @ Design databases also store non-spatial information about objects (e.g., construction material, color, etc.) @ Spatial integrity constraints are important. © E.g., pipes should not intersect, wires should not be too close to each other, etc. Dr. [Link], VIT Vellore CS12004 Advance DBMS 20 Database System Concepts - 6" Edition 25.20 ‘@Silberschatz, Korth and SudarshanGeographic Data @ Raster data consist of bit maps or pixel maps, in two or more dimensions. @ Example 2-D raster image: satellite image of cloud cover, where each pixel stores the cloud visibility in a particular area. @ Additional dimensions might include the temperature at different altitudes at different regions, or measurements taken at different points in time. ™@ Design databases generally do not store raster data. Dr. [Link], VIT Vellore CS12004 Advance DBMS 21 Database System Concepts - 6" Edition 25.21 ‘@Silberschatz, Korth and SudarshanGeographic Data (Cont.) @ Vector data are constructed from basic geometric objects: points, line segments, triangles, and other polygons in two dimensions, and cylinders, spheres, cuboids, and other polyhedrons in three dimensions. ®@ Vector format often used to represent map data. © Roads can be considered as two-dimensional and represented by lines and curves. @ Some features, such as rivers, may be represented either as complex curves or as complex polygons, depending on whether theit width is relevant. © Features such as regions and lakes can be depicted as polygons. Dr. [Link], VIT Vellore CS12004 Advance DBMS 22 Database System Concepts - 6" Edition 25.22 ‘@Silberschatz, Korth and SudarshanApplications of Geographic Data @ Examples of geographic data © map data for vehicle navigation © distribution network information for power, telephones, water supply, and sewage M@ Vehicle navigation systems store information about roads and services for the use of drivers: © Spatial data: ¢.g., road/restaurant/gas-station coordinates © Non-spatial data: e.g., one-way streets, speed limits, traffic congestion H Global Positioning System (GPS) unit - utilizes information broadcast from GPS satellites to find the current location of user with an high accuracy ™@ increasingly used in vehicle navigation systems as well as utility maintenance applications. Dr. [Link], VIT Vellore CS12004 Advance DBMS 23 Database System Concepts - 6” Edition 25.23 Silberschatz, Korth and SudarshanSpatial Queries vs Non-spatial Queries ® Non-spatial queries: List the names of all bookstore with more than ten thousand titles. List the names of ten customers, in terms of sales, in the year 2001 Where is Building 78? = Which courses are meeting in GP Building? ® Spatial Queries: = List the names of all bookstores with ten miles of Minneapolis List all customers who live in Tennessee and its adjoining states Which buildings are adjacent to the lake? = Which building is adjacent to @ /ake? Dr. $.Vengadeswaran, VIT Vellore CS12004 Advance DBMS 24 Database System Concepts - 6" Edition 25.28 ‘@Silberschatz, Korth and SudarshanSpatial Queries @ Nearness queries request objects that lie near a specified location. @ Nearest neighbor queries, given a point or an object, find the nearest object that satisfies given conditions. @ Region queries deal with spatial regions. e.g., ask for objects that lie partially or fully inside a specified region. ® Queries that compute intersections or unions of regions. @& Spatial join of two spatial relations with the location playing the role of join attribute. Dr. $.Vengadeswaran, VIT Vellore CS12004 Advance DBMS 25 Database System Concepts - 6" Edition 25.25 ‘@Silberschatz, Korth and SudarshanSpatial Queries (Cont.) Spatial data is typically queried using a graphical query language; results are also displayed in a graphical manner. @ Graphical interface constitutes the front-end ®@ Extensions of SQL with abstract data types, such as lines, polygons and bit maps, have been proposed to interface with back-end. © allows relational databases to store and retrieve spatial information © Queries can use spatial conditions © queries can mix spatial and nonspatial conditions Dr. [Link], VIT Vellore CS12004 Advance DBMS 26 Database System Concepts - 6" Edition 25.26 ‘@Silberschatz, Korth and Sudarshan=a Applications of Spatial Data @ Computer graphics, games, movies @ Computer vision, street maps (google maps/google Earth) @ Human-computer interface design B Virtual reality @ Visualization etc.. Dr. [Link], VIT Vellore CS12004 Advance DBMS 27 Database System Concepts - 6" Edition 25.27 ‘eSilberschatz, Korth and Sudarshan= Geometric Objects Q Scalars: 1-d point © Point: location in d-dimensional space. d-tuple of scalars. P=(x1,x2,x3...,xd) ® Vectors: direction and magnitude (length) in that direction. B& Line: infinite in both directions @ y= mx + c [slope m, intercept c] @ In higher dimensions, any two points define a line. @ Ray: infinite in one direction ® Segment: finite in both directions ® Polygons: cycle of joined line segments Dr. [Link], VIT Vellore CS12004 Advance DBMS 28 Database System Concepts - 6" Edition 25.28 ‘eSilberschatz, Korth and SudarshanSpatial Indexing (Contd.) @ Spatial databases store information related to spatial locations, and support efficient storage, indexing and querying of spatial data. @ Indexing: It is an auxiliary file that makes more efficient to search a record in the data file. @ Primary Index © Clustering Index @ Secondary Index © Multilevel Indexing (B Tree, B+ Tree) Q How to create an index for spatial data? » Each cell is associated with one data pointer pointing to that data ———_— Dr. $.Vengadeswaran, VIT Vellore CS12004 Advance DBMS 29 Database System Concepts - 6" Edition 25.29 ‘@Silberschatz, Korth and SudarshanPR Quadtrees Dr. [Link], VIT Vellore Database System Concepts - 6" Edition CS12004 Advance DBMS 25.30 30 ‘@Silberschatz, Korth and Sudarshan= PR Quadtrees (Point-Region) ¢ Recursively subdivide cells into 4 equal-sized subcells until a cell has only one point in it. ¢ Each division results in a single node with 4 child pointers. ¢ When cell contains no points, add special “no-point” node. ¢ When cell contains 1 point, add node containing point + data associated with that point (perhaps a pointer out to a bigger data record). Dr. $.Vengadeswaran, VIT Vellore CS12004 Advance DBMS 31 Database System Concepts - 6" Edition 25.31 ‘@Silberschatz, Korth and Sudarshan=- PR Quadtrees Internal Nodes NW NE NW, SE e NE/ \sw e sw SE ° e eo °% Dr. [Link], VIT Vellore CSI2004 Advance DBMS: 32 Database System Concepts - 6" Edition 25.32 ‘@Silberschatz, Korth and Sudarshanas PR Quadtrees e a NW SE NE \SW Dr. [Link], VIT Vellore CS12004 Advance DBMS 33, Database System Concepts - 6" Edition 25.33 ‘eSilberschatz, Korth and Sudarshan= Insert in PR Quadtrees e insert(P): - find(P) - if cell where P would go is empty, then add P to it (change from to MM) - Ifcell where P would go has a point Q in it, repeatedly split until P is separated from Q. Then add P to correct (empty) cell. ¢ How many times might you have to split? unbounded in 1 Dr. $.Vengadeswaran, VIT Vellore CS12004 Advance DBMS 34 Database System Concepts - 6" Edition 25.34 ‘@Silberschatz, Korth and Sudarshan= Delete in PR Quadtrees e delete(P): find(P) If cell that would contain P is empty, return not found! Else, remove P (change gg to ). If at most 1 siblings of the cell has a point, merge siblings into a single cell. Repeat until at least two siblings contain a point. © Acell “hasa point” ifitis mg or@ . Dr. $.Vengadeswaran, VIT Vellore Database System Concepts - 6" Edition 25.35 CS12004 Advance DBMS 35 ‘@Silberschatz, Korth and Sudarshan‘Samet, Foundations of Multidimensional ‘and Metric Data Structures ‘Samet, Design and Analysis of Spatial Data Structures. Point Quadtree data structure foo |B 200m in/out Mode 522, 0) ‘Compiled on Oct 28, 2007 Dr. [Link], VIT Vellore CSI2004 Advance DBMS 36 Database System Concepts - 6" Edition 25.36 ‘@Silberschatz, Korth and Sudarshan= Features of PR Quadtrees ¢ Locations of splits don’t depend on exact point values (it is a partitioning of space, not of the set of keys) e Leaves should be treated differently that internal nodes because: - Empty leaf nodes are common, = Only leaves contain data ¢ Bounding boxes constructed on the fly and passed into the recursive calls. e Extension: allow a constant b > 1 points ina cell (bucket quadtrees) Dr. $.Vengadeswaran, VIT Vellore CS12004 Advance DBMS 37 Database System Concepts - 6" Edition 25.37 ‘eSilberschatz, Korth and Sudarshan= An Advantage of PR quadtrees ¢ Since partition locations don’t depend on the data points, two different sets of data can be stored in two separate PR quadtrees - The partition locations will be “the same” - Eg. a quadrant Q; in T1 is either the same as, a superset of, or a subset of any quadrant Q> in T2 - You cannot get partially overlapping quadrants - Recursive algorithms cleaner, e.g. Dr. $.Vengadeswaran, VIT Vellore CS12004 Advance DBMS 38 Database System Concepts - 6" Edition 25.38 ‘@Silberschatz, Korth and Sudarshan= Issues with PR Quadtrees ¢ Can be inefficient: - two closely spaced points may require a lot of levels in the tree to split them - Have to divide up space finely enough so that they end up in different cells © Generalizing to large dimensions uses a lot of space. - octtree = Quadtree in 3-D (each node has 8 pointers) Ind d=20=> dimensions, nodes will ~ each node 1 million has 2¢ children pointers! Dr. [Link], VIT Vellore CS12004 Advance DBMS: 39 Database System Concepts - 6" Edition 25.39 ‘@Silberschatz, Korth and Sudarshan2 Find in PR Quadtrees Dr. [Link], VIT Vellore CS12004 Advance DBMS 40 Database System Concepts - 6" Edition 25.40 ‘@Silberschatz, Korth and Sudarshan