Database Fundamentals

6 Questions

What is a relational database model based on?

The concept of n-ary relation

What is a key in a relational database?

A single attribute or a combination of attributes where its values are uniquely defined

What is the result of a selection operator on a relation?

Certain n-tuples are chosen from the relation based on a condition

What is an adjacency list used for?

Representing graphs without multiple edges

What is a Eulerian circuit?

A simple circuit containing every edge of a graph

What is a necessary condition for a graph to be Eulerian?

The degree of each vertex is even

Study Notes

Database Basics

A binary relation refers to a table with two columns.
An n-ary relation refers to a table with n columns.

Relational Database Model

The relational database model was invented by E.F. Codd in 1970.
This model is based on the concept of n-ary relations.

Database Concepts

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.

Relations and Attributes

In an n-ary relation, attributes refer to the columns.
The domain of an attribute is the set to which all its elements belong.

Keys and Queries

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.

Operators

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.

Graph Theory

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.

Eulerian Circuits and Paths

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.