Add exam notes for db and pp

4 files changed, 558 insertions, 21 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*
+
+
diff --git a/sem7/pp/eksamnen.md b/sem7/pp/eksamnen.md
index 6641d2a..be694ae 100644
--- a/sem7/pp/eksamnen.md
+++ b/sem7/pp/eksamnen.md
@@ -7,6 +7,9 @@
 
 ## Alt Andet
 
+  - "The last condition ..." i logic part 2 1:40. Er det rigtigt?
+  - Er det ikke en fejl i 0:32 i prolog lists videon
+
 # Mixed
 
 *Parameters* is in the declaration, and *arguments* are the things actually passed.
@@ -21,6 +24,19 @@ The arguments are placed in the body according to the parameters.
 
 **Eta** says that functions that just pass arguments to other functions can be substritued by its body.
 
+## Some Haskell Things
+
+```haskell
+-- if
+hej = if (x == 10) then 2 else 3
+
+-- List comprehention
+evens = [i | i <- [0..], i `mod` 2 == 0]
+
+-- Here True and False are *term contructors* and Boolean is a *type constructor*
+data Boolean = True | False
+```
+
 # Scheme lek. 1
 
 Programming paradigm
@@ -184,3 +200,189 @@ Therefore normal order is the post powerful reduction
 
 `(delay expr)` is used to delay the evaluation of `expr`, by returning a promise.
 The value of this can then be extracted with `(force promise)`.
+
+# Haskell lec.5 Lazy Evaluation
+
+Lazy evaluation is the default in haskell.
+Semanticly it is quite simple requiring only a small amount of rules.
+
+There is the beta rewrite rule from before.
+And then there is *application* rule which states that for an application `e1 e2` we only evaluatate `e1`.
+This means that `e2` is newer evaluated before the application is done.
+
+# Haskell lec.7 Type Systems
+
+## Simple Type System
+
+Her har man at expressions kan have simple typer som Int, Bool, eller funktionener og tuples.
+Dette giver nogle forskellige garantier.
+
+Hvis `e` er *wel typed* og `e` reducere til `e'`, så er `e'` også vel typed.
+Dette hedder **subject reduction** og siger noget om *type preservation*.
+
+Den anden er at hvis `e` er *well typed*, så terminere `e`, altså der er en `e'` som er `e` reduceret og `e'` kan ikke reduceres længere.
+Dette er **type safety**.
+
+Disse garantier betyder også at der er mange ting man ikke kan representere.
+For eksempel hvad hvis man gerne vil lave programmer der terminere.
+
+Dette kan man sige fordi det imple type system har *slack*.
+Dette er fordi der er expressions der er safe, men ikke er vel typed.
+For eksempel:
+
+```
+let f = x: x; in (f 0, f True)
+```
+
+Dette giver bare `(0, True)` men det er ikke well typed, fordi der ikke en type for `f`.
+
+## Parametric Polymorhism
+
+Her introducere man
+
+  - **Type variables** som der kan representere hvad som helst.
+  - **Type schemes** som siger noget om free og bound type variables.
+
+Hvis ens type scheme ikke har nogen quantifier for en bestemt type variable, så er den variabel *free*.
+
+Her kan man sige at `Ftv(t)` finder alle frie type variables i typen `t`.
+Her kan man også sige `Ftv(E)` for type environment `E` så er resultatet `Ftv(t)` for alle typer `t` i `E`.
+
+### Specialization
+
+Her snakker man om at et type scheme er en specialization af en type.
+Så man laver en type fra en type scheme.
+
+Så for eksempel er `Int -> Int \leq \forall a. a -> a`.
+
+### Generalization
+
+Her er det det omvendte, med at man laver en type scheme ud fra en type.
+Dette er hvis man har en type har free variable `a`, så kan man lave et scheme der indeholder `\forall a`.
+
+Dette gør man med funktionen `close(E, t)`.
+Denne funktion ville tage og lave quantifiers for alle `Ftv(t) \setminus Ftv(E)`.
+
+### Principle Types
+
+En type `t` er principle for expression `e` og type env `E` hvis enten
+
+  - `t` er typen for `e` i `E`,
+  - eller typen `t1` for `e` i `E` er en specialization af `t`.
+
+Så man kan kalde principle types den mest generelle type.
+
+Her vil vi gerne have et *type inference algorithm* der finder den principielle type for en expression.
+
+### Semantic Regler
+
+Her introducere man nogle regler der sammen med gamle regler kan identificere typer for expressions.
+Dette er `PROJ` som laver specialization, og `GENERALIZATION` som laver generalization.
+
+# Haskell lec.8 More Typing
+
+## Type Classes
+
+With typeclasses, we now say that the quantifiers in a scheme do not say `a can be everything` but `a is part of typeclass \Gamma`.
+We use `\Gamma` for a collection of type classes.
+
+Dette betyder at når man normalt bestemte tyder ud fra et environment der mapper Vars til Types,
+er der nu også en `C` der mapper fra typevariabler til typeclasses.
+
+Okay tror jeg laver de her noter på papir.
+Lidt meget matematik.
+
+# Logic lec.9 Introduction and Datalog
+
+Her skriver jeg igen noter på papir.
+
+# Logic lec.10 Datalog
+
+**Herbrand universe** is the set of constant that appear in the datalog program.
+These are the things which we can talk about.
+
+The **Herbrand base** is then the set of all ground atoms that can be created.
+This is basicly all the things we can say about the **Herbrand universe**, giving a pretty large set.
+
+## Interpretation
+
+An *interpretation* is a set of atoms from the Herbrand universe.
+This could be any subset, and does not have to have to make sense.
+
+We will now talk about how a clause can be true under an interpretation, or how an interpretation models a clause.
+Here facts are easy, as we just check if it is contained in the interpretation.
+A rule is only false if all the facts in the body are true and the head is false, due to the implicative nature of rules.
+
+## Model
+
+We say that an interpretation is a model for a clause, if every ground instance of the clause is true under the interpretation.
+Such an interpretation we denote with M.
+
+We denote the *minimal model* for a program as the smallest possible model for the program.
+This mimimal model can be found as the intersection between all models of the program.
+
+We can find it by starting with the empty interpretation, and then repeatedly extend it will all possible conclusions from the program.
+First facts are added, and then we will start adding conclusions from rules.
+This process will always finish.
+
+## Proof Directed Goal Search
+
+Instead of computing the minimal model, we are only interested in a specific conclusion or query.
+This is done with *goal directed proof search*.
+
+This is done by constructing a proof tree.
+Here we branch the tree every time we have to choose between two clauses.
+
+## Negation in Datalog
+
+In Datalog we can only negate atoms, and not rules.
+Therefore we destinquist negative and positive atoms.
+A negative atom can then only appear in the body of a rule and not the head.
+
+Here we extend the idea of when an atom is in an interpretation, such that `I |= not p(t)` holds if `p(t)` is not in `I`.
+
+In datalog we need to do some stuff for stuff to make sense, as we can create programs with multiple incompatible models:
+
+```prolog
+P(x) :- not Q(x).
+Q(x) :- not P(x).
+```
+
+Therefore we want to disallow circularity, which we do by defining layers.
+We split the program in subprograms, where each subprogram only refers to things from the preveous layer.
+We call this *stratification*.
+
+## Some Words
+
+  - *Model-theoretical* semantics refers to finding a solution with Herbrand universe and base, interpretation and minimal models.
+  - *Fixed-point* semantics is the bottom up approach, where we compute the minimal model.
+  - *Proof-theoretical* semantics is the top down approach, with proof trees.
+
+These can be shown to be equivalent.
+
+The idea of a minimal model does not make much sense with prolog, as the minimal models can be infinite.
+
+# Logic lec.11 Prolog Instead of Datalog
+
+One should remember that prolog uses proof search instead of computing minimal model.
+With proof search and the existence of recursive clauses, the ordering of clauses matters.
+This is because the order of clauses determines the order in which proof search tries things.
+
+## Some Short Prolog Things
+
+```prolog
+% This mimics the idea of haskells composite types.
+nat(zero).
+nat(succ(X)) :- nat(X).
+
+% Some list notation
+% [1,2,3] er det samme som [1 | [2 | [3 | []]]]
+```
+
+The above thing means that the herbrand base is infinite.
+
+## Proof Search
+
+We check each clause in the order in which they appear.
+If the head of a clause matches, we unify it with the body of the clause.
+We then get new goals which we continue with.
diff --git a/sem7/pp/larger.hs b/sem7/pp/larger.hs
index 5618faf..2cf8e57 100644
--- a/sem7/pp/larger.hs
+++ b/sem7/pp/larger.hs
@@ -1,5 +1,26 @@
 import Data.Maybe
 
