5.124. elements

DESCRIPTIONLINKSGRAPH
Origin

Derived from πšŽπš•πšŽπš–πšŽπš—πš.

Constraint

πšŽπš•πšŽπš–πšŽπš—πšπšœ(π™Έπšƒπ™΄π™Όπš‚,πšƒπ™°π™±π™»π™΄)

Arguments
π™Έπšƒπ™΄π™Όπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πšπšŸπšŠπš›,πšŸπšŠπš•πšžπšŽ-πšπšŸπšŠπš›)
πšƒπ™°π™±π™»π™΄πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πš’πš—πš,πšŸπšŠπš•πšžπšŽ-πšπšŸπšŠπš›)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(π™Έπšƒπ™΄π™Όπš‚,[πš’πš—πšπšŽπš‘,πšŸπšŠπš•πšžπšŽ])
π™Έπšƒπ™΄π™Όπš‚.πš’πš—πšπšŽπš‘β‰₯1
π™Έπšƒπ™΄π™Όπš‚.πš’πš—πšπšŽπš‘β‰€|πšƒπ™°π™±π™»π™΄|
πš›πšŽπššπšžπš’πš›πšŽπš(πšƒπ™°π™±π™»π™΄,[πš’πš—πšπšŽπš‘,πšŸπšŠπš•πšžπšŽ])
πšƒπ™°π™±π™»π™΄.πš’πš—πšπšŽπš‘β‰₯1
πšƒπ™°π™±π™»π™΄.πš’πš—πšπšŽπš‘β‰€|πšƒπ™°π™±π™»π™΄|
πšπš’πšœπšπš’πš—πšŒπš(πšƒπ™°π™±π™»π™΄,πš’πš—πšπšŽπš‘)
Purpose

All the items of π™Έπšƒπ™΄π™Όπš‚ should be equal to one of the entries of the table πšƒπ™°π™±π™»π™΄.

Example
πš’πš—πšπšŽπš‘-4 πšŸπšŠπš•πšžπšŽ-9,πš’πš—πšπšŽπš‘-1 πšŸπšŠπš•πšžπšŽ-6,πš’πš—πšπšŽπš‘-1πšŸπšŠπš•πšžπšŽ-6,πš’πš—πšπšŽπš‘-2πšŸπšŠπš•πšžπšŽ-9,πš’πš—πšπšŽπš‘-3πšŸπšŠπš•πšžπšŽ-2,πš’πš—πšπšŽπš‘-4πšŸπšŠπš•πšžπšŽ-9

The πšŽπš•πšŽπš–πšŽπš—πšπšœ constraint holds since each item of its first argument π™Έπšƒπ™΄π™Όπš‚ corresponds to an item of the πšƒπ™°π™±π™»π™΄ collection: the first item βŒ©πš’πš—πšπšŽπš‘-4 πšŸπšŠπš•πšžπšŽ-9βŒͺ of π™Έπšƒπ™΄π™Όπš‚ corresponds to the fourth item of πšƒπ™°π™±π™»π™΄, while the second item βŒ©πš’πš—πšπšŽπš‘-1 πšŸπšŠπš•πšžπšŽ-6βŒͺ of π™Έπšƒπ™΄π™Όπš‚ corresponds to the first item of πšƒπ™°π™±π™»π™΄.

Typical
|π™Έπšƒπ™΄π™Όπš‚|>1
πš›πšŠπš—πšπšŽ(π™Έπšƒπ™΄π™Όπš‚.πš’πš—πšπšŽπš‘)>1
|πšƒπ™°π™±π™»π™΄|>1
πš›πšŠπš—πšπšŽ(πšƒπ™°π™±π™»π™΄.πšŸπšŠπš•πšžπšŽ)>1
Symmetries
  • Items of π™Έπšƒπ™΄π™Όπš‚ are permutable.

  • Items of πšƒπ™°π™±π™»π™΄ are permutable.

  • All occurrences of two distinct values in π™Έπšƒπ™΄π™Όπš‚.πšŸπšŠπš•πšžπšŽ or πšƒπ™°π™±π™»π™΄.πšŸπšŠπš•πšžπšŽ can be swapped; all occurrences of a value in π™Έπšƒπ™΄π™Όπš‚.πšŸπšŠπš•πšžπšŽ or πšƒπ™°π™±π™»π™΄.πšŸπšŠπš•πšžπšŽ can be renamed to any unused value.

