# Data Models

*By Robert Laing*

A freely available textbook Foundations of Computer Science by Al Aho and Jeff Ullman separates the subject by data models in this order.

The book also separates Propositional Logic and Predicate Logic.

Predicate Logic expands Propositional Logic by including

- for all x
- called a
*universal quantifier*and denoted by ∀x. - there exists an x
- called an
*existential quantifier*and denoted by ∃x

## Sets

- N
- Positive integers, also called natural numbers.
- Z
- Integers
- Q
- Rational numbers, also called fractions
- R
- Real Numbers

https://web.eecs.umich.edu/~weimerw/2011-6610/reading/liskov-clu-abstraction.pdf

To be is to be the value of a variable — Willard Van Orman Quine

http://i.stanford.edu/~ullman/focs/ch07.pdf

Linked lists, characteristic vectors, and hash tables provide three basic ways torepresent sets. Linked lists offer the greatest flexibility for most set operationsbut are not always the most efficient. Characteristic vectorsprovide the great-est speed for certain set operations but can be used only whenthe universal setis small. Hash tables are often the method of choice, providing both economyof representation and speed of access.

## Relational Databases

- arity
- The number of components a tuple has is called its arity.For example, (a, b) is a tuple of arity 2; its first component is a and its second component is b. A tuple of arity k is also called a k-tuple.
- attributes
- or properties of the described objects, that can be kept together in a table, without introducing
*redundancy*, a situation where a fact is repeated several times. The columns of a table are named by attributes. The*key*for a table (or relation) is a set of attributes whose values uniquely determine the values of a whole row of the table. Knowing the key for a table helps us design datastructures for the table

## Binary Relations

### Transitivity

Let *R* be a binary relation on the domain *D*. We say that the relation *R* is transitive if whenever *aRb* and *bRc* are true, *aRc* is also true.