Database Fundamentals

Study Notes

A database is a collection of records that are manipulated by a computer.
Database Management Systems (DBMS) are programs that help users access information in databases.

A key is a single attribute or a combination of attributes that uniquely define an n-tuple.
A query is a request for information from the database.

A selection operator chooses certain n-tuples from a relation based on conditions given on attributes.
A projection operator chooses columns and eliminates duplicates.
A join operation manipulates one or two relations.

An adjacency list represents a graph without multiple edges by listing all its edges and the vertices adjacent to each vertex.
An adjacency matrix of a graph is based on the ordering chosen for the vertices.
A path is a sequence of edges that begins at a vertex and travels from vertex to vertex along the graph's edges.
A circuit or cycle is a path of length greater than zero that begins and ends at the same vertex.
A graph is connected if there is a path between every pair of distinct vertices.
A graph is disconnected or not connected if removing vertices or edges produces a disconnected graph.
A graph is strongly connected if there is a path from vertex a to vertex b and from vertex b to vertex a.
A graph is weakly connected if there is a path between every two vertices in the underlying directed graph.

An Eulerian circuit is a simple circuit containing every edge of a graph.
An Eulerian path is a simple path containing every edge of a graph, with each edge appearing exactly once.
A theorem states that a connected graph has an Eulerian circuit if and only if the degree of each vertex is even.