scalation
API
Generated with
scalation/scalation/scalation.database/Normalization

Normalization

scalation.database.Normalization
class Normalization(r: Attrs, fd: ArrayBuffer[FD])

The Normalization class provides methods useful in normalization theory that can be used to assist in designing relational databases. These include Closure, Superkey, Key, Losslessness, Dependency Preservation, BCNF Decomposition, Minimal Cover, and 3NF Synthesis.

Value parameters

fd

the given collection of Functional Dependencies (FDs)

r

the schema or complete set of attributes R

Attributes

See also

scalation.SetExt, scalation.database.BinTree`

Graph
Supertypes
class Object
trait Matchable
class Any

Members list

Value members

Concrete methods

def _3nf_synthesis(fd_mc: ArrayBuffer[FD]): ArrayBuffer[Attrs]

3NF SYNTHESIS ALGORITHM that synthesizes tables from Functional Dependencies (FDs). Caveat: Assumes the Functional Dependencies (FDs) constitute a MINIMAL/CANONICAL COVER.

3NF SYNTHESIS ALGORITHM that synthesizes tables from Functional Dependencies (FDs). Caveat: Assumes the Functional Dependencies (FDs) constitute a MINIMAL/CANONICAL COVER.

Value parameters

fd_mc

the minimal cover (mc) set of Functional Dependencies (FDs) to use (defaults to fd)

Attributes

def bcnf_decomp(tree: BinTree[Attrs], ri: Attrs, fd_: ArrayBuffer[FD]): Unit

BCNF DECOMPOSITION ALGORITHM that builds a BCNF decomposition tree. Caveat: Comment out find_not_bcnf_Fp line to only consider FDs in F. Reorder FDs so that those with prime attributes come last.

BCNF DECOMPOSITION ALGORITHM that builds a BCNF decomposition tree. Caveat: Comment out find_not_bcnf_Fp line to only consider FDs in F. Reorder FDs so that those with prime attributes come last.

Value parameters

fd_

the set of Functional Dependencies (FDs) to use (defaults to fd)

ri

the i-th sub-table (defaults to r)

tree

the tree (sub-tree) to work off of (defaults to bcnf_root)

Attributes

def closure(z: Attrs, fd_: ArrayBuffer[FD]): Attrs

Compute the closure of z (Z+), i.e., given the attributes in set z, what attributes in R are functionally dependent on z.

Compute the closure of z (Z+), i.e., given the attributes in set z, what attributes in R are functionally dependent on z.

Value parameters

fd_

the set of Functional Dependencies (FDs) to use (defaults to fd)

z

the given set of attributes

Attributes

def findKey(fd_mc: ArrayBuffer[FD]): Attrs

Find a (global) key for relational schema R efficiently using Algorithm based on Section 3 with modifications of An Efficient Algorithm to Compute the Candidate Keys of a Relational Database Schema.

Find a (global) key for relational schema R efficiently using Algorithm based on Section 3 with modifications of An Efficient Algorithm to Compute the Candidate Keys of a Relational Database Schema.

Value parameters

fd_mc

the minimal cover (mc) set of Functional Dependencies (FDs) to use (defaults to fd)

Attributes

See also
def find_not_bcnf(ri: Attrs, fd_: ArrayBuffer[FD]): FD

Find the first Functional Dependency (FD) explicitly in fd_ that violates the BCNF rule that the LHS of all applicable, nontrivial FDs are superkeys. Return null if none found.

Find the first Functional Dependency (FD) explicitly in fd_ that violates the BCNF rule that the LHS of all applicable, nontrivial FDs are superkeys. Return null if none found.

Value parameters

fd_

the set of Functional Dependencies (FDs) to use (defaults to fd)

ri

the i-th sub-table Ri

Attributes

def find_not_bcnf_Fp(ri: Attrs, fd_: ArrayBuffer[FD]): FD

Find the first Functional Dependency (FD) in (fd_)+, the closure, that violates the BCNF rule that the LHS of all applicable, nontrivial FDs are superkeys. Return null if none found.

Find the first Functional Dependency (FD) in (fd_)+, the closure, that violates the BCNF rule that the LHS of all applicable, nontrivial FDs are superkeys. Return null if none found.

Value parameters

fd_

the set of Functional Dependencies (FDs) to use (defaults to fd)

ri

the i-th sub-table Ri

Attributes

def key(z: Attrs, ri: Attrs, fd_: ArrayBuffer[FD]): Boolean

Determine whether the attributes z form a key for sub-schema ri.

Determine whether the attributes z form a key for sub-schema ri.

Value parameters

fd_

the set of Functional Dependencies (FDs) to use (defaults to fd)

ri

the given sub-schema (a subset of r, defaults to r)

z

the given set of attributes

Attributes

def lossless(r1: Attrs, r2: Attrs, fd_: ArrayBuffer[FD]): Boolean

Determine whether the two sub-schemas { r1, r2 } represent a lossless decomposition using the Pairwise Losslessness Test (PLT).

Determine whether the two sub-schemas { r1, r2 } represent a lossless decomposition using the Pairwise Losslessness Test (PLT).

Value parameters

fd_

the set of Functional Dependencies (FDs) to use (defaults to fd)

r1

the first sub-schema defining a table

r2

the second sub-schema defining a table

Attributes

def lossless_(p: ArrayBuffer[Attrs], fd_: ArrayBuffer[FD]): Boolean

Determine whether the db design p is lossless by checking that one of its sub-schemas contains a global key.

Determine whether the db design p is lossless by checking that one of its sub-schemas contains a global key.

Value parameters

fd_

the set of Functional Dependencies (FDs) to use (defaults to fd)

p

the set of sub-schemas defining the tables

Attributes

def merge_fds(fd_: ArrayBuffer[FD]): ArrayBuffer[FD]

Merge the Functional Dependences (FDs) that share a common LHS.

Merge the Functional Dependences (FDs) that share a common LHS.

Value parameters

fd_

the set of Functional Dependencies (FDs) to use (defaults to fd)

Attributes

def minimal_cover(fd_: ArrayBuffer[FD]): ArrayBuffer[FD]

Return a Minimal/Canonical Cover of Functional Dependencies (FDs) that are streamlined, yet equivalent to the give set fd_.

Return a Minimal/Canonical Cover of Functional Dependencies (FDs) that are streamlined, yet equivalent to the give set fd_.

Value parameters

fd_

the set of Functional Dependencies (FDs) to use (defaults to fd)

Attributes

def preserve(f: FD, p: ArrayBuffer[Attrs], fd_: ArrayBuffer[FD]): Boolean

Determine whether the functional dependency f is preserved by db design p, i.e., Y ⊆ X+_p. Combines last two methods for early algorithm termination.

Determine whether the functional dependency f is preserved by db design p, i.e., Y ⊆ X+_p. Combines last two methods for early algorithm termination.

Value parameters

f

the given function dependency

fd_

the set of Functional Dependencies (FDs) to use (defaults to fd)

p

the set of sub-schemas defining the tables

Attributes

def preserve_(f: FD, p: ArrayBuffer[Attrs], fd_: ArrayBuffer[FD]): Boolean

Determine whether the functional dependency f is preserved by db design p, i.e., Y ⊆ X+_p.

Determine whether the functional dependency f is preserved by db design p, i.e., Y ⊆ X+_p.

Value parameters

f

the given function dependency

fd_

the set of Functional Dependencies (FDs) to use (defaults to fd)

p

the set of sub-schemas defining the tables

Attributes

def rclosure(z: Attrs, ri: Attrs, fd_: ArrayBuffer[FD]): Attrs

Compute the restricted closure of z (Z+) with respect to sub-schema ri. Z+ = (Z ∩ Ri)+ ∩ Ri

Compute the restricted closure of z (Z+) with respect to sub-schema ri. Z+ = (Z ∩ Ri)+ ∩ Ri

Value parameters

fd_

the set of Functional Dependencies (FDs) to use (defaults to fd)

ri

the given sub-schema (subset of r)

z

the given set of attributes

Attributes

def rclosure_p(z: Attrs, p: ArrayBuffer[Attrs], fd_: ArrayBuffer[FD]): Attrs

Compute the restricted closure of z (Z+_p) with respect to db design (set of tables) p = {r1, r2, ...rk}.

Compute the restricted closure of z (Z+_p) with respect to db design (set of tables) p = {r1, r2, ...rk}.

Value parameters

fd_

the set of Functional Dependencies (FDs) to use (defaults to fd)

p

the set of sub-schemas defining the tables

z

the given set of attributes

Attributes

def remove_redundant_FDs(fd_: ArrayBuffer[FD]): ArrayBuffer[FD]

Return a reduced set of Functional Dependencies (FDs) with the redundant ones removed.

Return a reduced set of Functional Dependencies (FDs) with the redundant ones removed.

Value parameters

fd_

the set of Functional Dependencies (FDs) to use (defaults to fd)

Attributes

def shrink_LHS(fd_: ArrayBuffer[FD]): Unit

Shrink the LHS of each Functional Dependency (FD) that contains extraneous attributes.

Shrink the LHS of each Functional Dependency (FD) that contains extraneous attributes.

Value parameters

fd_

the set of Functional Dependencies (FDs) to use (defaults to fd)

Attributes

def subset_tables(p: ArrayBuffer[Attrs]): ArrayBuffer[Attrs]

Return the collection of tables that are subsets of any other table in p. Note, removal of a subset table may mean that a CHECK constraint (rather than a KEY constraint) will be required to enforce the affected FD.

Return the collection of tables that are subsets of any other table in p. Note, removal of a subset table may mean that a CHECK constraint (rather than a KEY constraint) will be required to enforce the affected FD.

Value parameters

p

the set of sub-schemas defining the tables

Attributes

def superkey(z: Attrs, ri: Attrs, fd_: ArrayBuffer[FD]): Boolean

Determine whether the attributes z form a superkey for sub-schema ri.

Determine whether the attributes z form a superkey for sub-schema ri.

Value parameters

fd_

the set of Functional Dependencies (FDs) to use (defaults to fd)

ri

the given sub-schema (a subset of r, defaults to r)

z

the given set of attributes

Attributes

Generated with