Standards

[thesamchris]

• [x] Step 0: Boilerplate
• [x] Step 1: Setup the tableau
• [x] Step 2: Simple chase
• [x] Step 3: F-rule
• [x] Step 4: J-rule
• [x] Step 5: Entailment
• [x] Step 6: Lossless decomposition
• [x] Step 7: Projected dependencies
• [x] Step 8: Minimal cover
• [ ] Step 9: Dependency preservation

Tableau

A1	A2	A3	A4
a1	a2	b1	b2
b1	b2	b3	b4
a1	b2	a3	b4

Represented by:

{
  columns: ['A1', 'A2', 'A3', 'A4'],
  rows: [
      ['a1', 'a2', 'b1', 'b2'],
      ...
   ]
}

Functional dependencies

AB -> C,D

Represented by:

{
  lhs: ['A', 'B'],
  rhs: ['C', 'D'],
  mvd: false
}

Boilerplate

Assigned to: Amelia

Create a function that the front-end can call. Take in the relation, FDs, task + things relevant to task (e.g. entailment, take in FD/JD/MVD to chase).

This function should be accessible by something like

import Chase from 'chase.js';

Tasks: (+ help to create a set of constants we can import across the project)

• Entailment
• Lossless decomposition
• Projected dependencies
• Minimal cover
• Test for dependency preservation

const ENTAILMENT;
const LOSSLESS_DECOMPOSITION;
...

Step 1: Set up the Tableau

---

Assigned to: Sam Input: Relation (what columns), "What task is this?" (ref: constants from boilerplate)

If entailment, create two rows and distinguish the LHS

If lossless decomposition, on row per relation scheme, each row with non-distinguished variables (b1 ...) then distinguish based on the relation scheme.

Step 2: Run the Simple Chase (Test for implication of Functional Dependency only)

Assigned to: Input: Tableau, FDs,

Step 3: Apply F-rule

---

Assigned to: Input: Tableau Output: Tableau after F-rule applied

Follow 8.5.1

Step 4: Apply J-rule

Assigned to: Input: Tableau Output: Tableau after J-rule applied

Follow 8.5.2

Step 5: Entailment

Assigned to: Amelia Take in relation, FDs and FD/MVD/JD to chase

Steps:

1. Use step 1
2. Use step 3/4
3. When no change, then check if RHS has column of distinguished variables

Step 6: Lossless decomposition

Assigned to: Sam Take in relation, FDs and relation scheme

Steps:

1. Use step 1
2. Use step 3/4
3. When no change, then check if there is a row of distinguished variables

Step 7: Projected dependencies

Assigned to: Sam Use step 5 for entailment in Algorithm below

Step 8: Minimal cover

Assigned to: Amelia

1. For each FD, use step 5 to check if its entailed
2. If any are entailed return 'false', i.e. not a min cover. Else, return true.

Step 9: Dependency preservation

---

Assigned to: Amelia + Sam (??)

Given a relation, a set of C of dependencies and a relation scheme find if the relation scheme is dependency preserving.

Steps:

1. For each relation scheme, find the projected dependencies.
2. For each dependency in the set C, see if they can be entailed by any of the set of projected dependencies.
3. If all dependencies in C can be entailed, then the relation scheme is dependency preserving.

[ameliatjy]

Specification and example of usage of chase function

Given the following Relation: A, B, C, D Dependencies: {A} ->-> {B, C}, {D} -> {C} To chase: {A} -> {C}

const relation = ['A', 'B', 'C', 'D']
const fds = [
  {
    lhs: ['A'],
    rhs: ['B', 'C'],
    mvd: true
  },
  {
    lhs: ['D'],
    rhs: ['C'],
    mvd: false
  }
]
const task = TASK_ENTAILMENT
const otherInfo = {
  lhs: ['A'],
  rhs: ['C'],
  mvd: false 
}
chase(relation, fds, task, TYPE_SIMPLE_CHASE, otherInfo)

Output:

{
  result: true,
  steps: [
    {
      description: "...",
      tableau: [
        {
          columns: ['A1', 'A2', 'A3', 'A4'],
          rows: [
            ['a1', 'a2', 'b1', 'b2'],
            ...
          ]
        },
        {...}
      ]
    },
    {...}
  ],
  finalTableau: ...
}

Note: For projected dependencies, result in the output object will be the set of functional dependencies that satisfies the projection.

Specifics of otherInfo object passed to function

For entailment, include the dependency to chase for as such:

const otherInfo = {
  lhs: ['A'],
  rhs: ['C'],
  mvd: false 
}

For lossless decomposition, include table decomposition schema as such:

const otherInfo = {
  relationSchemes: [
    ['A', 'B', 'C'],
    ['C', 'D']
  ] 
}

For projected dependencies, include subset of relation as such:

const otherInfo = {
  projection: ['A', 'B', 'C']
}

For minimal cover, pass null as otherInfo.

For test for dependency preservation, include schemas of the decomposed fragments as such:

const otherInfo = {
  relationSchemes: [
    ['A', 'B', 'C'],
    ['A', 'D']
  ]
}

[thesamchris]

SFLR

otherInfo

• For lossless decomposition and dependency preservation, can we use relationSchemes as the key instead of tables?
• For projected dependencies, can we use projections as the key instead of relation?
• For minimal cover, we do not need otherInfo because the fds are the other info - since we are seeing if there are any redundant functional dependencies in the fds provided. If there is a redundant FD in fds then it is not a minimal cover.