Database Concepts - The Entity-Relationship Diagram

Via texample.net

In this post I will try to start database ideas with modeling. Here, I will explain what an ER diagram is and how it is used as a database model. In future posts I will explain more into detail of database ideas once I have established a basic bridge. Lets get started!


In order to continue understanding clearly upcoming concepts we need to first establish some more basic basic basic terms:

Primary Keys:
Primary Keys are the significant attributes of an entity. The primary keys are used to identify the specific entity, meaning that they are unique e.g., student IDs. You'll see more of an explanation of what an entity is below.

Foreign Keys:
Foreign Keys are specific attributes that are referencing an original attribute. Continuing with the student ID example, there may be a chart of students that are age 20, identified by their student IDs. That chart's student IDs refer to the original list of Students and their student IDs.
+-------------------+     +------------------------+
| Student |   ID#   |       |      aged 20 IDs       |
|   John    |  1001  |       |          1001              |
|   Sally   |  1002  |       +-----------------------+
+-------------------+

*see here that we have a roster of students, and then a list of students that are 20, we're assuming only John is 20. This is omitted but the roster of students should also include the details of their age.

Summarized:
Primary Keys are unique identifiers, Foreign keys refer to another entity's attributes. So, looking back into the previous post, we have a change.

1. Professors(Pid CHAR(50), Pname CHAR(50), Dept CHAR(50), PRIMARY KEY (Pid))
2. Students(Sid CHAR(50), Sname CHAR(50), Age INTEGER, MajorCHAR(50), PRIMARY KEY (Sid))
3. Departments(Did CHAR(50), Dname CHAR(50), PRIMARY KEY (Did))
4. Courses(Cno INTEGER, Cname CHAR(50), PRIMARY KEY (Cno))
5. EnrolledIn(Sid CHAR(50) REFERENCES Students(Sid), Cno INTEGER, PRIMARY KEY (Sid))

*here we have added things to specify PRIMARY KEY. Also, EnrolledIn has an addition to show that Sid is referring to the table Student(Sid).  With that said, we also need to establish some integrity constraints to avoid big disastrous problems. I'll talk about these once we get the whole picture.

The Entity-Relationship Diagram:
Also called ER diagrams. ER diagrams are used to plan out how different elements of the database are going to be connected and "mapped." They show the relationships between entities their attributes, as well as entity-entity relationships.

Entity:
The entities in the diagram above are the ones in blue(Employee, Salesman, Mechanic, etc.).
Entities are the "things" that are major in a database. In the diagram, we see that the "Important" objects that are the bigger part of this database are going to be the ones in blue. All of the entities are represented as a rectangle.

Attributes:
Attributes are the little details related to each entity.

And there you have it! If you read this then you have just learned the very basics of database concepts! I'm looking forward to writing more about this topic! See you soon.

Read More

Data Structures - Stacks and Queues

In this post we'll go over some things about stacks and queues.
I have in an earlier post wrote an implementation of a queue while explaining lists. You can take a look here.

Queues:
Queues are FIFO, meaning first in first out. The first element put into the queue is dequeued in the before the others. There is a head and a tail that keeps track of the first and last element enqueued.

Priority queues:
Priority queues are used in storing processes and their priorities. When a system has to switch the processor between many many processes going on, it can switch based on priorities. Some processes have lower priority and some, higher.

Circular Queues:
Circular queues are the same as queues, except that it wraps around the end to the beginning again. With circular queues, it would be easy to use an array, since there is only a limited amount of space in a circle.

Stacks:
Stacks are FILO, meaning first in last out. Think of the stack like, a stack of plates. If you stack one plate over another, say five plates, you would take each one off one by one from the fifth one you stacked to the first one at the very bottom. Stacks are used for memory storage in systems, can be allocated for a process.

These two data structures, as you can see my examples of them, are used in important systems and programs.

Read More

Database Concepts - What is a Database? Some beginning notes

What is a database?
A database is a glop of data, a collection of data that models real world things; companies, inventory, websites, etc. The collection of data describes a series of relationships between some entities. (e.g., Annie is taking course number A110 or Josie is subscribed to a specific magazine).

