5.126. elements_sparse

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 πšƒπ™°π™±π™»π™΄ or to the default value π™³π™΄π™΅π™°πš„π™»πšƒ if the entry π™Έπšƒπ™΄π™Όπš‚.πš’πš—πšπšŽπš‘ does not occurs among the values of the index attribute of the πšƒπ™°π™±π™»π™΄ collection.

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

The πšŽπš•πšŽπš–πšŽπš—πšπšœ_πšœπš™πšŠπš›πšœπšŽ constraint holds since:

  • The first and third items (items βŒ©πš’πš—πšπšŽπš‘-8 πšŸπšŠπš•πšžπšŽ-9βŒͺ and βŒ©πš’πš—πšπšŽπš‘-2 πšŸπšŠπš•πšžπšŽ-5βŒͺ) of its π™Έπšƒπ™΄π™Όπš‚ collection respectively correspond to the fourth and second item of its πšƒπ™°π™±π™»π™΄ collection.

  • The πš’πš—πšπšŽπš‘ attribute of the second item of its π™Έπšƒπ™΄π™Όπš‚ collection (i.e.,Β value 3) does not correspond to any index of the πšƒπ™°π™±π™»π™΄ collection. Therefore the πšŸπšŠπš•πšžπšŽ attribute of the second item of the π™Έπšƒπ™΄π™Όπš‚ collection is set the the default value 5 given by the last argument of the πšŽπš•πšŽπš–πšŽπš—πšπšœ_πšœπš™πšŠπš›πšœπšŽ constraint.

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 sparse table by one single constraint.

Reformulation

Let 𝙸 k and πš… k respectively denote π™Έπšƒπ™΄π™Όπš‚[k].πš’πš—πšπšŽπš‘ and π™Έπšƒπ™΄π™Όπš‚[k].πšŸπšŠπš•πšžπšŽ (k∈[1,|π™Έπšƒπ™΄π™Όπš‚|[]). The πšŽπš•πšŽπš–πšŽπš—πšπšœ_πšœπš™πšŠπš›πšœπšŽ(π™Έπšƒπ™΄π™Όπš‚,πšƒπ™°π™±π™»π™΄,π™³π™΄π™΅π™°πš„π™»πšƒ) constraint can be expressed in term of |π™Έπšƒπ™΄π™Όπš‚|[ reified constraints of the form:

((𝙸 k =πšƒπ™°π™±π™»π™΄[1].πš’πš—πšπšŽπš‘βˆ§πš… k =πšƒπ™°π™±π™»π™΄[1].πšŸπšŠπš•πšžπšŽ) ∨

Β (𝙸 k =πšƒπ™°π™±π™»π™΄[2].πš’πš—πšπšŽπš‘βˆ§πš… k =πšƒπ™°π™±π™»π™΄[2].πšŸπšŠπš•πšžπšŽ) ∨

Β ...

Β (𝙸 k =πšƒπ™°π™±π™»π™΄[|πšƒπ™°π™±π™»π™΄|].πš’πš—πšπšŽπš‘βˆ§πš… k =πšƒπ™°π™±π™»π™΄[πšƒπ™°π™±π™»π™΄|].πšŸπšŠπš•πšžπšŽ)) ∨

((𝙸 k β‰ πšƒπ™°π™±π™»π™΄[1].πš’πš—πšπšŽπš‘) ∧

Β (𝙸 k β‰ πšƒπ™°π™±π™»π™΄[2].πš’πš—πšπšŽπš‘) ∧

Β ...

Β (𝙸 k β‰ πšƒπ™°π™±π™»π™΄[|πšƒπ™°π™±π™»π™΄|].πš’πš—πšπšŽπš‘) ∧

Β (πš… k =π™³π™΄π™΅π™°πš„π™»πšƒ)).

See also

common keyword: πšŽπš•πšŽπš–, πšŽπš•πšŽπš–πšŽπš—πšΒ (data constraint), πšŽπš•πšŽπš–πšŽπš—πš_πšœπš™πšŠπš›πšœπšŽΒ (sparse table).

implied by: πšŽπš•πšŽπš–πšŽπš—πš_πšœπš™πšŠπš›πšœπšŽ.

part of system of constraints: πšŽπš•πšŽπš–πšŽπš—πš_πšœπš™πšŠπš›πšœπšŽ.

Keywords

characteristic of a constraint: derived collection.

constraint type: data constraint, system of constraints.

filtering: arc-consistency.

modelling: table, shared table, sparse table, sparse functional dependency.

Derived Collections
πšŒπš˜πš•π™³π™΄π™΅-πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πš’πš—πš,πšŸπšŠπš•πšžπšŽ-πš’πš—πš),πš’πšπšŽπš–(πš’πš—πšπšŽπš‘-0,πšŸπšŠπš•πšžπšŽ-π™³π™΄π™΅π™°πš„π™»πšƒ)]
πšŒπš˜πš•πšƒπ™°π™±π™»π™΄_𝙳𝙴𝙡-πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πšπšŸπšŠπš›,πšŸπšŠπš•πšžπšŽ-πšπšŸπšŠπš›),πš’πšπšŽπš–(πš’πš—πšπšŽπš‘-πšƒπ™°π™±π™»π™΄.πš’πš—πšπšŽπš‘,πšŸπšŠπš•πšžπšŽ-πšƒπ™°π™±π™»π™΄.πš’πš—πšπšŽπš‘),πš’πšπšŽπš–(πš’πš—πšπšŽπš‘-𝙳𝙴𝙡.πš’πš—πšπšŽπš‘,πšŸπšŠπš•πšžπšŽ-𝙳𝙴𝙡.πšŸπšŠπš•πšžπšŽ)
Arc input(s)

