Welcome to DB-FDs documentation

class db_fds.fdfuncs.FunctionalDependency(fro: Symbol | set[Symbol], to: Symbol | set[Symbol])

A class to represent a functional dependency (FD) between two sets of attributes. Two FDs are equal if their LHS (fro) are equal and their RHS (to) are equal.

Attributes:

fro (set[Symbol]): Set of attributes that determine another set of attributes. to (set[Symbol]): Set of attributes that is determined by fro. lhs (set[Symbol]): Alias for fro. rhs (set[Symbol]): Alias for to.

otherrep() → str

Alternative representation of the FD using Symbol::otherrep.

class db_fds.fdfuncs.Symbol(name: str, desc: str = '')

A class for the smallest element of Functional Dependency logic. Use this to represent relation attributes. Name should be unique: Two Symbols with the same name will return True when checked with equality ==. Other comparisons are also done by name.

Attributes:

name (str): Name of the attribute/symbol. This is the main representation. desc (str, optional): Alternative descriptor, used with Symbol::otherrep

otherrep() → str

Alternative representation of the Symbol using its description.

db_fds.fdfuncs.all_subset_closures(attrs: set[Symbol], fds: set[FunctionalDependency]) → dict[frozenset[Symbol], set[Symbol]]

Calculates the closure for all attribute subsets.

Args:

attrs (set[Symbol]): Full set of attributes to compute on. fds (set[FunctionalDependency]): Set of FDs to calculate closure using.

Returns:

dict[frozenset[Symbol], set[Symbol]]: Dictionary containing closure of every attribute subset combination.

Note that the key is a frozenset due to hashing limitations.

Raises:

TypeError: If input sets contain unexpected types.

db_fds.fdfuncs.canonical_cover(fds: set[FunctionalDependency], minimum_cover: set[FunctionalDependency] = None) → set[FunctionalDependency]

Calculates the canonical cover / basis of a set of FDs. Note: Canonical cover is equivalent to the minimal cover with the Union Rule applied.

Args:

fds (set[FunctionalDependency]): Initial set of FDs.

Returns:

set[FunctionalDependency]: Canonical basis of input FDs.

Raises:

TypeError: Via minimal_cover

db_fds.fdfuncs.compute_closure(attrs: set[Symbol], fds: set[FunctionalDependency]) → set[Symbol]

Calculates the closure of a set of attributes with respect to the given FDs. The closure is defined as the set of attributes that can be determined from the input attributes using the FDs.

Args:

attrs (set[Symbol]): The set of Symbols to compute closure for. fds (set[FunctionalDependency]): FDs to use for closure.

Returns:

set[Symbol] The closure.

Raises:

TypeError: If input sets contain unexpected types.

db_fds.fdfuncs.find_keys(superkeys: set[frozenset[Symbol]] = None, attrs: set[Symbol] = None, fds: set[FunctionalDependency] = None) → set[frozenset[Symbol]]

Finds all candidate keys (or just keys) for a relation. This is a set of minimal superkeys, i.e. removing an attribute from any subset in this list makes it no longer a key.

IMPORTANT: Either superkeys or both of (attrs, fds) must be provided. If superkeys is provided, other arguments will be ignored.

Args:

superkeys (set[frozenset[Symbol]], optional): A set of superkeys for the relation. If not provided, superkeys will first be computed from attrs and fds. attrs (set[Symbol], optional): Set of attributes in the relation. fds (set[FunctionalDependency]): Set of FDs of the relation.

Returns:

set[frozenset[Symbol]]: Set containing a list of all attribute combinations that act as candidate keys for the relation. Note that it must be a set of frozensets due to hashing limitations.

Raises:

TypeError: Via find_superkeys.

db_fds.fdfuncs.find_superkeys(attrs: set[Symbol], fds: set[FunctionalDependency]) → set[frozenset[Symbol]]

Finds all superkeys of a relation.

Args:

attrs (set[Symbol]): Set of attributes in the relation. fds (set[FunctionalDependency]): Set of FDs of the relation.

Returns:

set[frozenset[Symbol]]: Set containing a list of all attribute combinations that act as superkeys for the relation.

Note that it must be a set of frozensets due to hashing limitations.

Raises:

TypeError: If input sets contain unexpected types.

