Frontier Software

Robert Laing's programing notes

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.

  1. Trees
  2. Lists
  3. Sets
  4. Relations
  5. Graphs
  6. Automata

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


Positive integers, also called natural numbers.
Rational numbers, also called fractions
Real Numbers

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

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

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.
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


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.

Transitive Closure R+

Reflexive-Transitive Closure R*

Graph Databases

Last updated on 2 Jan 2021
Published on 2 Jan 2021

Content Footer