Usage

Used for replacing several πšŽπš•πšŽπš–πšŽπš—πš constraints sharing exactly the same table by one single constraint.

Reformulation

The πšŽπš•πšŽπš–πšŽπš—πšπšœ(βŒ©πš’πš—πšπšŽπš‘-I 1 πšŸπšŠπš•πšžπšŽ-V 1 ,πš’πš—πšπšŽπš‘-I 2 πšŸπšŠπš•πšžπšŽ-V 2 ,...,πš’πš—πšπšŽπš‘-I |π™Έπšƒπ™΄π™Όπš‚| πšŸπšŠπš•πšžπšŽ-V |π™Έπšƒπ™΄π™Όπš‚| βŒͺ,πšƒπ™°π™±π™»π™΄) constraint can be expressed in term of a conjunction of |π™Έπšƒπ™΄π™Όπš‚| πšŽπš•πšŽπš– constraints of the form:

Β Β Β πšŽπš•πšŽπš–(βŒ©πš’πš—πšπšŽπš‘-I 1 πšŸπšŠπš•πšžπšŽ-V 1 βŒͺ,πšƒπ™°π™±π™»π™΄),

Β Β Β πšŽπš•πšŽπš–(βŒ©πš’πš—πšπšŽπš‘-I 2 πšŸπšŠπš•πšžπšŽ-V 2 βŒͺ,πšƒπ™°π™±π™»π™΄),

Β Β Β ...

Β Β Β πšŽπš•πšŽπš–(βŒ©πš’πš—πšπšŽπš‘-I |π™Έπšƒπ™΄π™Όπš‚| πšŸπšŠπš•πšžπšŽ-V |π™Έπšƒπ™΄π™Όπš‚| βŒͺ,πšƒπ™°π™±π™»π™΄).

See also

implied by: πšŽπš•πšŽπš–πšŽπš—πšπšœ_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš.

part of system of constraints: πšŽπš•πšŽπš–, πšŽπš•πšŽπš–πšŽπš—πš.

Keywords

constraint type: data constraint, system of constraints.

filtering: arc-consistency.

modelling: table, shared table, functional dependency.

Arc input(s)

π™Έπšƒπ™΄π™Όπš‚ πšƒπ™°π™±π™»π™΄

Arc generator
π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πšπšŽπš–πšœ,πšπšŠπš‹πš•πšŽ)

Arc arity
Arc constraint(s)
β€’ πš’πšπšŽπš–πšœ.πš’πš—πšπšŽπš‘=πšπšŠπš‹πš•πšŽ.πš’πš—πšπšŽπš‘
β€’ πš’πšπšŽπš–πšœ.πšŸπšŠπš•πšžπšŽ=πšπšŠπš‹πš•πšŽ.πšŸπšŠπš•πšžπšŽ
Graph property(ies)
𝐍𝐀𝐑𝐂=|π™Έπšƒπ™΄π™Όπš‚|

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.124.1 respectively show the initial and final graph associated with the Example slot. Since we use the 𝐍𝐀𝐑𝐂 graph property, the arcs of the final graph are stressed in bold.

Figure 5.124.1. Initial and final graph of the πšŽπš•πšŽπš–πšŽπš—πšπšœ constraint
ctrs/elementsActrs/elementsB
(a) (b)
Signature

Since all the πš’πš—πšπšŽπš‘ attributes of πšƒπ™°π™±π™»π™΄ collection are distinct and because of the first condition πš’πšπšŽπš–πšœ.πš’πš—πšπšŽπš‘=πšπšŠπš‹πš•πšŽ.πš’πš—πšπšŽπš‘ of the arc constraint, a source vertex of the final graph can have at most one successor. Therefore |π™Έπšƒπ™΄π™Όπš‚| is the maximum number of arcs of the final graph and we can rewrite 𝐍𝐀𝐑𝐂=|π™Έπšƒπ™΄π™Όπš‚| to 𝐍𝐀𝐑𝐂β‰₯|π™Έπšƒπ™΄π™Όπš‚|. So we can simplify 𝐍𝐀𝐑𝐂 Β― Μ² to 𝐍𝐀𝐑𝐂 Β―.