db_fds.fdfuncs.get_augmented(fds: FunctionalDependency | set[FunctionalDependency], others: Symbol | set[Symbol]) → set[FunctionalDependency]

Gets all FDs derived from Armstrong’s Axiom of Augmentation.

Args:

fds (FunctionalDependency or set[FunctionalDependency]): Set of dependencies to augment. others (Symbol or set[Symbol]): Symbol`s to augment `fds with.

Returns:

set[FunctionalDependency]: Derived Functional Dependencies, excluding the original(s).

Raises:

TypeError: If the function encounters invalid types.

Example:

Given FD A –> B returns Ax –> Bx for all x combinations in others.

db_fds.fdfuncs.get_reflexive(lhs_attrs: Symbol | set[Symbol]) → set[FunctionalDependency]

Gets all FDs derived from Armstrong’s Axiom of Reflexivity.

Args:

lhs_attrs (Symbol or set[Symbol]): Attribute(s) to get reflexive FDs from. This set will appear on the LHS of all returned FDs.

Returns:

set[FunctionalDependency]: All derived Functional Dependencies.

Raises:

TypeError: If the function encounters anything in lhs_attrs that is not a Symbol.

Examples:

Given attributes ABC, it can determine any subset of ABC. >>> get_reflexive({A, B}) {AB –> A, AB –> B, AB –> AB}

db_fds.fdfuncs.get_transitive(fds: set[FunctionalDependency]) → set[FunctionalDependency]

Gets all FDs derived from Armstrong’s Axiom of Transitivity.

Args:

fds (set[FunctionalDependency]): Set of dependencies to check.

Returns:

set[FunctionalDependency]: Derived dependencies, not including the inputs.

Raises:

TypeError: If any type other than FunctionalDependency encountered in the input.

Example:

Given FDs A –> B and B –> C, returns A –> C.

db_fds.fdfuncs.make_decomposed(fds: FunctionalDependency | set[FunctionalDependency]) → set[FunctionalDependency]

Returns a decomposed set of FDs from the input.

Args:

fds (FunctionalDependency or set[FunctionalDependency]): Set of FDs to decompose.

Returns:

set[FunctionalDependency]: Decomposed FDs, as well as any from the input that were already in a decomposed form.

Does not include FDs that were identified as non-decomposed.

Raises:

TypeError: If any type other than FunctionalDependency encountered in the input.

Examples:

>>> make_decomposed({A --> B, B --> CD})
{A --> B, B --> C, B --> D}

db_fds.fdfuncs.make_union(fds: set[FunctionalDependency]) → set[FunctionalDependency]

Returns a set of FDs with the Rule of Union applied.

Args:

fds (FunctionalDependency or set[FunctionalDependency]): Set of FDs to apply union to.

Returns:

set[FunctionalDependency]: All FDs that were either

1. Were not used in any union (already in most combined form).

2. Result of a union.

Does not include FDs that produced a new FD by union.

Raises:

TypeError: If fds contains a type other than FunctionalDependency.

Examples:

>>> make_union({A --> B, A --> C, B --> D})
{B --> D, A --> BC}

db_fds.fdfuncs.minimal_cover(fds: set[FunctionalDependency]) → set[FunctionalDependency]

Calculates the minimal cover / basis of a set of FDs.

Args:

fds (set[FunctionalDependency]): Initial set of FDs.

Returns:

set[FunctionalDependency]: Minimal basis of input FDs.

Raises:

TypeError: Via make_decomposed

db_fds.fdfuncs.non_trivial_n_decomposed(attrs: set[Symbol], fds: set[FunctionalDependency]) → set[FunctionalDependency]

Returns all ‘non-trivial and decomposed’ Functional Dependencies:

• Non-Trivial: If a Symbol exists on the LHS of an FD, it will not appear on the RHS.

• Decomposed: All RHS will only contain a single Symbol.

Any FDs not in the initial arguments will be derived.

Args:

attrs (set[Symbol]): Set of attributes in the relation. fds (set[FunctionalDependency]): Set of FDs of the relation.

Returns:

set[FunctionalDependency]: Set of all non-trivial and decomposed FDs.

Raises:

TypeError: Via all_subset_closures.

Indices and tables

• Index

• Module Index

• Search Page