What is a DBMS?
DBMS stands for "Database Management System." As the name says, it's a software that is designed to manage and store the database.

How is a file system different?
A file system is split between main memory and secondary storage, since not everything can be stored in one place. A file system also has multiple users, but it also has access control.

How is this important in CS?
The need for database knowledge is growing; websites have big sets of products, search libraries, the Human Genome project, etc. The concepts of databases also connect to Operating Systems, Programming, theory, or Artificial Intelligence.

What is a data model?
A data model is something that describes the relationships between the entities.
The relational model of relational data consists of tables:
1. The Relation: the rows and columns part of the tables are the relations.
2. The Schema: The schema are the entities and it's attributes.

The different levels of abstraction:
1. View Level/External Level:
       This layer describes how users see this data and database
2. Conceptual Level:
        This level defines the logical part of the database, the connections.
3. Physical Level:
        This level are the schemas that describe those physical files.

Examples of Levels:

Physical Level:

        All the files of each table, not in some order. So just think of a big floating world of tables, I suppose.

Conceptual Level:

1. Professors(Pid CHAR(50), Pname CHAR(50), Dept CHAR(50))
2. Students(Sid CHAR(50), Sname CHAR(50), Age INTEGER, Major CHAR(50))
3. Departments(Did CHAR(50), Dname CHAR(50))
4. Courses(Cno INTEGER, Cname CHAR(50))
5. EnrolledIn(Sid CHAR(50), Cno INTEGER)

So here we have covered some basic knowledge of databases. Please let me know in the comments what I should talk more about, or if I made any mistakes or typos in this post! I hope you enjoy the start of this learning experience with me! I will soon add to this collection of database posts and put the next link here.

Read More

Sorting Algorithms - Insertion Sort

Pic from Geeksquiz

Insertion Sort is utilized to sort a group of elements from smallest to largest. Here's how it works:

Lets say we start with an array A = {15, 16, 12, 7, 9}. This array is not sorted(least to greatest).

Pseudocode:

Insertion-Sort(A)

1.    for j = 2 to A.length do

2.        key = A[j]

3.        i = j - 1

4.        while i > 0 and A[i] > key do

5.            A[i+1] = A[i]

6.            i = i - 1

7.        A[i + 1] = key

Walk-through:

Starting with the unsorted array {15, 16, 12, 7, 9}...

line #1: j is 2. array is unchanged {15, 16, 12, 7, 9}

line #2: key is 16

line #3: i is 1

line#4: loops while i is not going out of bounds and A[i] is bigger than the key(current j that we are comparing)

line#7: we skipped lines 5 and 6 because A[i](15) was not bigger than key(16). We basically copy the key back into i + 1 in which this case it is also j.

line#1: j = 3 array is {15, 16, 12, 7, 9}

line#2: key is 12

line#3: i is 2

line#4: loops while i is not going out of bounds and A[i] is bigger than the key(current j that we are   comparing)

line#5: 16 > 12, so A[i + 1] = A[i] OR {15, 16, 16, 7, 9}

line#6: i is 1

line#7: A[i + 1] = key OR {15, 12, 16, 7, 9}

line#5: 15 > 12, so A[i + 1] = A[i] OR  {15, 15, 16, 7, 9}

line#6: i is 0

line#7: A[i+1]  = key OR {12, 15, 16, 7, 9}

See here that first three elements are now already sorted, if we keep going with the pseudocode we will eventually come to the sorted {7, 9, 12, 15, 16}. Try doing the rest!

Analysis: 

Worst Case: The worse array that can go through this is some array that is sorted in reverse order e.g, {19, 15, 13, 7, 3, 1} 

In this case, the algorithm will have to go through and compare each number to more and more numbers.

For example, the worst case array presented here will first compare 15 once, then compare 13 twice, then 7 three times, 3 four times, and 1 five times:

                                                     1 + 2 + 3 + 4 + 5........

In terms of the length of the array n, it will compare a total of:
                                                            n(n + 1)/ 2  OR  (n^2 + n)/2 times

As you accumulate more knowledge or already have, you will see that O(n^2) is not very nice a time compared to some others.

Read More