There are broadly two methods to execute queries in database –
Imperative – in this, code tells computer to perform certain operations in sequence. Most of the programming languages are imperative.
Declarative – in this method, one specifies the pattern of data needed, rest all is taken care by query optimizer. Most of the SQL languages are declarative. It is easier to work with, hides database engine’s implementation details. Also these languages support parallisation across multiple machines.
MapReduce Querying –
Neither imperative, nor declarative, combination of two.
It is based on the map (also known as collect) and reduce (also known as fold or inject) functions that exist in many functional programming languages.
Map and reduce are pure functions, which means they only use the data that is passed to them as input, they cannot perform additional database queries, and they must not have any side effects.
Thanks for stopping by! Hope this gives you a brief overview in to query languages for data models. Eager to hear your thoughts and chat, please leave comments below and we can discuss.
As per author there are three paradigms in programming –
Structured Programming
Object Oriented Programming
Functional Programming
Lets’s go through each of them briefly as subsequent chapters go in detail on them.
Structured Programming
Structured programming imposes discipline on direct transfer of control
Robert Martin
This paradigm was discovered last, but was the first to be adopted. It was discovered by Dijsktra. It removes the use of unrestrained GOTO statements. Goto statements were used to transfer control to another part of code, and once that finished, there would be another go to statement to return back. This would create unnecessary overhead in programming. Also, adversely impacting readability of code. He replaced goto with if/then/else and do/while/until, or more specifically what we now call conditional statements and loops.
Object Oriented Programming
Object-oriented programming imposes discipline on indirect transfer of control
Robert Martin
This paradigm was second to be discovered but was adopted after structured programming. It was discovered by Johan Dahl and Kristen Nygaard. They moved the function call stack to heap, which allowed the reuse of local variables by multiple functions. (Each thread has its own stack but multiple threads share the heap memory) Now in modern programming we have constructors in a class to initialize objects and instance variables. These instance variables are accessible to all the methods in the class. Thereby decreasing unnecessary function calls to pass those instance variables.
Functional Programming
Functional programming imposes discipline on assignment
Robert Martin
This paradigm was the first to be discovered but last to be adopted. It was discovered by Alonzo Church. This is based on lambda functions in mathematics. Lambda functions are based on the assumption that values of the symbols do not change (Immutability). And most of the functional programming languages have no assignment statement. They do allow changing the value but under strict conditions.
Summary
Most of the modern programming languages today follow all three paradigms in some way. For example, Java, primarily object-oriented language, not long ago from Java 8 implemented functional interfaces to allow for functional programming. Another great example is Javascript. We will see Structured programming paradigm in next post and learn how modern languages heavily use it.
Thanks for stopping by! Hope this gives you a perspective on software paradigms. Post comments to start a discussion. See you in the next post.
Graph search or finding whether one vertex is reachable from another vertex in a graph is one of the operations we can apply on graphs. There are two basic methods for this:
Depth First Search
Breadth First Search
In this post, we will study Depth First Search. We will create a graph for a directed unweighted graph as an adjacency list using the concepts discussed in this previous post. Then apply DFS on it.
What does reachability mean?
One vertex is reachable from another vertex if and only if there exists a path between them. For example in the directed graph given below, there exists a pathbetween 1 and 6 but not between 3 and 4.
We can either go directly from node 1 to node 6 or go from node 1 to node 5 and then to node 6. The blue color highlights the path. And the gray color highlights the lack of path between 3 and 4 in the above graph.
How does Depth First Search (DFS) work?
We have source node and a destination node in a graph. Our motive is to find a path between them. So we call DFS on our source and destination. DFS then checks whether there is a path from any of the node’s children to the destination. If there is a path it returns true. Else it continues on the current node’s children until either we reach the destination (return true) or we reach a node already traversed ( return false).
The following example will clarify this more.
Fig 2 shows a directed unweighted graph along with adjacencylist of each node. Suppose we want to find whether a path exists between 3 and 4. As per DFS, we check whether a path exists between 3’s child i.e. 6 and 4. Which further checks whether a path exists between 6’s child i.e. 2 and 4. This then checks whether a path exists between 2’s child i.e. 3 and 4. 3 is our node already traversed and so we return false. Let’s look at an example where a path exists.
Suppose we want to find whether a path exists between 1 and 6. Again, we start with 1’s child i.e 2 and call our method pathExists on 2 and 6. Then again we call method pathExists method on 2’s child i.e. 3and 6 and then finally on 6 and 6 which returns true. This True goes all the way back to our first call and we return the final result ie True.
Implementation
Now we code the above concept in Java. I will break down the code into few simple steps for ease in understanding
Step 1: Create a Node class, which stores the Node’s id of primitive type along with a LinkedList/ArrayList to store adjacency list of that node.
Step 2: Create a hashmap/ArrayList to store the vertices of a graph as Node objects. Here we can create a global variable to store graph or locally in methods and then pass them as parameters. Till now, we created a global variable for the graph, for the next two videos we will create a graph in a method and pass it as parameters.
Step 3: Add all the edges into the graph by updating the adjacency list of source nodes.
Step 4: Write method to find whether a path exists between source and destination using DFS.
Now we go through each step in detail:
Step 1:
Create a Node class, which stores the Node id/name/label of primitive type along with a LinkedList/ArrayList to store adjacency list of that node. For a detailed explanation refer to this post.
/**
* Node --- class to store each vertex along with its adjacent vertices
*/
static class Node{
private String id;
private LinkedList<Node> adjacent;
public Node(String id){
this.id = id;
adjacent = new LinkedList<Node>();
}
//Getter method for start vertex
public String getId(){
return id;
}
//Getter method for end vertex
public LinkedList<Node> getAdjacent(){
return adjacent;
}
//add node to the adajcent list
public void addAdjacent(Node vertex){
adjacent.add(vertex);
}
//To print Node
public String toString(){
String msg = id + " : ";
for(Node node: adjacent)
msg = msg + node.id + " ";
return msg;
}
}
Step 2:
Create a HashMap/ArrayList to store the vertices of a graph as Node objects.
In our example graph in Fig 4, we have string nodes. So our HashMap will have keys of type String and Values of type Node.
/**
* Creates a HashMap with string key and Node value
* @param input list of edges
* @return HashMap<String,Node>
*/
public static HashMap<String, Node> createGraph(String[] input){
HashMap<String, Node> graph = new HashMap<String, Node>();
Node node;
for(String s: input){
String first = String.valueOf(s.charAt(0));
String second = String.valueOf(s.charAt(1));
add(graph, first, second);
}
return graph;
}
Step 3:
Add all the edges into the graph by updating the adjacency list of source nodes.
Our input is an array of strings where each string “XY” represents an edge from X to Y. So we traverse our list and do the following three steps on each of the string values.
//Input edges of the graph.
String[] input = {"AB","BC","BE","CF","DE","EF"};
Part 1: First we separate X and Y from our string “XY”. We can do that by using the String’s charAt(index) method and assign them to a first and second variable. Then add the edge to our graph by calling the add method.
public static void add(HashMap<String, Node> graph, String source, String destination){
//Get nodes corresponding to source and destination vertices.
Node s = getNode(graph, source);
Node d = getNode(graph, destination);
//add nodes to adjacent list
s.addAdjacent(d);
}
Part 2: We access the node corresponding to string X and Y in the graph. If there is no such node in our graph then we create one. This method getNode() does exactly that. It checks whether string K is present in our graph, if yes, then returns the corresponding node, else creates a new node with id K and adds it to our graph with key K.
Part 3: Once we have both the nodes, we can add the destination node to source node’s adjacent list. Now our graph is created.
Step 4:
Write method to find whether a path exists between source and destination.
We know that path exists between source and destination when the source becomes equal to the destination while traversing the graph. And we also know that if we encounter a node already visited while searching the destination then we don’t have a path between source and destination. So we need to keeptrack of the nodes visited so far. We do that using a HashSet visited.
We create an empty HashSet in our helper method and pass it and the source and the destination node to our main recursive method. We can get the nodes from the hashmap using getNode() method described above.
Once we are on a node, we check whether that node exists in our visited set. If it exists, we return false (no path between source and destination). If it doesn’t exist in visited, we add the node to the visited set.
Then we check whether the current node is equal to our destination. If yes, we have found a path, so we return true. Else we traverse the adjacent list of the current node and check if a path exists between its children and the destination node. If a path does exist we return true, else we return false.
/**
* Helper method for pathExists recursive method
* @param HashMap<String, Node> graph
* @param source start index
* @param destinations end index
* @return true or false
*/
public static boolean pathExists(HashMap<String, Node> graph, String source, String destination){
HashSet<Node> visited = new HashSet<Node>();
return pathExists(getNode(graph, source), getNode(graph, destination), visited);
}
/**
* pathExists recursive method to find path between source and destination
* @param source start index
* @param destinations end index
* @param visited set to store visited nodes
* @return true or false
*/
public static boolean pathExists(Node source, Node destination, HashSet<Node> visited){
if(visited.contains(source))
return false;
visited.add(source);
if(source == destination)
return true;
for(Node neighbor : source.getAdjacent()){
if(pathExists(neighbor, destination, visited))
return true;
}
return false;
}
Example
We see recursive calls on two examples for the graph in Fig 4.
pathExists(graph, “A”, “F”)
pathExists(graph, “A”, “D”)
The adjacency list of all nodes in the graph of Fig 4 is:
What is this argument label? Why do we use it? How’s it different from the parameter names.
Let’s find out.
Remember this factorial function from last few posts?
func factorial (number: Int) -> Int{
var factorial = 1
var temp = number
while(temp>1){
factorial = factorial * temp
temp = temp - 1
}
return factorial
}
We will add an argument label “of” to the parameter name number.
func factorial (of number: Int) -> Int{
var factorial = 1
var temp = number
while(temp>1){
factorial = factorial * temp
temp = temp - 1
}
return factorial
}
Immediately we have an error here, where we are calling this function factorial.
The error says “Incorrect argument label in call(have number:”, expected “of:”
When we replace the number with of, the error vanishes.
This “of’ here is an argument label. The argument labels are like external parameter name. These are used when calling a function. The other parameter name “number” is the internal parameter name and is used inside the function.
Earlier when there was no “of” ie argument label, the parameter name became the default argument label and we used “number:” instead of “of:”.
So when we explicitly write an argument label we have to use that in the function call. Else we use the parameter name as argument label.
The use of argument label makes a function more expressive, sort of like a sentence. Like this factorial function call above, now, can be read as the factorial of 7.
With this we complete functions. If you have any questions leave them in the comment section below.