diff options
Diffstat (limited to 'sem7/db')
| -rw-r--r-- | sem7/db/eksamnen.md | 334 |
1 files changed, 334 insertions, 0 deletions
diff --git a/sem7/db/eksamnen.md b/sem7/db/eksamnen.md new file mode 100644 index 0000000..2a6480b --- /dev/null +++ b/sem7/db/eksamnen.md @@ -0,0 +1,334 @@ + +# TODO + + - Lav opgave 2.3 i distributed thing + +# Nice Spatial SQL Commands + + - `ST_GeometryType(thing)` finds the type of `thing`. + - `ST_Boundary(thing)` finds the boundary of `thing`. There is probably a interior version too. + - `ST_DWithin(a, b, distance)` returns true if `a` and `b` are within `distance` of each other. + - `ST_MakeBox2D(a, b)` create a box from two points. + + +One can find nearest neighbour with: + +```sql +select l.*, +ST_Distance (l.geo , ST_Point (5, 5)) as dist +from landscape as l +order by dist +limit 5 +``` + +# Introduction Spatial Queries + +**Range queries** are the most simple, as we just query inside a square. +This is very similar to something like + +```sql +SELECT * WHERE salary BETWEEN 10 AND 20 +``` + +Only with range queries we often look in two dimensions instead of one. + +**Directional relationships** is stuff like north, west or south, and can the done with `ST_Azimuth`. +However this does not make much sense in 3D. + +## Topological Relationships + +We first define boundary and interior. +**Boundary** are the pixels that are adjendant to a pixel outside the object. +While **Interior** is the space inside the object not occupied by the boundary. + +If we consider two shapes, we can say that they either *intersects* and *disjoint*. +We they are disjoint we cannot really say more than that, but if they *intersect* they can either be + + - *equal* if their boundaries and interior are equal, + - *inside* if the one interior is completely inside the other, + - *contains* is the reverse of *inside* + - *adjendant* if their borders share pixels, but not their interior, + - *overlaps* if they share interior pixels, but they each have pixels which are not in the other. + +```sql +ST_Contains (b.geo , y.geo) +ST_Within (b.geo , y.geo) +ST_Touches (b.geo , y.geo) +ST_Equals (b.geo , y.geo) +ST_Overlaps (b.geo , y.geo) +``` + +## Points, Linestring and Polygons + +These are used to represent the different things in the 2d database. +This is nicely explained [here](https://help.arcgis.com/en/geodatabase/10.0/sdk/arcsde/concepts/geometry/shapes/types.htm). + +Points +: A single point represented by coordinates. It boundary is empty and the interior is just the point. + +Linestring +: A line between a sequence of at least two points. + Can either be closed, where the begin point is also the end. + The line between the points is the interior, and the boundary are the outer points. + +Polygon +: Define by an exterior closed linestring and zero og more interior closed linestrings. + The exterior ring must be defined against the clock and the interior with the clock, such that the right side of the linestring is always outside. + See #c6fd for a nice figure. + +# Spatial Database Indexing + +We can specify the indexing method in sql like this. + +```sql +-- Creation of the table +create table landscape ( +geo_name varchar (20) primary key , +geo geometry not null +); + +-- With B+ tree +create index landscape_geo_name +on landscape ( geo_name ); + +-- With R-tree, GIST, generalized search trees +create index landscape_geo +on landscape using gist (geo ); +``` + +## Space Filling Curves + +*Also refered to as SFC.* + +If is often more convenient to store points in a specific 1d ordering, as we can then use existing indexing methods. +However the spatial stuff we want to store and search is 2d. +Therefore we map this 2d data to 1d, making search and inserting much easier. + +We do this by splitting the 2d space into smaller chunks, and then we find a ordering of these chunks. +The ordering of the chunks is determined by a space filling curve, which there are many different. + +A good spacefilling curve is one where points that are close in 2d space, are also close to each other on the curve. + +However because we have many points in the same chunk, we can not know for sure whether they overlap just because they are in the same chunk. +This is therefore only used for finding candidates. + +Using space filling curves allows us to reuse the B+tree indexing structure, which is well supported by postgresql. +However they can also be combined with other quadtrees or R-trees which work in 2d by themselves. + +## Trees + +Here we will introduce *minimum-bounding rectangles* or MBRs, which is a axis aligned rectange. +These are used to give an estimate of an object, which can lead to false positives (but not false negatives). + +We will then insert those bounding boxes into a into nodes, with a maximum of M boxes per tree node. +When more than M nodes are to be inserted in a box we split it in two. + +Again when deleting we should combine nodes if they are smaller than `m * M`. +Here it's often hard to get the right clusterings of boxes, as we want to mimimize the deadspace. + +`m` is often `0.4` and `M` is often set according to page size etc. + +When searching we use a two step filtering process. +First we check fast intersections with boxes and then the expensive geometric intersection. + +What now refine R trees as *R+trees* which require that there is no overlap between the node regions. +We will therefore have to insert some objects twice. +However this eliminates the need to do multi-path searching. + +# Introduction to Parallel Databases + +Lets start with some important definitions. + +Distributed Database +: Software system that permits management of the distributed database and makes the distribution transparent to the user. +Scale-up +: Adding more CPU cores etc hardware. +Scale-out +: Adding more smaller machines and connecting them. +Throughput +: Time from query start to last row received. +Response Time +: Time from query start to first row received. + +There is a nice slide about transistency in this lecture. +It does not really make sense to repeat it here. + +## Performance + +When performing a query we have many choices for where to do this. +**Inter-query** is when we have many smaller queries that are performed in parallel, +while **intra-query** is a very large query that is queried concurrently. + +## Design of Distributed Database + +Often done in a *3-tier* architecture, with a client layer, application layer, and database server layer. +Each layer can then have many different interconnected computers, with communication to adjendant layers via a network. + +## Partitioning + +**Horizontal partitioning** (also called *sharding*) is when we have different sets of rows of the same table on different sites. +We therefore preserve the whole scheme at each site. +We can partition these in different ways: + + - **Range partitioning**, by partitioning on some column such as timestamps. + - **List partitioning** such as using *round-robin*. + - **Hash partitioning**. + +Here we should watch out for getting a *data-skew*, where data is partitioned unbalanced. +This could for example be if we partition on a name column. + +**Vertical partitioning** is where each site has each row, but the partitioning happens on the columns. +This allows for better compressions, but we must repeat primary key rows accross all sites for identification. + +We must be able to say something about partitioning. +Such as **completeness** which states that all rows in the originals, should still be present in at least one of the partitions. +Or **reconstruction** which states that the original table can be recovered by applying some operator to all partitions. +And lastly **disjointness** which states that the partitions should not share rows. + +# Just Parallel Databases (what) + +Scaling up as explained before, is often much harder. +This is also called *vertical scaling* as is associated with *tight coupling*. + +Scaling out is easier and often gives a more losely coupled thing, however this comes at the cost of complexity. +Scaling out is also called *horizontal scaling*. + +**Shared memory** is a architecture where we have a shared memory between processors. +Here each CPU can see the whole memory space, and they all run the same OS instance. +Often used for *inter-query parallelism* or *load balancing*. +However not very common for databases. + +**Shared disk** is very common for databases in cloud computing such as Amazon S3. +Here many processors, each with their own memory, shares a set of disks via an interconnect. +Therefore disks and CPU's can be shared independently. + +**Shared nothing :-(** very common with NoSQL. +Here many computers are connected with an interconnect and share nothing, such like *scale-out*. +This is harder to scale than shared-disk but can give better performance. + +**Symmetric algorithm** whether the processing of incomming tuples can be pipelined with own tuples. +See page 368 for a better explanation. + +## ACID and CAP + +ACID stands for + + - Atomicity + - Consistency + - Isolation + - Durability + +While CAP stands for + + - Consistent (same as in ACID) + - Always Available + - Partitioned + +With CAP we are only allowed to have two of the three *things*. + +## Amdahl's Law + +The more of our computation we can do in parallel, the better. +If we can do all of it (which is impossible) we get a linear grow in performance as we add more units. +However if we cannot it will have a curve down :-(. + +There is a nice formula for this in the slides, but i can try to write it here. + +```haskell +MaxSpeedUp seq p = 1 / (seq + ( (1-seq) / p)) +``` + +We are interested in parallising sorting and joining. +These operate on rows that are all over the place, and it is beneficial to do as much as possible on the device where stuff is stored, before sending it. + +# Summary of Parallel Databases + +This repeats some things in a nicer way. +I will just write what can be found in the slides, instead of repeating it. + + - Comparison between partitioning techniques, such as advantages of hash etc. + - Interquery parallism + + Multiple queries in parallel. Easiest to implement on shared-memory. + + - Intraquery parallism + + - **Intraoperation parallism** parallizes the execution of each operation in query. + - **Interoperation parallism** execute different query operations in parallel. + +# Intro Data Warehousing and Multidimensional Modeling + +Reasons for data warehousing + + - Often data quality is bad (different formats, inconsistent data) + - Data is not permanent (deleted after 30 days, or overwritten by changes) + +This makes it hard to answer more bussiness oriented queries. + +If we consider the example of a single sale, then this sale would be a *fact* in the database, and the sales value would be called a *measure*. +Then this sales fact is associated with a set of *dimensions* such as the product type, the store and the sale time. + +Each of these dimensions are oriented in a hierarchy, such that we can "zoom in" or out for more or less detail. +For example with a timestamp, we can only be interested in week or year, but also zoom into specific days. + +Therefore we divide data into dimensions and facts. + +Facts +: an important entity such as a sale. Often contain a *measures* which are things that can be aggregated, such as sales price. +Dimensions +: describes a fact such that we can search for different things. For example where did the sale happen, who bought it etc. + +We can then say that facts live a *cube* with many dimensions (yeah that does not make such sense, so *hypercube* is also sometimes used). +Often these cubes have around 4-12 dimensions, but often 2 or 3 can be shown due to our stupid brains. +We denote a *sparse cube* as a cube with many empty cells and the opposite as a *dense cube*. + +The slides have a nice todo list of things todo when designing a data warehouse. + +## Types of Facts + +Event fact +: or an *transaction fact* is a bussiness event such as a sale. +Measureless fact +: without a numerical measure, so just something that happened for some combination of dimensions. +State fact +: captures the current status at some timestamp, such as inventory. + +## Granularity + +What does a single fact mean, like the *level of detail*, "is a single fact the total sales in a day, or every single sale?". +We often let the granularity be a single business transaction, such as a sale, however we can aggregate this for scalability. + +## More on Measures + +This is something that a user might want to study for optimize for. +Each measure has two components, namely a *numerical value* and a *aggregation formula*. + +There are different forms of measures: + + - **Additive measure** can be aggregated for all dimensions. A good example is the sale price. + - **Semi-additive** can be aggregated over some dimensions, but not all. + A good example is inventory, which cannot be aggregated over time (we would count stuff twice), but we can over aggregate over store to get total inventory. + - **Non-additive** cannot be aggregated over anything. For example if it is a average sales price. + +## Implementation + +Here the granuality is avery important to consider, "what does a single row represent". + +It is not very nice to store the whole dimension stuff with each fact, so instead we use *star schemas* and *snowflake schemas*, +with work with *fact tables* and *dimension tables*. + +A **fact table** stores facts, and facts only, with references to the dimension values in the *dimension tables*. +Here we use a *surrogate key* to reference dimension values, which should be meaningless. + +A **Star schema** has one fact table, and then one de-normalized dimension table for each dimension containing all levels. +This elliminates a lot of the foreign key usage, making stuff faster, however it hides the levels from the user and takes up more storage. + +A **snowflake schema** stores the dimensions normalized, in that each level has its own dimension table. + +In regards to *redundancy*, this is something we want to avoid, as it allows for inconsistent data and complexities with updating. + +# Advanced Multidimensional Modeling + +*warning: very very advanced* + + |