+-- Fra lec5
+valid :: (Integral a, Ord a) => [(a, b)] -> Bool
+valid = recur empty
+  where recur _ [] = True
+        recur known (pair:rest) =
+          if key `member` known
+          then False
+          else recur (insert key known) rest
+          where key = fst pair
+
+
+-- TODO, case where key is not in is unhandled
+lookup' :: (Integral a, Ord a) => [(a, b)] -> a -> b
+lookup' (pair:rest) key = if (fst pair) == key
+                          then (snd pair)
+                          else lookup' rest key
+
+-- I dont see how findfun and lookup are not the same
+findfun = lookup'
+
+
 data LTree = LLeaf String | LNode LTree LTree
 data LTreeRoot = LTreeRoot LTree Float
 
diff --git a/sem7/pp/lec5.hs b/sem7/pp/lec5.hs
index 3340346..37f6b12 100644
--- a/sem7/pp/lec5.hs
+++ b/sem7/pp/lec5.hs
@@ -39,7 +39,7 @@ ispalindrome x = x == reverse' x
 
 
 -- Okay assuming that a are all integers, i
--- would say that the fype of cfrac :: (Real a, Integral b) -> a -> b -> [b]
+-- would say that the fype of cfrac :: (Real a, Integral b) => a -> b -> [b]
 
 cfrac _ 0 = []
 cfrac x n = let intPart = truncate x in
@@ -69,23 +69,3 @@ flatten' (x:xs) = x ++ flatten' xs
 -- The function type is therefore flatten' :: [[a]] -> [a]
 
 -- When running :t on flatten' we get the same.
-
-
-valid :: (Integral a, Ord a) => [(a, b)] -> Bool
-valid = recur empty
-  where recur _ [] = True
-        recur known (pair:rest) =
-          if key `member` known
-          then False
-          else recur (insert key known) rest
-          where key = fst pair
-
-
--- TODO, case where key is not in is unhandled
-lookup' :: (Integral a, Ord a) => [(a, b)] -> a -> b
-lookup' (pair:rest) key = if (fst pair) == key
-                          then (snd pair)
-                          else lookup' rest key
-
--- I dont see how findfun and lookup are not the same
-findfun = lookup'