Title: Theory / Important / CS / Algo / Database / Database System Concept 6 - McGraw Hill+27{ / 1 Introduction / Formal;
Tags: fromMath mathToDef defToCS toBinaryFunction hasSeenConjDef fromImplication mathToSee FromInstruction closed computer_to_instruction hasNotNewEffectReturnsMeaning récupéré seen_description toBinaryRelation

Name: A tuple
Definition: A row of the table.
Page: 41
Chapter: 2
Section: 1
Variables: \(T\) a table

Name: A relation instance of \(R\)
Definition: A specific instance of the relation \(R\).
Page: 41
Chapter: 2
Section: 1
Variables: \(R\) a relation

Name: The domain of \(a\)
Definition: The set of permitted value for \(a\).
Page: 42
Chapter: 2
Section: 1
Variables: \(R\) a relation and \(a\) an attribute

Name: The null value
Definition: Value that signifies that the value is unknown or does not exist.
Page: 42
Chapter: 2
Section: 1

Name: Database schema
Definition: The logical design of the database.
Page: 42
Chapter: 2

Name: Database instance
Definition: A snapshot of the data in the database at a given instant in time.
Page: 42
Chapter: 2

Name: A superkey
Definition: A set of one or more attributes that, taken collectively, allow us to identify uniquely a tuple in the relation.
Page: 45
Chapter: 2
Section: 3

Name: Candidate key
Definition: A minimal superkey.
Page: 45
Chapter: 2
Section: 3

Name: The set of superkey
Page: 45
Section: 3
Chapter: 2
Under: taking a superset

Name: Primary key
Definition: A candidate key that is chosen by the database designer as the principal means of identifying tuples within a relation.
Page: 45
Chapter: 2
Section: 3
Notation: Underlined (in Entity relationship diagram)
Property: Nonnull
Cardinal: unique

Name: Foreign key
Definition: The primary key of another relation.
Page: 46, 47, 131
Chapter: 2, 2, 4
Section: 3, 4, 4.5
Denoted by: Underlined attributes

Name: Query language
Definition: A language in which a user requests information from the database.
Page: 17
Chapter: 2
Section: 5

Page: 49
Section: 5
Chapter: 2
Name: Join operation
Definition: Allows the combining of two relations by merging pairs of tuples, one from each relation, into a single tuple.
Example: natural join
Example2: Cartesian product

Page: 50
Section: 5
Notation: \(\times\)
Chapter: 2
Name: Cartesian product
Definition: All pairs of tuples from the two relations.

Name: Projection
Definition: Output specified attributes from all rows of the input relation. Remove duplicate tuples from the output.
Page: 51
Chapter: 2
Section: 6
Context: database algebra
Notation: \(\Pi\)

Name: unary operation
Definition: Operations operating on one relation
Page: 217
Chapter: 6
Section: 1.1
Example: select
Example2: rename
Example3: project

Name: selection
Definition: The subset of rel containing the tuples satysfing cond
Page: 218
Chapter: 6
Section: 1.1.1
Variables: rel a relation,
cond a condition
Notation: \(\sigma_{cond }(rel)\)
Intuition: where of SQL

Name: project
Definition: The relation rel restricted to the schema with name in names
Page: 219
Chapter: 6
Section: 1.1.2
Variables: rel a relation,
names
Notation: \(\pi_{names }(rel)\)
Typ: A relation whose schema is composed of names and each name have the same type than in rel
Assuming: names is a subset of the names occurring in rel

Page: 220, 221
Section: 1.1.4
Notation: \(rel\cup rel'\)
Variables: rel, rel' relations
Chapter: 6
Name: Union
Definition: The relation with elements of rel and of rel'
Assuming: rel and rel' have the same type
Codomain: A relation whose schema is the same than the one of rel and of rel'

Page: 220, 221
Section: 1.1.5
Notation: \(rel- rel'\)
Variables: rel, rel' relations
Chapter: 6
Name: set difference
Definition: The relation occuring in rel and not in rel'
Assuming: rel and rel' have the same type
Codomain: A relation whose schema is the same than the one of rel and of rel'

Page: 221
Section: 1.1.6
Notation: \(rel_1\times rel_2\)
Variables: rel_1, rel_2 relations
Chapter: 6
Name: Cartesian product
Definition: The relation whose tuples is every possible concatenations of tuples of rel_1 and of rel_2
Assuming: arguments of the Cartesian-product operation have distinct names.
Codomain: A relation whose schema is composed of rel_i.name for name in the schema of rel_i or name if there is no ambiguity

Page: 226
Definition: Queries which, given the same relations as inputs, output the same relations
Chapter: 6
Section: 1.1.6
Name: Equivalent queries

Name: Rename
Definition: The same content than rel but with names names
Page: 226
Chapter: 6
Section: 1.1.7
Variables: rel a relation
names a tuple of names
Notation: \(\rho_{names}(E)\)
Typ: The schema whose names are names and types are the one of rel
Assuming: names and rel's schema have the same number of elements

Name: A constant relation
Definition: The relation containing exactly the tuples listed
Page: 228
Chapter: 6
Section: 1.2
Notation: \(\{\text{explicit list of tuples}\}\)
Assuming: Each tuple's have the same types

Page: 229
Section: 1.3.1
Notation: \(\cap\) on relations
Variables: \(s,r\) relations
Chapter: 6
Name: Intersection of relations
Definition: \((r,s)\mapsto r-(r-s)\)
Assuming: inputs are of the same type

Definition: Assign to \(foo\) the result of the operation \(bar\)
Page: 232
Chapter: 6
Section: 1.3.2
Notation: \(foo\leftarrow bar\)

Name: Generalized Projection
Definition: For each entry of \(E\), the \(n\)-tuple of result of the \(F_i\)'s applied to this entry
Page: 235
Chapter: 6
Section: 1.4.1
Variables: \(E\) any relational-algebra expression
\(F_i\) arithmetic expressions
Notation: \(\Pi_{F_1,\dots,F_n}(E)\)
Assuming: \(F_i\)'s attribute are in the schema of \(E\)

Name: An aggregate function
Definition: A function taking a collection of values and returning a single value
Page: 235
Chapter: 6
Section: 1.4.1
Example: sum
Example2: max

Definition: The aggregate function returning the sum of the values of the input collection
Page: 235
Chapter: 6
Section: 1.4.1
Notation: sum

Definition: The aggregate function returning the average of the values of the input collection
Page: 236
Chapter: 6
Section: 1.4.1
Notation: avg

Definition: The aggregate function returning the number of elements in the input collection
Page: 236
Chapter: 6
Section: 1.4.1
Notation: count

Instruction: min/max(column)
Page: 236
Language: sql
Context: SQL
Chapter: 6
Section: 1.4.1
Returns: The least/greatest element of the input collection
Typ: The aggregate function

Definition: The function sending a relation to its image by \(a\)
Page: 236
Chapter: 6
Section: 1.4.1
Variables: \(a\) an aggregate function
Context: Aggregation function sql
Notation: \(\mathcal G_{a}\)

Definition: A relation containing a \(n+m\) tuple:
\(\left( \left(v_1\right)_{i=1}^n, \left( F_j\left( \left\{ a_j\mid \left( \left(v_1\right)_{i=1}^n, a_j \right) \in \Pi_{G_1,\dots,G_n,A_j}(E) \right\} \right) \right)_{j=1}^m\right)\)
for each \(v_i\) a value of the attribute \(G_i\).)
Page: 27
Chapter: 6
Section: 1.4.1
Variables: \(E\) a relational-algebra expression\(G_i\) distinct attributes of \(E\)
\(A_i\) attributes,
\(F_i\) aggregate function
Notation: \(_{G_1,\dots,G_n}\mathcal G_{F_1(A_1),\dots,F_m(A_m)}(E)\)
Typ: A table with one column for each \(G_i\) and one for each \(F_i\)

Name: Multiset algebra
Definition: The adaptation of set algebra for multiset
Page: 238
Chapter: 6
Section: 1.4.1

Name: A tuple-relational-calculus expression
Definition: A term of the form \(\{t\mid P(t)\}\) with \(P\) a formula whose set of free variable is a subset of \(t\).
Page: 243
Chapter: 6
Section: 2.2
Context: database

Name: A free variable
Definition: A variable which does not lie in the scope of a quantifier
Page: 243
Chapter: 6
Section: 2.2
Variables: \(P\) a formula

Name: An atom
Definition: \(s\in r\) with \(s\) a tuple variable and \(r\) a relation
Page: 243, 245
Chapter: 6
Section: 2.2
Context: tuple-relational-calculus
Definition2: \(s_1[x_2]\Theta s_2[x_2]\) for \(s_i\) tuple variables, \(x_i\) attribute of \(s_i\), \(\Theta\) being \(\le,<,=,\ne,>,\ge\)
Conjdef: Either
Definition3: \(s[x]\Theta c\) for \(s\) tuple variables, \(x\) attribute of \(s\), \(\Theta\) being \(\le,<,=,\ne,>,\ge\) and \(c\) a constant
Name2: An atomic formula

Name: A formula
Definition: An atom
Page: 243
Chapter: 6
Section: 2.2
Context: Tuple-relational-calculus
Definition2: A Boolean combination of formula
Conjdef: Either
Definition3: \(\exists s\in r(P(s))\) for \(s\) occurring free in \(P\), \(r\) a relation and \(P\) a formula
Denoted by: \(P\)

Name: An expression in domain relational calculus
Definition: An expression of the form \(\{\langle x_1,\dots,x_n\rangle\mid P(x_1,\dots,x_n)\}\) with \(x_i\) domain variables and \(P\) a formula
Page: 245
Chapter: 6
Section: 3

Name: An atomic formula
Definition: \(<x_1,\dots,x_n>\in r\) with \(r\) a relation on \(n\) attributes, and \(x_i\) domain variable or constant
Page: 245
Chapter: 6
Section: 3
Context: Domain relational calculus
Definition2: \(x_1\Theta x_1\) for \(x_i\) a domain variable, \(\Theta\) being \(\le,<,=,\ne,>,\ge\). The \(x_i\) must be in comparable domains
Conjdef: A formula of the form:
Definition3: \(x\Theta c\) for \(s\) tuple variables, \(x\) attribute of \(s\), \(\Theta\) being \(\le,<,=,\ne,>,\ge\) and \(c\) a constant comparable to the domain of \(x\)

Name: A safe formula
Definition: A formula whose every existential quantification is restricted to a specific relation
Page: 245
Chapter: 6
Section: 3
Context: domain relational calculus

Smaller0: \(P\) is safe
Greater0: is a subset of \(dom(P)\)
Page: 245
Chapter: 6
Section: 3
Variables: \(P\) a formula in domain relational calculus
Prefix Greater: \(\{<x_1,\dots,x_n>\mid P(x_1,\dots,x_n)\}\)

Smaller0: \(f\) is expressible as a safe expression in domain-relational-calculus
Greater0: \(f\) is expressible as a safe expression in tuple-relational-calculus
Page: 248
Chapter: 6
Section: 3.4
Variables: \(f\) a function from relations to relations
Smaller to greater: iff
Smallest: \(f\) is expressible in basic relational algebra

Name: next
Definition: end of chapter
Page: 248
Chapter: 6
Section: 3.4

Name: The relational algebra's term based on \(D\)
Definition: constant relation
Page: 228
Chapter: 6
Section: 1.2
Variables: \(D\) a db
Definition2: Select
Conjdef: The least set containing
Definition3: database's relation
Definition4: Boolean operations
Definition5: Cartesian product
Definition6: Project
Definition7: Renaming

Left: Database
Right: Executable
Left2: A relation
Right2: A variable
Page: 42
Chapter: 2
Left3: Relation schema
Right3: Type definition
Left4: A relation instance
Right4: The interpetation of a variable