π™Έπšƒπ™΄π™Όπš‚ πšƒπ™°π™±π™»π™΄_𝙳𝙴𝙡

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

Arc arity
Arc constraint(s)
β€’ πš’πšπšŽπš–πšœ.πšŸπšŠπš•πšžπšŽ=πšπšŠπš‹πš•πšŽ_𝚍𝚎𝚏.πšŸπšŠπš•πšžπšŽ
β€’ πš’πšπšŽπš–πšœ.πš’πš—πšπšŽπš‘=πšπšŠπš‹πš•πšŽ_𝚍𝚎𝚏.πš’πš—πšπšŽπš‘βˆ¨πšπšŠπš‹πš•πšŽ_𝚍𝚎𝚏.πš’πš—πšπšŽπš‘=0
Graph property(ies)
ππ’πŽπ”π‘π‚π„=|π™Έπšƒπ™΄π™Όπš‚|

Graph model

An item of the π™Έπšƒπ™΄π™Όπš‚ collection may have up to two successors (see for instance the third item of the π™Έπšƒπ™΄π™Όπš‚ collection of the Example slot). Therefore we use the graph property ππ’πŽπ”π‘π‚π„=|π™Έπšƒπ™΄π™Όπš‚| for enforcing the fact that each item of the π™Έπšƒπ™΄π™Όπš‚ collection has at least one successor.

PartsΒ (A) andΒ (B) of FigureΒ 5.126.1 respectively show the initial and final graph associated with the Example slot. Since we use the ππ’πŽπ”π‘π‚π„ graph property, the vertices of the final graph are drawn with a double circle.

Figure 5.126.1. Initial and final graph of the πšŽπš•πšŽπš–πšŽπš—πšπšœ_πšœπš™πšŠπš›πšœπšŽ constraint
ctrs/elements_sparseActrs/elements_sparseB
(a) (b)
Signature

On the one hand note that π™Έπšƒπ™΄π™Όπš‚ is equal to the number of sources of the initial graph. On the other hand note that, in the initial graph, all the vertices that are not sources correspond to sinks. Since isolated vertices are eliminated from the final graph the sinks of the initial graph cannot become sources of the final graph. Therefore the maximum number of sources of the final graph is equal to π™Έπšƒπ™΄π™Όπš‚. We can rewrite ππ’πŽπ”π‘π‚π„=|π™Έπšƒπ™΄π™Όπš‚| to ππ’πŽπ”π‘π‚π„β‰₯|π™Έπšƒπ™΄π™Όπš‚| and simplify ππ’πŽπ”π‘π‚π„ Β― Μ² to ππ’πŽπ”π‘π‚π„ Β―.