Towards declarative comparabilities: application to functional dependencies
Lhouari Nourine Jean Marc Petit Simon Vilmin

	



































Towards declarative comparabilities: application to functional 
dependencies.This research is supported by the French government 
		IDEXISITE initiative 16-IDEX-0001 (CAP 20-25). The last author is funded by the 
		CNRS, France, ProFan project.
    
	Lhouari NourineLIMOS, Université Clermont Auvergne, France.
	
	Jean-Marc PetitLIRIS, CNRS, Université de Lyon, France.
	footnote-2 
	Simon Vilmin
    December 11th, 2019; revised on July 2nd, 2021
====================================================================================================================================================================================================================================================




Whether two values can be considered as equal is more subtle and complex than it seems. 

In practice, only domain experts could tell what does “equality” mean.

Surprisingly, declarative frameworks allowing to specify equality at a highlevel of 
abstraction are missing.

Thus, we introduce a lattice-based declarative framework to cope with this issue.

First, we assign a comparability function to each attribute of the relation scheme.

This function maps each pair of the attribute's domain to a truth value in a 
truth lattice.

Then, we associate a lattice of comparabilities to every relation, comparing pairwise its 
tuples.

We define realities being {0, 1}-interpretations of this lattice.

Realities model several interpretations of equality.

In this setting, we define abstract FDs, from which the semantics of classical 
FDs can be recovered with realities.

Eventually, we apply the notions of possible/certain answers in databases to FDs and 
study associated complexity and problems.	

5ptKeywords: Database theory, lattices, comparability function,
truth lattice, abstract functional dependency, possible functional dependency.
	









§ INTRODUCTION




A simple yet fundamental question in data management is  the following: given two values 
u and v, how to decide whether or 
not u = v, or at least under which assumptions those values are close enough to be 
considered as equal?
Clearly, there does not exist a unique answer, many interpretations of equality being 
indeed possible.
This question is often implicit in database applications such as query answering 
<cit.>, data 
integration 
<cit.>, inconsistent databases <cit.>, 
probabilistic data 
<cit.> or database design <cit.>.
However, it is also crucial to deal with data quality issues. 
Moreover, in practice, domain experts are often the only ones who could specify what does 
“equality”  mean on their data in a given context.
To the best of our knowledge, declarative frameworks allowing them to specify at a high 
level of abstraction the different possible interpretations of equality in their data 
(taking into account measurement errors, null values, etc.) are still lacking.
As a consequence, the treatment of different types of equality is left to programmers, 
who have to struggle with those different interpretations in their code.

In this paper, we introduce a lattice-based declarative framework to cope with this 
problem, and study its impact on functional dependencies (FDs).
Each attribute of a relation scheme is given a comparability function that maps 
every pair of the attribute's domain to a truth value in a fine-grained 
similarity scale, ordered in a truth lattice. 
In practice, this knowledge should be given by a domain expert beforehand.
For each attribute, the combination of the comparability functions and the truth lattices 
form the attribute context.
It extends the built-in knowledge on the attribute.
The schema context (the combination of attribute contexts) forms a 
database framework which comes to extend the relation scheme.
Therefore, we consider that a relation is given over a schema context instead of solely a 
relation scheme.

(running example)
An expert has been recording medical parameters on some patients: their triglyceride 
level (mmol/L), their gender (M/F) and their waist size (cm).
A sample of these records is represented in a relation in Figure <ref>.
For the sake of simplicity, we denote these parameters by A, B, C respectively.
We put = {A, B, C} as the relation scheme.



On top of , the expert has been providing comparability functions for each of 
these parameters:


    f_A(x, y) = good    if  x = y  or  x, y ∈ [0, 2[ 
    good or bad    if  x, y ∈ [2, 5[, x ≠ y 
    unknown    if  (x, y)  or  (y, x) ∈ [0, 2[ × [2, 5[ 
    bad   otherwise.


    f_B(x, y) = true    if  x = y 
    different    if  x ≠ y


    f_C(x, y) = correct    if  x = y ≠null or  x, y ∈ [70, 80]
    unknown    if  u = null or  v = null
    incorrect   otherwise.


The codomains of these functions, the abstract domain of each attribute, are given as the 
lattices _A, _B, _C in <ref>.
We use abbreviations for each value: g stands for good, gb for good 
or bad, b for bad, u for unknown, c for correct, i 
for incorrect and d for different.
The set _ = {{f_A, _A}, {f_B, _B}, {f_C, _C}} is the 
schema context over which r is defined.


Thus, given 2 tuples of a relation, their comparison gives rise to an abstract 
	tuple, a precise account of the truth of their agreement on each component.
This comparison, obtained according to the background knowledge, naturally extends 
equality.

 
(Continued) If we consider t_1, t_2 in r, we have f_(t_1, t_2) = ⟨ 
f_A(1.4, 1.5), f_B(F, F),  f_C(73, null) ⟩ = ⟨ g, 
t, u ⟩.
Thus, ⟨ g, t, u ⟩ is an abstract tuple of r.


The set of abstract tuples associated to a relation induces an abstract lattice 
over the product of truth lattices.
From our example, the abstract lattice _r associated to r is given in Figure 
<ref>.
The abstract lattice lays the ground for abstract functional dependencies as a 
generalization of classical FDs.
They are lattice implications x  y, where x and y are elements of the product 
of truth lattices, which have the following meaning: the partial knowledge described by 
x is 
sufficient to guarantee a degree of certainty higher than y.
Data dependencies are also well-studied in presence of incomplete information as 
they deal with errors or uncertainty and similarity/dissimilarity 
<cit.>.



Then, we define {0, 1}-interpretations of such lattices which make it possible to see 
equalities under different angles.
The truth value of two abstract tuples t, t' can be interpreted as their degree of 
equality.
It is true if the interpretation of the truth value is 1, and false if it 
is 0.
In particular, we are interested in realities: they are those interpretations 
which satisfy two natural rules: they are increasing and they preserve the classical 
AND operation, true and true will also be interpreted as 
true.
As a side effect, the equality (1) can be represented by a unique minimum element in 
each truth lattice, which can be thought as a threshold for deciding whether two tuples 
agree or not on an attribute.

Interestingly, realities do not only capture several meanings of equality but they also 
have the ability to recover the semantic of FDs, 
thus drawing a parallel between abstract FDs, and FDs that we obtain after interpretation 
of the abstract lattice. 
We also study strong realities, that do not only sets a minimum threshold for 
equality, but also set a maximum threshold for difference.
In this way, the interpretations of truth values respect the classical OR, AND rules 
of boolean logic.
As the relation is based on the schema context, declaring a reality could be done with a 
proper data definition language (DDL), not described in this paper.
Quite clearly, this framework offers to domain experts an opportunity to specify at a 
high level of abstraction different types of equality on top of database schemas, 
independently of the underlying applications.

(Continued)
The expert gives several hypotheses on the meaning of equality with respect to her data.
They lead to three possible interpretations g_0, g_1, g_2 of the truth values which are 
represented in <ref> (a), (c) and (e).
These interpretations are furthermore realities.
Each of these realities gives a different interpretation of the abstract lattice _r 
illustrated in <ref> (b), (d) and (f).
These interpretations also induce different functional dependencies among attributes of 
.
For instance A  C holds in both g_0(_r) and g_2(_r), but not in 
g_1(_r), which suggests a connection in the data between the triglyceride level 
(A) and the waist size (C).
In fact, this relationship can be directly expressed as a dependency based on similarity 
values: as long as the triglyceride level is at least good or bad (gb), 
we can guarantee that the waist size is not incorrect (i).
This is represented by the abstract functional dependency ⟨ gb, d, i ⟩⟨ b, d, u ⟩ which holds in _r.





Eventually, our framework allows to introduce the notion of plausibility 
(certain/possible) of a given FD, inspired from query answering 
<cit.>.
More precisely, the existence of numerous realities lead to cases of equality semantic 
where the FD holds, and some other for which it does not.
In this case, the FD is possible.
In practice, this may occur if for instance the relation suffers from unclean data: a FD 
(such as waist size, gender  triglyceride for instance in our example) 
should theoretically hold with respect to background knowledge, but due to 
mismeasurements or imprecisions, it fails to do so.
Here, weakening/strengthening the meaning of equality according to expert knowledge could 
easily
fix this problem, by simply applying the “right” reality with 
respect to the background knowledge.
After possibility, it is also natural to wonder for a given FD if there is a 
chance that it holds in any reality, in which case we say that it is certain.

(Continued)
According to her background knowledge, the domain expert should be able to recover a 
well-known rule from the data: women with large waist size have in general a 
high triglyceride level, BC  A.
In other words, this FD should be possible.
However, due to data quality problems, the validity of this FD depends on the 
interpretation of equality given by the expert.

For instance, the reality g_1 given in <ref> is the unique 
reality among g_0, g_1, g_2 which interprets _r in a way that BC  A is valid.


Paper contribution.
We summarize the main contributions of this paper:


  * We introduce a formalism at the database schema level allowing to consider 
different interpretations of equalities as first class citizen.

  * We show that any relation is associated to an abstract 
lattice, thus introducing abstract functional dependencies.

  * We characterize those interpretations, realities and strong 
	realities, which ensure that the image of any abstract lattice preserves the 
	semantic of 
classical FDs. 
By doing so, we show the strong connection, relying on realities, between abstract 
FDs 
and usual FDs.

  * We investigate the plausibility of a given functional dependency: whether there 
exists 
at least a reality for which the FD holds, or whether it holds for any 
reality. We also discuss this problem for the case of strong realities and show that 
deciding possibility in this context is untractable.



Paper organisation. 
The <ref> recalls standard notions from database and lattice 
theory.
Then, we introduce our formalism based on truth lattices and binary 
interpretations in <ref>.
We show that any relation can be associated to an abstract 
lattice, thus giving a semantic for abstract functional dependencies.
We prove in <ref> that under certain circumstances, an interpretation 
preserves the validity of classical FDs for any abstract lattice. 
These interpretations are called realities and strong realities.
We show in <ref> a connection between abstract and classical FDs 
using (strong) realities.
In <ref> we discuss certain/possible FDs.
The <ref> summarizes related works.
We conclude with some perspectives in <ref>.








§ PRELIMINARIES



All the objects considered in this paper are finite. 
First, we recall standard databases definitions <cit.>.

A relation scheme  is a (finite) set of attributes A_1, …, A_n, 
for n ∈N. 
Its powerset is written 2^.
Each attribute A_i has values in some set (A_i) called the 
domain of A_i.
The domain of  is the union of attributes domain, that is () = ⋃_A ∈(A).
Capital first letters of the alphabet A, B, C represent attributes, and capital last 
letters such as X, Y, Z denote sets of attributes. 
We write XY as a shortcut for X ∪ Y, and A_1A_2A_3 for {A_1, A_2, A_3}.
A tuple t over  is a mapping t →() such that t[A] ∈(A) for each A ∈, where t[A] is the projection of t on A.
Similarly, t[X], for some X ⊆, denotes the projection of t on X.
A relation r is a collection of tuples over .
A functional dependency (FD) over  is a pair (X, A) usually written X  A, where X ⊆ and A ∈. 
If  is clear, we simply write X  A. 
We assume w.l.o.g. that X  A is not trivial, A ∉X.
Let r be a relation over . 
We say that r satisfies the functional dependency X  A if for any pair 
t_1, t_2 of tuples in r, t_1[X] = t_2[X] implies t_1[A] = t_2[A].
This is written r  X  A.

We move to definitions from lattice theory <cit.>.
Let S be a set. 
A partial order or poset is a pair (S, ≤) where ≤ is a binary 
relation which is reflexive, transitive and anti-symmetric. 
Let x, y ∈ S. 
We say that x and y are comparable if x ≤ y or y ≤ x. 
Otherwise, they are incomparable which is written x  y. 
A lower bound ℓ of x and y is an element of S satisfying ℓ≤ x 
and ℓ≤ y. 
If moreover, for any lower bound ℓ' of x, y we have ℓ' ≤ℓ, ℓ is 
called the meet of x and y. 
We shall denote it by x  y. 
Dually, an upper bound of x, y is an element u ∈ S such that x ≤ u and 
y ≤ u. 
If u is minimal with respect to all upper bounds of x, y it is the join of x 
and y. 
We write it x  y.
For X ⊆ S, the meet X and join X of X are defined accordingly.
A poset in which every pair of elements has both a meet and a join is a lattice.
A lattice will be noted (S, ≤, , ) or simply  when precisions are not 
necessary.
It has a minimum element 0 called the bottom, and a maximum one, the top 
denoted by 1.
Let  be a lattice, and x, y, z ∈ such that y < x (y ≤ x and y 
≠ x).
If for any z ∈, y < z ≤ x implies x = z, then we say that x 
covers y and we write y ≺ x.
An element a ∈ which covers the bottom 0 of  is called an atom.
We denote by A() the set of atoms of .
Let m ∈.
We say that m is meet-irreducible if for any x, y ∈, m = x  y 
implies m = x or m = y.
A join-irreducible element j is defined dually with .
Meet-irreducible elements (resp. join-irreducible elements) of  are denoted by 
M() (resp. J()).
Let _1, _2 be two lattices. 
A map φ_1 →_2 is increasing if for any x, y ∈_1, x ≤ y implies φ(x) ≤φ(y).
It is a -homomorphism if for any x, y ∈_1, φ(x  y) = 
φ(x) φ(y). 
Decreasing maps and -homomorphisms are defined dually. 
The map φ is a homomorphism if it is both a -homomorphism and a 
-homomorphism. 
If _1, …, _n are lattices, the cartesian product ∏_i = 1^n_i 
with component-wise induced order is the direct product of _1, …, 
_n. 
One has x ≤ y if and only if x_i ≤ y_i for every 1 ≤ i ≤ n. 
If  is a lattice, a -sublattice ' of  is a lattice which is 
a subset of  such that x, y ∈' implies x  y ∈'.

Now we introduce lattice implications and closure operator, based on definitions and 
results of <cit.>.
Let  be a lattice and →.
The map  is a closure operator if for any x, y ∈, x ≤(x) 
(extensive), x ≤ y (x) ≤(y) (increasing) and ((x)) = 
(x) (idempotent).
Then, (x), also written x^+ when  is understood from the context, is the 
closure of x with respect to .
The set _ = () = {x ∈|(x) = x } of fixed points (or 
closed elements) of  is a -sublattice of  which contains the top of .
Therefore we also have that x^+ = {y ∈_| x ≤ y }.
The set of all such -sublattices of  is denoted ().
When  equals 2^ for some attribute set  and  is a closure operator on 
, _ is a closure system 
<cit.> (in this case  is the set intersection ∩).
A (lattice) implication is a pair x  y such that x, y ∈.
We say that an element z ∈ satisfies the implication x  y if x ≤ z 
 y ≤ z, and we write z  x  y.
Let  be a set of implications over .
Then  induces a closure operator ^ on  such that x ∈ is
closed if and only if x.
Formally, _^ = { x ∈| x }.
Dually, any closure operator  on , and hence any ' ∈(), can be 
represented by implications <cit.>.
Let ' ∈() and x  y be an implication on .
We have that ' satisfies x  y, written '  x  y if for 
any z ∈', z  x  y.
The notion ' follows.
We have the following folklore property: '  x  y if and only if y 
≤ x^+.








§ SCHEMA CONTEXT AND ABSTRACT FUNCTIONAL DEPENDENCIES



For every attribute A ∈, the first step is to define truth values whenever two 
elements of (A) are compared. 
The abstract domain of A, denoted by A, is a finite set of truth 
values(resp.) disjoint from the domain (A), representing comparabilities between 
every pair of values in (A).
Moreover, we assume that a partial order ≤_A, or simply ≤ when no confusion 
arises, exists over A such that the poset _A = (A, ≤_A) is a 
lattice.
We say that _A is the truth lattice of A.
We put 0_A and 1_A  as the bottom and top elements (resp.) of _A.
The abstract domain  of  is the direct product of 
abstract domains, = ∏_A ∈A.
Two attributes can have the same abstract domain.

We now define the explicit mapping of pairs of domain values to truth values through a 
comparability function. 
A comparability function for an attribute A, denoted by f_A, is a (surjective) 
map from (A) ×(A) to A which subsumes equality (f_A(x_A, 
x_A) = 1_A) and is commutative (f_A(x_A, y_A) = f_A(y_A, x_A)).
Let t_1, t_2 be two tuples over .
The comparability function f_ for  is the combination of comparability 
functions on attributes of .
It is defined from ()^n ×()^n to  as follows:


    f_(t_1, t_2) = ⟨ f_A_1(t_1[A_1], t_2[A_1]), …, f_A_n(t_1[A_n], 
    t_2[A_n]) ⟩


Note that f_(t_1, t_2) is a generalization of agree sets for FDs 
between two tuples <cit.>.
For any relation r over , we put f_(r) = { f_(t_1, t_2) | t_1, t_2 ∈ 
r}.
Let us denote by _ = (, ≤_) the direct product of truth lattices.
An element of _ is an abstract tuple (see <ref>).
We now introduce attribute context and schema context:


Let A ∈.
An attribute context for A, denoted by _A, is represented 
by the pair {f_A, _A}. 
A schema context for a relation scheme , denoted by _, is defined 
by _ = {_A | A ∈}.


From a schema context _, we have both its associated comparability function 
f_ and its abstract domain .
When clear from the context, the subscript  will be omitted, we shall use ≤, 
, instead of ≤_, _, _ respectively.
In the sequel, a relation r will be defined over a schema context _, instead of 
. 
Thus, every relation r over _ is associated to a -sublattice _r of 
_ such that


    _r = ( { T | T ⊆ f_(r) }, ≤_)




In the introductory example, the abstract domain A of A is {bad, 
unknown, good or bad, good} and 
the 
corresponding truth lattice is _A, illustrated in <ref>.
Thus, the attribute context of A is {f_A, _A}. 
The schema context is then _ = {{f_A, _A}, {f_B, _B}, {f_C, 
_C}}.
The abstract lattice associated to r is _r, given in <ref>.
In _r, ⟨ gb, d, c⟩ for instance, results from the comparison of t_3, 
t_4 in r (see <ref>): f_(t_3, t_4) = ⟨ f_A(3.2, 3.5), 
 f_B(M, F), f_C(72, 76)⟩ = ⟨ gb, d, c ⟩.
The closure of ⟨ gb, d, i ⟩ in _r is ⟨ gb, d, i ⟩^+ = 
⟨ gb, d, u ⟩.
Note that ⟨ gb, d, u ⟩ is obtained by taking the meet of ⟨ gb, d, c 
⟩ = f_(t_3, t_4) and ⟨ g, t, u ⟩ = f_(t_1, t_2) in 
_.


As f_ subsumes equality, the top element of ⟨ 1_A_1, …, 1_A_n⟩ of _ also belongs to _r.
Furthermore, _r is -sublattice of _ so that _r ∈(_).
Therefore, it can be represented by a set of lattice implications, the so-called 
abstract functional dependencies in our framework.


Let  be a relation scheme, _ a schema context and  its abstract 
domain.
An abstract functional dependency over _ is an expression of the form 
_ x  y where x, y ∈.




Let r be a relation over _ and x, y ∈.
We say that r satisfies x  y with respect to _, denoted by r 
__ x  y, if for all t_1, t_2 ∈ r, x ≤ f_(t_1, t_2) 
entails y ≤ f_(t_1, t_2).


We can draw a direct connection between the satisfaction of an abstract FD for a relation 
and the validity of a lattice implication.

 
Let r be relation over _ and x  y an abstract functional dependency.
Then r __ x  y if and only if _r  x  y.



The if part is clear as f_(r) ⊆_r.
Let us assume that r __ x  y and let z ∈_r such that x 
≤ z.
If z ∈ f_(r), then y ≤ z as r __ x  y.
Assume z ∈_r ∖ f_(r).
By definition of _r, there exists a subset F_z ⊆ f_(r) such that 
z =  F_z.
Let m ∈ F_z.
As z ≤ m, we have that x ≤ m and since r __ x  y, it 
must be that y ≤ m.
As this holds for any m ∈ F_z, we have y ≤ F_z = z, thus concluding the 
proof.


When clear from the context, we shall drop the element _ of notations regarding 
functional dependencies. Namely, we will denote by x  y an abstract functional 
dependency over _ and r  x  y when r models x  y with 
respect to _.
Furthermore, we can use x, y ∈_ as a shortcut for x, y ∈.
Also, we will make a slight abuse of the [ ] notation: if x ∈_ we denote 
by x[A] the projection of the vector x on A.


In our introductory example, ⟨ u, d, i ⟩⟨ b, d, u ⟩ is a valid abstract 
FD, as the closure of ⟨ u, d, i ⟩ in _r is ⟨ u, d, u 
⟩ 
and ⟨ b, d, u ⟩≤⟨ u, d, u ⟩ in _. However,
⟨ g, t, i ⟩⟨ gb, t, c ⟩ does not hold 
since ⟨ g, t, i ⟩^+ = ⟨ g, t, u ⟩ in _r and ⟨ 
gb, t, c ⟩≰⟨ g, t, u ⟩ in _.	









§ REALITIES AND STRONG REALITIES



Next, we define (attribute) interpretations as particular mappings from a truth lattice 
to {0, 1}.
Their aim is to introduce a semantic for equality by deciding for each two elements in 
the attribute's domain if they are equal or not.
Then, we generalize attribute interpretations to schema interpretations.

As we are particularly interested in functional dependencies, we seek to find 
schema interpretations which preserve their semantic. 
We give a characterization of such interpretations we call realities.
We also introduce a restricted type of realities, strong realities, for they 
behave in accordance with OR/AND boolean rules.
We give a lattice-based characterization for their existence.

 
Let  be a relation schema, A ∈ and _A = {f_A, _A } an attribute 
context. 
An attribute context interpretation of A is a map h_A _A 
→{0, 1} satisfying the following properties:

	
  * x ≤ y in _A implies h_A(x) ≤ h_A(y), h_A is an 
	increasing map,
	
  * h_A(1_A) ≠ h_A(0_A).



<ref> implies that any interpretation is surjective as h_A(1_A) = 1 
and h_A(0_A) = 0.
Practically, it guarantees that two values in (A) can always be interpreted as 
equal or different.
Moreover, the interpretation has to be increasing. 
Intuitively, if a truth value x_A of _A is interpreted as 1 (equality) by 
h_A, any value y_A ≥_A x_A must be set to 1 since it is closer to 
“true” equality than x_A.

 
Let = {A_1, …, A_n} be a relation schema,  _ a schema context and 
h_A_i an attribute context interpretation for A_i, 1 ≤ i ≤ n. 
A schema context interpretation for , denoted by g_h_A_1, …, h_A_n 
(or simply g whenever (h_A_i)_i ≤ n are clear from the context) is a map g 
_→{0,1}^n defined by g(⟨ x_1, …, x_n ⟩) = ⟨ 
h_A_1(x_1), …, h_A_n(x_n) ⟩.

In the sequel, g_| A_i will denote the restriction of g to an attribute A_i 
∈, that is g_| A_i(x) = (g(x))[A_i] = h_A_i(x[A_i]). 


Consequently, given an interpretation g and ∈(_), the family g() 
= {g(x) | x ∈} is the interpretation of  by g.
Note that the map g is an embedding of the lattice _ into {0, 1}^n, or 
equivalently, into 2^.
Then each image of g(·) is a characteristic vector of a set of attributes in . 
In the sequel, we will use g(·) interchangeably to denote a set or its 
characteristic vector. 


Consider t_1, t_3 in our running example.
Here g_0 is the combination of h_A^0, h_B^0 and h_C^0 represented in each of 
the truth lattices of <ref>. 
Hence with t_1, t_3 we obtain:


    g_0(f_(t_1, t_3))     = ⟨ h_A^0(f_A(t_1[A], t_3[A])), 
    	h_B^0(f_B(t_1[B], t_3[B])), 
        h_C^0(f_C(t_1[C], t_3[C])) ⟩
        = ⟨ h_A^0(gb), h_B^0(d), h_C^0(c) ⟩
        = ⟨ 1, 0, 1 ⟩ = AC



The following statement means that a schema interpretation g is uniquely defined by its 
components.

 
The following hold for any schema interpretation g: 


  * g increasing if and only if h_A_i is increasing for any 1 ≤ i ≤ n,

  * g a -homomorphism (resp. -homomorphism, homomorphism) if and only if 
h_A_i is a -homomorphism (resp. -homomorphism, homomorphism) for any 1 
≤ i ≤ n.




We prove the items for increasing and -homomorphism.
Other homomorphisms and decreasing properties are obtained in a dual way.


  * First assume that for any 1 ≤ i ≤ n, h_A_i is increasing.
Let x = ⟨ x_1, …, x_n ⟩, y = ⟨ y_1, …, y_n 
⟩∈_R, we have


    [                             x ≤ y               x_i ≤ y_i   ∀ i ≤ n                     (def of 
    		_);                                   h_A_i(x_i) ≤ h_A_i(y_i)   ∀ i ≤ n             (h_A_i 
    		increasing);                                                         g(x) ≤ g(y)                                  ;                                   ]


For the only if part, assume g is increasing and consider x_i ≤ y_i in 
_A_i. 
Build x and y in _ as follows, x = ⟨ 1_1, …, x_i, …, 
1_n ⟩ and y = ⟨ 1_1, …, y_i, …, 1_n ⟩.
Since g is increasing, we have g(x) ≤ g(y) and for any j ≠ i, 
h_A_j(x_j) = h_A_j(y_j) = h_A_j(1_j) = 1.
We must also have h_A_i(x_i) ≤ h_A_i(y_i).
Because for any pair x_i ≤ y_i in _A_i and for any i ≤ n we can build 
such x, y showing h_A_i(x_i) ≤ h_A_i(y_i), we have that h_A_i is 
increasing for any i ≤ n.


  * Let us assume that for any i ≤ n, h_A_i is a -homomorphism.
For x, y ∈_, one has:


    g(x  y) =    ⟨ h_A_1(x_1  y_1), …, h_A_n(x_n  y_n) 
    	⟩  (def of g)
    
    	=    ⟨ h_A_1(x_1)  h_A_1(y_1), …, h_A_n(x_n)  
    	h_A_n(y_n) ⟩(-homomorphism)
    
    	=    ⟨ h_A_1(x_1), …, h_A_n(x_n) ⟩⟨ 
    	h_A_1(y_1), …, 
    	h_A_n(y_n) ⟩  (in {0, 1}^n)
    
    	=     g(x)  g(y)


As for the only if part, we use contrapositive. 
Assume w.l.o.g. that h_A_1 is not -homomorphic and let x_1, y_1 ∈_A_1 
such that h_A_1(x_1  y_1) ≠ h_A_1(x_1)  h_A_1(y_1). 
Let x = ⟨ x_1, …, x_n ⟩ and y = ⟨ y_1, …, y_n 
⟩. 
Then g(x)  g(y) ≠ g(x  y) by definition of g, as for A_1 we have 
h_A_1(x_1  y_1) ≠ h_A_1(x_1)  h_A_1(y_1).



Now, in view of functional dependencies, the following question arises: which property a 
schema interpretation should have to guarantee that the interpretation of any abstract 
lattice corresponding to a set of abstract FDs is closed by set intersection?
This question is central since functional dependencies must satisfy Armstrong axioms, and 
their model must form a closure system <cit.>.
First, we answer the case where  has few attributes.

 
If n ≤ 2, then for any schema interpretation g and any ∈(_), g() is a closure system over .



If n = 2, then for any ∈(_), g() is a non-empty subset of 
{0, 1}^2 containing ⟨ 1, 1 ⟩ by definition of (_).
The only subset of {0, 1}^2 possessing ⟨ 1, 1 ⟩ which is not closed 
with respect to  is {⟨ 0, 1 ⟩, ⟨ 1, 0 ⟩, ⟨1, 1 
⟩}.
However, if g() contains ⟨ 0, 1 ⟩ and ⟨ 1, 0 ⟩, there 
exists x, y ∈ such that g(x) = ⟨ 0, 1 ⟩ and g(y) = ⟨ 1, 0 
⟩.
As  is a -sublattice of _, and g is increasing, it must be that x 
 y ∈, g(x  y) ≤ g(x) and g(x  y) ≤ g(y) so that necessarily 
g(x  y) = ⟨ 0, 0 ⟩.
Therefore, g() is indeed a closure system, concluding the proof.


In the more general case where the number of attributes is unbounded, this 
property may not hold as shown by the following example.

 
Let = {A, B, C} and r the relation given in the table of
<ref> (a). 
The comparability functions for each attribute are given as follows:


    f_A(x, y) = 
    	1_A    if  x = y, 
    
    	a    if  (x, y) ∈{(1, 2), (2, 1)}, 
    
    	b    if  (x, y) ∈{(1, 3), (3, 1)}, 
    
    	0_A    otherwise.



    f_C(x, y) = 
    	0_C    if  x ≠ y  and  x  or  y  is null, 
    
    	1_C    otherwise.


As for f_B, it is the usual equality function. 
The truth lattices are illustrated in <ref> (b). 
For attribute interpretations we have h_A(x_A) = 1 if x_A ≠ 0 and 0 
otherwise. 
As for h_B and h_C they are bijections with {0, 1}. 
Finally, g is the combination of h_A, h_B, h_C.



Observe that g(_r) has a lattice structure, but it is not a closure system.
Indeed, g(⟨ a, 1, 0 ⟩⟨ b, 0, 1 ⟩) = g(⟨ 0, 0, 0 
⟩) = ∅ and g(⟨ a, 1, 0 ⟩) ∩ g(⟨ b, 0, 1 ⟩) = 
{A, B}∩{A, C} = {A}∉ g(_r) (see <ref>).





Inspired from this example, the next theorem answers the question we asked above.
Let ∈(_).
The idea is that for any two incomparable elements x, y of , there 
must be another element z in  whose interpretation coincides with the 
intersection of g(x) and g(y).
Since g is increasing, we have at least that g(x  y) ⊆ g(x)  g(y).
Thus, by forcing g(x  y) = g(x)  g(y), we can guarantee that the intersection of 
g(x) and g(y) belongs to g() too, as  is a -sublattice of 
_.

 
Let n ≥ 3, and g a schema interpretation. Then g is a -homomorphism if 
and only if for any ∈(_), g() is a closure system.



We begin with the only if part. 
Let g be a -homomorphism and ∈(_).
Consider x, y ∈ such that g(x)  g(y).
Then, since ∈(_) and g is a -homomorphism, it follows that 
x 
 y ∈ and g(x  y) = g(x)  g(y) ∈ g().
Furthermore, the top element ⟨ 1_1, …, 1_n ⟩ belongs to  by 
assumption and g(⟨ 1_1, …, 1_n ⟩) = ∈ g() by definition 
of 
g.
Hence g() is a closure system over .

For the if part, we use contrapositive.
Suppose g is not a -homomorphism.
We construct ∈(_) such that g() is not a closure system.

Recall by <ref> that if g is not a -homomorphism, 
then 
it must be that at least one of the h_A, A ∈ is not a -homomorphism 
either. 
W.l.o.g assume that A = A_1.
Since h_A_1 is increasing but not -homomorphic, there must be x_1, y_1 ∈_A_1 
such h_A_1(x_1) = h_A_1(y_1) = 1 and h_A_1(x_1  y_1) = 0.
Recall that we assumed n ≥ 3.
Let  be the four element set:


    {⟨ x_1, 1_2, 0_3, 1_4, …, 1_n ⟩,
    		⟨ y_1, 0_2, 1_3, 1_4, …, 1_n ⟩,
    		⟨ x_1  y_1, 0_2, 0_3, 1_4, …, 1_n ⟩, 
    ⟨ 1_1, 1_2, 1_3, 1_4, …, 1_n ⟩}


Note that  is clearly a -sublattice of _ which contains its 
top element.
Since g is increasing and we constrained h_A_i(0_A_i) = 0 and 
h_A_i(1_A_i) = 1, we obtain:


    g() = {⟨ 1, 1, 0, 1, …, 1 ⟩,
    ⟨ 1, 0, 1, 1, …, 1 ⟩,
    ⟨ 0, 0, 0, 1, …, 1 ⟩,
    ⟨ 1, 1, 1, 1, …, 1 ⟩}


which is not a closure system when interpreted as attribute sets, thus concluding the 
proof.


For each attribute, the -homomorphism property defines a minimum element in the 
truth lattice which is interpreted as 1. 
Thus, this element acts as a threshold, it is the minimum truth requirement for two 
values of the attribute's domain to be equal.

Still, -homomorphisms only partially capture the intuitive behaviour that an 
interpretation could have.
Indeed, while the meet of two truth values set to 1 equals 1 by 
-preservation of g, thus mimicking logical AND, the OR operation does not hold as 
the join of two truth values interpreted as 0 could be 1.
Hence, we are lead to consider two types of interpretations.
First, -homomorphisms, which guarantee the semantic for functional dependencies 
thanks to <ref>.
Second, homomorphisms, a strengthening of -homomorphisms which also captures the 
classical OR operations.
These types of interpretations are called realities and strong realities respectively.

 
A schema interpretation g is a reality if it is a -homomorphism.
It is a strong reality if it is a homomorphism.


We denote by R the set of realities of _.
The set of strong realities is R_s.
Now we give some properties of strong realities.
First of all, unlike normal realities, there may be cases where R_s = ∅ as 
shown by the following example.


Let = {A, B, C} and _A, _B, _C be the truth lattices of Figure 
<ref>. 
Due to _A no strong reality is possible: for any attribute interpretation h_A, 
each element a, b, c of _A must be assigned a binary value so that 
at least two elements will have the same value, say a, b.
However the homomorphism property implies that h_A(a  b) = h_A(a)  h_A(b) = 
h_A(a) 
 h_A(b) = h_A(a  b) so that either h_A(0) = 1 or h_A(1) = 0, a 
contradiction 
with the definition of an interpretation.





Let us assume that R_s is non-empty.
We show that strong realities are related to prime/co-prime decompositions pairs 
in lattices <cit.>.
Let  be a lattice and x ∈. 
We say that x is prime if for any y, z ∈, y  z ≤ x implies 
either y ≤ x or z ≤ x.
The term co-prime is defined dually with .
The bottom element of  cannot be co-prime, and the top element 
cannot be prime.
It is known from <cit.> Theorem 6, that  has a prime element p 
if and only if it has a co-prime element c.
Actually, if p is prime, then it has a unique associated co-prime element c = 
min_≤{x ∈| x ≰ p}.
Dually if c is co-prime, it has a unique associated prime element p = 
max_≤{x ∈| x ≱ c}.
This correspondence between primes and co-primes is bijective.
Furthermore a pair (c, p) splits  into two disjoint parts  {x ∈| x 
≥ c } and { x ∈| x ≤ p} such that {x ∈| c ≤ x }∪{ x ∈| x ≤ p} =.
For any A ∈, if _A has a pair c, p of coprime/prime elements, we shall 
denote it (c, p)_A.
Furthermore, the set of co-prime (resp. prime) elements of _A is denoted by 
(_A) (resp. (_A)).
Now, we establish the relationship between strong realities and co-prime/prime 
pairs.

 
Let _ be a schema context and g a reality. 
Then, g is a strong reality if and only if for any A ∈, there are 
co-prime/prime pairs (c, p)_A such that c = min_≤{x_A ∈_A | 
g_| A(x_A) = 1} and p = max_≤{x_A ∈_A | g_| A(x_A) =  
0}.



We begin with the only if part.
Let g ∈R_s and consider g_| A for some A ∈.
We show that g_| A induces a co-prime/prime pair (c, p)_A.
We put c =  g_| A^-1(1) and p =  g_| A^-1(0).
Note that as g(0_A) = 0 and g(1_A) = 1 by definition, g_| A^-1(1) and 
g_| A^-1(0) are non-empty.
Furthermore, since g is increasing and homomorphic, both p and c are 
well-defined and satisfy g_| A(p) = 0 and g_| A(c) = 1.
Let us prove that p is prime. 
Let x_A, y_A ∈_A, such that x_A  y_A ≤ p.
As x_A  y_A ≤ p, it must be that g_| A(x_A  y_A) = 0 and either 
g_| A(x_A) = 0 or g_| A(y_A) = 0 since otherwise we would break the 
-homomorphic property of g.
By construction of p then, it follows that either x_A ≤ p or y_A ≤ p.
A similar reasoning can be applied to c.
We show that min_≤{x_A ∈_A | x_A ≰ p} is a singleton 
element 
and that it equals c.
Let y_A, z_A ∈{x_A ∈_A | x_A ≰ p}.
By construction of p and since g is an homomorphism, it must be that g_| A(y_A) 
= g_|_A(z_A) = 1 so that y_A  z_A ∈{x_A ∈_A | x_A ≰ p}.
Therefore, this set has a unique minimum element.
By definition of c, we also have that c ≤ y_A  z_A and c = 
min_≤{x_A ∈_A | x_A ≰ p} holds.
Similarly we obtain p = max_≤{x_A ∈_A | x ≱ c}.
Thus (c, p)_A is indeed a co-prime/prime pair of _A.
As these arguments can be applied for any A ∈, the only if part of the 
statement follows.

Now we move to the if part.
Let A ∈ and (c, p)_A be a co-prime/prime pair of _A.
Let us put h_A as follows:


    h_A(x_A) = 
    	1     if  x_A ≥ c 
    
    	0     if  x_A ≤ p


We have to check that such a definition covers the whole lattice _A in a 
satisfying way.
First, Let x_A ∈_A such that x_A ≰ p.
As p is prime and (c, p)_A is a co-prime/prime pair, we have that c = 
min_≤{y_A ∈_A | y_A ≰ p} so that x_A ≥ c.
Hence, any x_A ∈_A is uniquely mapped to 0 or 1 and h_A is an 
increasing 
mapping.
As for the homomorphism property, we show the -homomorphic side of h_A.
As h_A is increasing, the case where h_A(x_A) = h_A(y_A) = 1 is already covered.
If however, h_A(x_A) = h_A(y_A) = 0, then we have x_A ≤ p and y_A ≤ p so 
that 
x_A  y_A ≤ p and hence h_A(x_A  y_A) = 0 by definition of h_A.
The -homomorphic side of h_A is proved analogously.
Now if we consider g = ⟨ h_A_1, …, h_A_n⟩ we obtain a strong 
reality in virtue of <ref> and <ref>.


Thus, any strong reality arises from the choice of a co-prime/prime pair in each of the 
truth lattices.
More formally, for any A ∈ and any c ∈(_A), let us define 
h_A^c(x_A) = 1 if x_A ≥ c and 0 if x_A ≤ p where p is the prime element 
associated to c in _A.
Then we have:


    R_s = ∏_A ∈{h_A^c | c ∈(_A) }









§ ABSTRACT FDS AND REALITIES



With (strong) realities, we can now study the relationship between abstract FDs and 
classical FDs.
As we have seen, any relation is associated to an abstract lattice from which can be 
derived abstract FDs.
Furthermore, any (strong) reality gives a semantic for classical FDs when the 
abstract lattice is interpreted.
First we settle the notion of satisfaction of an abstract FD through a reality.

 
	Let _ a schema context, r a relation over _, g a reality and 
	x  y an abstract FD. g(x)  g(y) is satisfied in r, denoted by r 
	__, g g(x)  g(y) (or simply r _g g(x)  g(y)) if 
	for 
	all t_1, t_2 ∈ r, g(x) ⊆ g(f_(t_1, t_2)) implies g(y) 
	⊆ g(f_(t_1, t_2)).


Note that in the interpretation g(x)  g(y) of an abstract FD x 
 y, g(y) may coincide with a set Y instead of an attribute A.
Without loss of generality, a FD of the form X  Y should be read as the equivalent 
set of FDs { X  A | A ∈ Y }.

We first give a proposition similar to <ref>.
It permits to work directly on the lattice _r induced by r without 
loss of generality with respect to FDs.

 
	Let r be a relation over _, g a reality, and x  y an abstract FD.
	We have r _g g(x)  g(y) if and only if for any z ∈_r, g(x) 
	⊆ 
	g(z) implies g(y) ⊆ g(z), denoted _r _g g(x)  g(y).



The if part is clear.
We prove the only if part.
Let z ∈_r. 
If z ∈ f_(r) then g(x) ⊆ g(z) implies g(y) ⊆ g(z) by 
assumption.
Hence consider an element z ∈_r ∖ f_(r) such that g(x) ⊆ 
g(z).
By definition of _r, z =  F_z where F_z = {m ∈ f_(r) | z ≤ m 
}.
As g is increasing, it must be that for all m in F_z, g(x) ⊆ g(m).
Since r _g g(x)  g(y), we also have that g(y) ⊆ g(m) for any 
m 
∈ F_z, and in particular g(y) ⊆⋂_m ∈ F_z g(m).
Moreover, g is a -homomorphism so that z =  F_z implies g(z) = g( 
F_z) = 
⋂_m ∈ F_z g(m).
Therefore g(y) ⊆ g(z) and _r _g g(x)  g(y).


Observe that each reality g is associated to a unique x_g ∈_ such that x_g[A] = min_≤{x_A ∈_A | g_| A(x_A) = 
1}.
As g is an increasing -homomorphism, such an x_g is well-defined and for any A 
∈, x_g[A] ≠ 0_A.
In what follows, we will need the next definition.


	Let g be a reality.
	The projection π_g(x) of x ∈_ on g is given as 
	follows: for any A ∈, π_g(x)[A] = x_g[A] if x[A] ≥ x_g[A] and 0_A 
	otherwise.


We prove in <ref> that the interpretation of a valid abstract 
FD of _r is true by g if its projection on g is still a valid 
abstract FD for _r.
Let X ⊆.
We define ψ_X ∈_ with ψ_X[A] = 1_A if A ∈ X and 0_A otherwise.
We need the following Lemma first.

 
	Let x ∈_, and g be a reality. Then g(π_g(x)^+) 
	= g(π_g(x))^+ = g(x)^+.



The equality g(π_g(x))^+ = g(x)^+ directly follows by construction of π_g(x) 
as g(π_g(x)) = g(x).
As π_g(x) ≤π_g(x)^+ in _ and g is increasing, we have that g(x) = 
g(π_g(x)) 
⊆ g(π_g(x)^+).
To show that g(π_g(x)^+) = g(x)^+, we prove that π_g(x)^+ = min_≤{y 
∈_r | g(x) ⊆ g(y)}, which implies that g(π_g(x)^+) = 
min_⊆{F ∈ g(_r) | g(x) ⊆ F} = g(x)^+.
If π_g(x)^+ is the bottom element of _r, g(π_g(x)^+) must be the bottom 
element of g(_r) and g(π_g(x)^+) = g(x)^+ is clear.
If this is not the case, let y ≱π_g(x)^+, y ∈_r.
By closure properties, y ≱π_g(x)^+ is equivalent to y ≱π_g(x).
To satisfy y ≱π_g(x), there must be A ∈ such that π_g(x)[A] 
≰_A y[A].
We have two cases: A ∈ g(x) or A ∉ g(x).
If A ∉ g(x), we have that A ∉ g(π_g(x)) as g(x) = g(π_g(x)).
Consequently, π_g(x)[A] = 0_A by construction of π_g(x) and hence 
π_g(x)[A] ≤_A y[A].
Therefore, it must be that A ∈ g(x).
As π_g(x)[A] ≰_A y[A] by assumption, it follows that A ∉ g(y) and  
therefore that g(x) ⊈ g(y).
Consequently, for any y ≱π_g(x), y ∈_r, we have g(x) ⊈ 
g(y) so that g(π_g(x)^+) = min_⊆{F ∈ g(_r) | g(x) ⊆ 
F} = g(x)^+, concluding the proof.


 
Let g be a reality and x  y an abstract FD.
Then _r _g g(x)  g(y) if and only if _r π_g(x) 
π_g(y).



Let g be a reality and x  y an abstract FD.
We prove the only if part.
Let us assume that _r _g g(x)  g(y).
As g(x) = g(π_g(x)) and g(y) = g(π_g(y)), we also have that _r _g 
g(π_g(x))  g(π_g(y)).
We show that _r π_g(x) π_g(y).
Since _r _g g(π_g(x))  g(π_g(y)), we have that g(π_g(y)) 
⊆ 
g(π_g(x))^+ = g(π_g(x)^+) by <ref>.
We prove that π_g(y) ≤π_g(x)^+.
Let A ∈.
If A ∉ g(π_g(y)), then we have π_g(y)[A] = 0_A by construction of 
π_g 
and hence π_g(y)[A] ≤_A π_g(x)^+[A].
If A ∈ g(π_g(y)) ⊆ g(π_g(x)^+), then π_g(y)[A] ≤_A 
π_g(x)^+[A] holds again by construction of π_g.
Therefore,  π_g(y) ≤π_g(x)^+ and _r π_g(x) π_g(y) follows.

We move to the if part.
Let us assume that _r π_g(x) π_g(y).
We have that π_g(y) ≤π_g(x)^+.
Then, g(π_g(y)) ⊆ g(π_g(x)^+) as g is increasing, and g(π_g(x)^+) 
= 
g(π_g(x))^+ = g(x)^+ by <ref>.
As g(π_g(y)) = g(y), we have that g(y) ⊆ g(x)^+ and _r _g 
g(x) 
 g(y) follows.


Moreover, if an abstract FD holds, then it reflects a potential dependency on r and 
hence there should be a reality which turns it into a valid FD.
This is the aim of the next proposition.

 
	Let x  y be an abstract FD. We have the following:
	
		
  * if _r  x  y, then there exists a reality g such that 
		_r
		_g g(x)  g(y),
		
  * if _r x  y, then there exists a reality g such that 
		_r _g g(x)  g(y).
	



Let x  y be an abstract FD. 
We prove the items in order.

	
  * Assume _r  x  y and let g be a reality such that 
	π_g(x) = 
	x.
	Note that such a reality always exists as it only requires to put x_g[A] = x[A] 
	for 
	any A ∈ such that x[A] ≠ 0_A.
	Then by <ref>, g(x^+) = g(x)^+.
	Since _r  x  y, we have that y ≤ x^+ and therefore g(y) 
	⊆ 
	g(x^+) = g(x)^+ so that _r _g g(x)  g(y).
	
	
  * Assume _r x  y and let g be a reality such that 
	π_g(y) = y.
	Again by <ref>, we have that g(y^+) = g(y)^+ which implies 
	that for any z ∈_r, g(y) ⊆ g(z) if and only if y ≤ z.
	However, _r x  y so that y ≰ x^+.
	Therefore, g(y) ⊈ g(x)^+ as g(y) ⊈ g(x^+) and g(x)^+ 
	⊆ 
	g(x^+)^+ = g(x^+).
	Hence _r _g g(x)  g(y). 


To conclude this section, we show an example illustrating the previous theorems.


We consider our introductory example.
Let g_0 be the reality of <ref> (a).
Namely, x_g_0 = ⟨ gb, t ,u ⟩.
Let ⟨ g, d, u ⟩⟨ gb, t, i ⟩ be an abstract FD.
We have that π_g_0(⟨ g, d, u ⟩) π_g_0(⟨ 
gb, 
t, i ⟩) 
 = ⟨ gb, d, u ⟩⟨ gb, t, i ⟩ which does not 
hold 
in 
_r.
By <ref>, we have that g_0(⟨ g, d, i ⟩) 
g_0(⟨ b, t, i ⟩) = AC  AB which is false in g_0(_r) 
(<ref>).

Now we consider the abstract FD ⟨ b, t, c ⟩⟨ u, t, c 
⟩ 
which holds in 
_r.
By <ref>, there exists g such that g(⟨ b, t, 
c⟩)  
g(⟨ u, t, c ⟩) holds in g(_r).
This is the case for instance of the reality g_1 in <ref> (b) 
where x_g_1 = ⟨ u, t, c ⟩.
We have g_1(⟨ b, t, c⟩)  g_1(⟨ u, t, c ⟩) = BC  
ABC, 
holding in g(_r).










§ POSSIBLE AND CERTAIN FDS



In this section, we are interested in functional dependencies from another 
point of view.
We are given a relation r over a schema context _, and a functional dependency 
X  A.
Recall that in our terms, a functional dependency X  A means a pair (X, A) where 
X ⊆ and A ∈. 
Since any reality g maps _r to a closure system, one may be inquiring about 
functional dependencies holding in g(_r). 
Beforehand, we formally define the meaning of a FD holding through a reality. 
This will mainly be a reformulation of <ref> with attribute sets 
instead of abstract tuples.

 
	Let r be a relation over _, g a reality, X ⊆ and A ∈.
	X  A is satisfied in r with respect to _ and g, denoted r 
	_g X  A, if for all x ∈ f_(r), 
	X ⊆ g(x) implies A ∈ g(x).
















<ref> can also be reformulated in this way, thus 
introducing the notation _r _g X  A if for any x ∈_r, X 
⊆ g(x) implies A ∈ g(x).

 
	Let r be a relation over _, g a reality, X ⊆ and A ∈.
	We have r _g X  A if and only if _r _g X  A.



	Let x, a ∈_ such that g(x) = X and g(a) = A.
	Note that x, a must exist as g(_) = 2^.
	The result follows from <ref> applied to x, a.


There are a lot of different realities for a given _. 
Therefore, a same FD X  A may or may not hold depending on the reality we choose. 
However, there are also some FDs that will hold for any reality. 
Consider for instance the trivial case X  A, A ∈ X.
Thus, inspired by certain query answering, we define certain functional dependencies as 
those who are true for any reality.
Similarly, a functional dependency is possible if it holds for at least one reality.
They are defined along with decisions problems. 





	Let r be a relation over _ and X  A a functional dependency.
	We say that X  A is certain (resp. strongly certain) if for any 
	reality g ∈R (resp. strong reality g ∈R_s), r _g X  
	A 
	holds.


Certain Functional Dependency (CFD)
A schema context _, a relation r over _ and a functional dependency X 
	 A.
Is X  A certain with respect to r, _?


Strongly Certain Functional Dependency (SCFD)
A schema context _, a relation r over _ and a functional 
dependency X  A.
Is X  A strongly certain with respect to r, _?




	Let r be a relation over _ and X  A a functional dependency.
	We say that X  A is possible (resp. strongly possible) if there 
	exists a reality g ∈R (resp.  a strong reality g ∈R_s) such that 
	r 
	_g X  A holds.


Possible Functional Dependency (PFD)
A schema context _, a relation r over _ and a functional dependency X 
	 A.
Is X  A possible with respect to r, _?

Strongly Possible Functional Dependency (SPFD)
A schema context _, a relation r over _ and a functional dependency X 
	 A.
Is X  A strongly possible with respect to r, _?



Before discussing the complexity of those problems we give an illustration of possible 
and certain functional dependencies.
This example also shows the relationship with classical FDs.
Indeed, if X  A is certain, then in particular r  X  A in the 
classical sense (the reality here is the usual equality).
On the other hand, if r  X  A, then X  A is possible.
However, the next example shows that the converses for these statements are not true.


	Let = {A, B, C} and consider the relation r given in
	<ref> (a).
	The comparability lattices for A, B, C are given in <ref> (b).
	As for the comparability function, we put f_A(i, i) = 1_A for i ∈{1, 2, 3}, 
	f_A(2, 3) = 0_A and u otherwise.
	The functions f_B, f_C are defined similarly on the same domain.
	Moreover, a reality g is illustrated in the Figure: g_| A(x_A) = 1 if x_A = 
	1 
	and 0 otherwise, g_| B(x_B) = 0 if x_B = 0 and 1 otherwise, and g_| 
	C 
	is similar to g_| A.
	
	
	
	On the one hand, we have r  B  C whereas r _g B  C 
	(take 
	t_2, t_3).
	On the other hand, r _g A  B but r A  B (see t_1, 
	t_2). 
	
	
	
	
	
	
	
	



No we show that the number of realities can be exponential. 
We assume that computing the results of comparability functions is constant time.
Their size in memory is also assumed to be constant.
The idea is to allow one degree of freedom in the choice of h_A for any A ∈.
It applies to strong realities too.

 
	Let  be a relation schema, _ a schema context. 
	Then the number of (strong) realities can be exponential in the size of  and 
	_.



	Let  be a relation scheme and _ = {(f_A, _A) | A ∈} 
	where _A is the three-element lattice 0 ≤ u ≤ 1 for each A ∈.
	Note that the size of _ is bounded by the size of .
	Now for each _A, there are only two possible interpretations h_A^1 and h_A^2:
	
		
  * h_A^1(0) = h_A^1(u) = 0 and h_A^1(1) = 1,
		
  * h_A^2(0) = 0 and h_A^2(u) = h_A^2(1) = 1.
	
	Clearly both h_A^1 and h_A^2 are homomorphisms.
	Using Proposition <ref> and Theorem <ref> we can 
	describe R as follows:
	
    R = {⟨ h_A_1^i_1, h_A_2^i_2, …, h_A_n^i_n⟩| i_k 
    	∈{1, 2 }, 1 ≤ k ≤ n }

	Which is a bijection with all binary words of size n on the {1, 2} alphabet. 
	Hence R = 2^n.

















Thus, given a functional dependency X  A, checking all realities to answer any 
of these problems is impossible in polynomial time.



 §.§ Certain functional dependencies


Now we investigate the problems related to certain functional dependencies.
Note that thanks to <ref> we can use equivalently r 
 X  A and _r  X  A.
To do so we characterize certainty of a FD using the structure of _r.
The main idea is to guarantee that if the interpretation of an element of _r can 
contain X, then we force it to contain A no matter the reality we choose.
For the recall, (_A) (resp. (_A)) denotes the set of co-prime (resp. 
prime) elements of the truth lattice _A, for any A ∈.

 
	Let r be a relation over _ and X  A a functional dependency.
	Then:
	
		
  * X  A is certain if and only if for any x ∈_r, either x[A] = 1_A 
		or there exists B ∈ X such that x[B] = 0_B.
		
  * X  A is strongly certain if and only if for any x ∈_r
		either x[A] ≥_A (_A) or there exists B ∈ X such that x[B] 
		≱_B c for any c ∈(_B).
	



	
	We prove the items in order.
	
	
		
  * We begin with the if part.
		There are two cases, either X = ∅, or X ≠∅.
		In the first case, our assumption implies that x[A] = 1_A for any x ∈_r.
		Hence, by construction of a reality g, A ∈ g(x) for any x ∈_r, in 
		particular the bottom element of _r, and r _g X  A holds.
		Assume X ≠∅.
		Let x ∈_r, and g be any reality.
		If x[A] = 1_A, then A ∈ g(x) since h_A(1_A) must be 1 by definition of 
		an interpretation.
		Hence if X ⊆ g(x), we still have A ∈ g(x) and x satisfies X  
		A 
		under g.
		Suppose now x[A] ≠ 1_A.
		By assumption, there exists B ∈ X such that x[B] = 0_B. 
		Hence h_B(x[B]) = 0, and B ∉ g(x) so that X ⊈ g(x).
		Therefore, in any case, x satisfies X  A through g and r _g X 
		 A for any g ∈R.
		
		We prove the only if part using contrapositive.
		Assume there exists x ∈_r such that for all B ∈ X, x[B] ≠ 0_B 
		and 
		x[A] ≠ 1_A. 
		We construct a reality g such that r _g X  A:
		
			
  * for A put h_A(y_A) = 1 if y_A ≥ z_A in _A with z_A some 
			cover of x[A].
			Note that such a cover must exist since x[A] ≠ 1_A.
			Put h_A(y_A) = 0 otherwise, so in particular h_A(x[A]) = 0.
			
  * For any B in X, let h_B(y_B) = 1 if y_B ≥ x[B] in _B 
			and 
			h_B(y_B) = 0 otherwise.
			Since x[B] ≠ 0_B, h_B(0_B) = 0 is satisfied.
			
  * For any other attribute C ∈, let h_C(y_C) = 1 if y_C = 1_C 
			and 0 
			otherwise.
		
		It is clear that any h thus defined is a -homomorphism.
		Using <ref> and <ref>, the 
		mapping g obtained by combining all attributes interpretations is a reality.
		If X = ∅, by construction of g and x, A ∉ g(x) and hence r 
		_g X  A.
		Assume X ≠∅.
		For any B ∈ X, one has B ∈ g(x) as g_| B(x) = h_B(x[B]) = 1 by 
		definition 
		of h_B.
		We also have A ∉ g(x) since g_| A(x) = h_A(x[A]) = 0 by 
		construction of 
		h_A.
		Therefore r _g X  A, and X  A is not certain, concluding 
		the 
		proof of this item. 
		
		
  * We begin with the if part.
		Let g be a strong reality and let x ∈_r.
		If X ⊈ g(x), then g(x) vacuously satisfies X  A.
		Let us assume that X ⊆ g(x) so that for any B ∈ X, there is c ∈(_B) such that x[B] ≥ c.
		As g is a strong reality, there must be some c' ∈(_A) such that 
		g_| 
			A = h_A^c' by <ref>.
		By assumption, we have that x[A] ≥ c' as x[A] ≥(_A).
		Therefore, A ∈ g(x) and we conclude that r _g X  A for any 
		reality g 
		∈R_s.
		Note that in the case where X = ∅, X ⊆ g(x) holds for any x 
		∈_r so that for all such x, we have x[A] ≥(_A). 
		
		We move to the only if part.
		Let us assume that X  A is strongly certain, and assume that there exists 
		x ∈_r such that for any B ∈ X, x[B] ≥ c for some c ∈(_B).
		If X = ∅, this is the case for any x ∈_r.
		We put k = (_A).
		We consider the sequence g_1, …, g_k of realities as follows, for 1 ≤ i 
		≤ 
		k:
		
			
  * g_i_| B = h_B^c for some c ∈(_B) such that x[B] 
			≥ 
			c, 
			B ∈ X,
			
  * g_i_| A = h_A^c for some c ∈(_A) such that 
			g_i_| 
					A≠ g_j_| A for any 1 ≤ j < i.
			
  * g_i_| C = h_C^c for some c ∈(_C), C ∈∖ X 
			∪{A}
		
		For any 1 ≤ i ≤ k, we have that X ⊆ g_k(x).
		As X  A is strongly certain, we must also have A ∈ g_k(x) by 
		<ref>.
		By construction of the sequence g_1, …, g_k, for any c ∈(_A) 
		there 
		is a (unique) 1 ≤ i ≤ k such that g_i_| A = h_A^c.
		However, as A ∈ g_i(x) for any g_i, we have that x[A] ≥ c for any c 
		∈(_A) and hence x[A] ≥(_A).
		Since this reasoning can apply to any x ∈_r, the second item follows. 
		


Therefore, deciding whether a FD is certain amounts to check the elements of _r.
Indeed, recall that ψ_A is the characteristic vector of A within _, that 
is ψ_A[A] = 1_A and ψ_A[B] = 0_B for any B ∈, B ≠ A.
Then, thanks to closure properties, we have that any element x_A ∈_A such that 
x_A[A] = 1_A is above ψ_A^+. 
The remaining elements of _r are dominated by a subset of f_(r) so that a run 
over f_(r) to check <ref> can be done in polynomial time in the 
size of r.
Note that as for any B ∈, _B is given in the input, computing the  
operation in _ can be done in polynomial time in the size of _.
Hence:

 
	CFD can be solved in polynomial time.



	Let (r, _, X  A) be an instance of CFD.
	From <ref>, we have to check that for any element x in _r, 
	either x[A] = 1_A or there exists B ∈ X such that x[B] = 0_B.
	Let us set up x ∈_ as follows:
	
		
  * x[A] = 1_A,
		
  * x[B] = 0_B for any B ≠ A (in particular for any B ∈ X)
	
	We consider x^+.
	Note that any element y ∈_r which satisfies y[A] = 1_A does not require 
	further verification and furthermore, lies above x^+ by construction of x.
	Hence it remains to check that for any y ≱ x^+ in _r, there exists some B 
	∈ X such that x[B] = 0_B.
	We show that we only need to test this property for the set max_≤{y ≱ 
	x^+ 
	| 
	y ∈_r}.
	First assume, that there exists m ∈max_≤{y ≱ x^+ | y ∈_r} 
	such 
	that for any B ∈ X, m[B] ≠ 0_B.
	Then the condition of <ref> fails with m and hence X  A is 
	not certain.
	Now suppose that for any m ∈max_≤{y ≱ x^+ | y ∈_r}, 
	there 
	exists 
	some B ∈ X such that m[B] = 0_B.
	By definition, for any y ≱ x^+ there must exists some m ∈max_≤{y 
	≱ x^+ 
	| y ∈_r} such that y ≤ m.
	As by assumption we supposed that there exists some B ∈ X such that m[B] = 0_B 
	and 
	as y ≤ m, y[B] = 0_B follows.
	Thus, for any y ≱ x^+ in _r, there exists some B ∈ X such that x[B] = 
	0_B if and only if for any m ∈max_≤{y ≱ x^+ | y ∈_r}, 
	there 
	exists B ∈ X such that m[B] = 0_B.
	
	It remains to show that the set max_≤{y ≱ x^+ | y ∈_r} can 
	be 
	checked efficiently.
	First, observe that max_≤{y ≱ x^+ | y ∈_r}⊆M(_r).
	Then, by construction of _r, any element y in _r ∖ f_(r) is 
	obtained by taking the meet of a subset of f_(r).
	Thus, y ∉M(), and M(_r) ⊆ f_(r).
	As the size of f_(r) is bounded by r^2 and each verification takes 
	O() operations, we conclude that checking all the 
	tuples in f_(r) can clearly be done in polynomial time in the size of (r, 
	_, 
	X  A), thus concluding the proof.



We can prove a similar theorem for strongly certain functional dependencies.
In this case however, we have to add a pre-processing step to compute co-prime
elements of the attribute lattice _A, for any A ∈.

 
	SCFD can be solved in polynomial time.



	Let (r, _, X  A) be an instance of SCFD.
	We first need to compute, for any B ∈, the set (_B).
	As _B is given in the input _, this can be done in polynomial time in 
	the 
	size of _ by greedily checking for each element x_B in _B whether 
	max_≤{y_B ∈_B | y_B ≱ x_B } is a singleton set.
	Therefore, we can already check that strong realities exist by 
	<ref> in polynomial time.
	If there are no strong realities, the answer to SCFD is positive.
	
	If there are strong realities, we apply use the arguments of <ref> 
	with 
	x ∈_ 
	as follows:
	
		
  * x[A] = (_A),
		
  * for any other B ∈, B ≠ A, x[B] = 0_B.
	
	Note that instead of checking whether for any m ∈max_≤{y ≱ x^+ | 
	y 
	∈_r}, there exists some B ∈ X such that m[B] = 0_B, we check that there 
	exists B ∈ X such that m[B] ≱ c for any c ∈(_B).
	This amounts equivalently to assert that m[B] < (_B) by definition of 
	co-prime/prime pairs decomposition.
	Again, as _B is part of the input, computing (_B) and (_B) 
	can be done in polynomial time in the size of (r, _, X  A).





 §.§ Possible functional dependencies


Now we establish the complexity of the problems PFD and SPFD.
Again, we need an intermediary structural lemma.
The main argument is dual to <ref>.
That is, we have to guarantee that whenever we are forced to put X in the 
interpretation of some element x of _r, we can put A too.

 
	Let r be a relation over _ and X  A a functional dependency.
	Then:
	
		
  * X  A is not possible if and only if there exists x ∈_r, 
		such that x[A] = 0_A and x[B] = 1_B for any B ∈ X.
		
  * X  A is strongly possible if and only if there exists c_X ∈_ such that c_X[B] = c, for some c in (_B), for every B 
		∈ X, and 
		such that c_X^+[A] ≥ c for some c ∈(_A).
	



	We prove the statements in order. Let r be a relation over _ and X  A 
	a functional dependency.
	For the first item we need to introduce particular realities.
	Recall that A(_A) is the set of atoms of _A.
	Let a ∈A(_A).
	We define a reality g^a as follows:
	
	
    g_| B^a(x) = {[              1 if  x[B] = 1_B;              0      otherwise ].
    	 for any B ≠ A and 
    	g_| A^a(x) = {[            1 if  x[A] ≥ a;            0    otherwise ].

	
	
		
  * We begin with the if part.
		Hence, assume there exists x ∈_r such that x[A] = 0_A and for every B 
		∈ X, 
		x[B] = 1_B.
		In the case where X = ∅, then x just satisfies x[A] = 0_A.
		Let g be a reality.
		By definition of interpretations, we must have A ∉ g(x) and  X 
		⊆ g(x).
		Hence, x does not satisfy X  A, so that r _g X  A.
		Since this holds for any reality g, we conclude that X  A is not possible.
		
		We show the only if part.
		Assume that X  A is not possible in _r, that is for any reality g, 
		_r 
		_g X  A.
		In particular, this is true for any reality g^a, a ∈A(_A).
		Then, for any a ∈A(_A), there exists x_a ∈_r such that x[B] 
		= 1_B 
		for any B ∈ X and x[A] ≱_A a, by definition of g^a and 
		<ref>.
		As _r is a meet-sublattice of _, x = _a ∈A(_A) 
		x_a also 
		belongs to _r.
		However, it must be that x[B] = 1_B for any B ∈ X.
		Furthermore, we have that x[A] = 0_A as x_a ≱_A a for any a ∈A(_A),
		which concludes the proof of the item.
		
		
  * We begin with the only if part.
		Let g be a strong reality such that r _g X  A and consider the 
		following 
		c_X:
		
			
  * c_X[B] = 0_B for B ∉ X,
			
  * c_X[B] = c for c ∈(_B) such that g_| B = h_B^c 
			for any B ∈ X.
			Such a c exists by <ref> as g is a strong 
			reality.
		
		Again, if X = ∅, then c_X[B] = 0_B for every B ∈.
		We consider c_X^+ ∈_r.
		As c_X ≤ c_X^+, and by construction of c_X, we must have X ⊆ 
		g(c_X^+).
		However, r _g X  A which implies that A ∈ g(c_X^+) by 
		<ref>.
		Hence, since g is a strong reality, there must be some c ∈(_A) 
		such that 
		g_| A = h_A^c and c_X^+[A] ≥ c.
		
		We move to the if part.
		Assume such c_X exists.
		We construct a strong reality g such that r _g X  A as follows:
		
			
  * g_| B = h_B^c for some c ∈(_B) if B ∉ X ∪{A},
			
  * g_| B = h_B^c_X[B] if B ∈ X,
			
  * g_| A = h_A^c for some c ∈(_A) such that c ≤ 
			c_X^+[A].
			Note that such c must exist by assumption.
		
		Thus defined, g is a strong reality as c_X[B] ∈(_B) for any B 
		∈ X.
		Now we show that r _g X  A.
		Let x ∈_r.
		Either x ≥ c_X^+ or x ≱ c_X^+.
		In the first case, by construction of g we have X ⊆ g(x), but we also 
		have 
		A 
		∈ g(x) as g_| A = h_A^c with c ≤ c_X^+[A], so that X  A is 
		satisfied 
		for g(x).
		Now suppose x ≱ c_X^+.
		We have that x ≱ c_X.
		However for any B ∉ X, c_X[B] = 0_B so that necessarily c_X[B] ≤ 
		x[B].
		Therefore, there must exists B ∈ X such that x[B] ≱ c_X[B].
		Hence, by construction of g we will obtain B ∉ g(x) and consequently X 
		⊈ g(x) so that X  A is also satisfied by g(x).
		As for any x ∈_r, X ⊆ g(x) implies A ∈ g(x), we conclude 
		that r 
		_g X  A and X  A is strongly possible.
	


Hence, PFD can be solved by checking ψ_X^+. Recall that ψ_X is the 
characteristic vector of X in _, that is ψ_X[A] = 1_A if A ∈ X and 
0_A otherwise.

 
	PFD can be solved in polynomial time.



	Let (r, _, X  A) be an instance of PFD.
	According to <ref>, X  A is not possible if and only if there 
	is an element x in _r such that x[B] = 1_B for any B ∈ X and x[A] = 
	0_A.
	Since f_(r) is a generating set of _r, we can compute the 
	closure ψ_X^+ of ψ_X (note that ψ_X[A] = 0_A) in polynomial time in 
	the 
	size of r and _ as truth lattices are part of _.
	Then, either ψ_X^+[A] = 0_A in which case X  A is not possible, or 
	ψ_X^+[A] ≠ 0_A and X  A is possible.


For strong possibility however, one might have to test an exponential number 
of closure since we have to check for any possible combination of co-prime elements.
In fact, we prove in the following theorem that SPFD is intractable (reduction 
from 3SAT).

 
	SPFD is NP-complete.



A certificate is a strong reality g _→{0,1}^n of polynomial size. 
Moreover, the satisfaction of a functional dependency given the strong reality can be 
checked in polynomial time. 
It follows that PFD belongs to NP.

To show NP-hardness, we reduce 3SAT to PFD.
Let φ = {C_1, …, C_m} be a 3-CNF on n variables V = {x_1,…, 
x_n}.
Without loss of generality, we consider that no clause of φ contains x_i 
and x̅_̅i̅.
We construct a schema context , a relation r_φ and a functional 
dependency X  A such that φ is satisfiable iff there exists a strong 
reality g such that r_φ_, g X → A.

We first build a relation schema R and then a schema context  as follows.
For each variable x_i, 1 ≤ i ≤ n, we create an attribute A_i. 
Then we create a new attribute A_n+1 which corresponds to the attribute A in 
the functional dependency X  A. 
Thus, we obtain the relation schema = {A_1, …, A_n, A_n+1}. 
The domain of each attribute is N. 
Now, we define the schema context :



  * For each attribute A_i∈ R, 1 ≤ i ≤ n, we put A_i = {⊤, 
a_i, a̅_̅i̅, } and for A_n+1, A_n+1 = {⊤, }.


  * For each attribute A_i∈ R, 1 ≤ i ≤ n, its comparability function is 
defined by:


    f_A_i(x,y) = ⊤    if  x = y 
    
    	a_i           if x - y = 1 
    a̅_̅i̅    if x - y = 2 
        otherwise.


and for A_n + 1:


    f_A_n+1(x,y) = ⊤    if x - y≠ 1 
        if x - y = 1



  * For each attribute A_i∈ R, 1 ≤ i ≤ n, its lattice is defined by 
_A_i = {≤ a_i ≤⊤; ≤a̅_̅i̅≤⊤}, and for 
A_n+1, _A_n + 1 = {≤⊤}.


Then _ = {(f_A_i, ℒ_A_i), 1 ≤ i ≤ n + 1} is the 
resulting schema context.

Now, we construct a relation instance r_φ over .
To any clause C_j ∈φ, 1 ≤ j ≤ m we associate a subrelation r_C_j 
with two tuples t and t' as follows:


	
  * For each attribute A_i, 1 ≤ j ≤ n:
	
		
  * if x_i ∈ C_j, t[A_i] = 3j-2 and t'[A_i] = 3j, 
		
  * if x̅_̅i̅∈ C_j, t[A_i] = 3j-2 and t'[A_i] = 3j-1 ,
		
  * if x_i ∉C_j and x̅_̅i̅∉C_j, t[A_i]= t'[A_i]=3j.
	
	
  * For the attribute A_n+1, we put t[A_n+1]=3j-1 and t'[A_n+1]=3j.


The obtained relation is r_φ=⋃_C_j ∈φ r_C_j. 
We consider the functional dependency X  A where X={A_1,...,A_n} and A = 
A_n+1.
Clearly, the size of the reduction is polynomial in the size of the 3CNF φ. 

Let g be a strong reality.
We have that r_φ_, g X  A iff r_C _, g X  
A, for every subrelation r_C ⊆ r_φ, C ∈φ.
Indeed, if r_φ_, g X  A, then clearly r_C _, g 
X→ A as r_C ⊆ r.
To see the other direction, we show that any pair of tuples lying in different 
subrelations must agree on A_n + 1 with respect to g, so that it always 
satisfies X  A. 
Let t, t' be two tuples of r such that t, t' are in distinct subrelations 
r_C_j, r_C_k where j < k (resp.).
By construction of r, the minimum value of t[A_n + 1] - t'[A_n + 1] is 
reached when t[A_n + 1] = 3j and t'[A_n + 1] = 3k - 1.
As k ≥ j + 1, we obtain 3k - 1 ≥ 3j + 2 and hence t[A_n+1] - 
t'[A_n+1]≥ 2.
Therefore, we have f_A_n+1(t[A_n+1],t'[A_n+1])=⊤ by definition of 
f_A_n + 1 and g_|A_n+1(f_A_n+1(t[A_n+1],t'[A_n+1])) = 1 for any 
(strong) reality g.
Thus, for every reality, whenever two tuples t and t' disagree on the right-hand 
side of X  A, it implies  r_C={t,t'} for some C∈φ, t[A_n+1]-t'[A_n+1] = 1 and f_A_n+1(t[A_n+1],t'[A_n+1])=.



Now, we show that φ is satisfiable if and only if the functional dependency 
X  A is strongly possible.
Suppose φ is satisfiable and let μ:𝒱→{0,1} be a valid 
truth assignment of φ. 
We construct a strong reality g such that r_φ_, g X  A. 
First for every attribute context (f_A_i, _A_i), 1 ≤ j ≤ n, we define 
the following attribute context interpretation h_i:

	
  * h_i() = 0 and h_i(⊤) = 1,
	
  * h_i(a_i)=μ(x_i) and h_i(a̅_̅i̅) = 1 - μ(x_i).

For A_n+1, we define h_n+1()=0 and h_n+1(⊤)=1.
Next, we define the schema context interpretation  g: _→{0,1}^n by 
g(⟨ x_1, …, x_n+1⟩) = ⟨ h_1(x_1), …, 
 h_n+1(x_n+1)⟩. 
For any 1 ≤ j ≤ n, we have that h_i(a_i)≠ h_i(a̅_̅i̅) which implies 
that h_i is an homomorphism.
Therefore, g is a strong reality by <ref> and 
<ref>.

By previous discussion, it is sufficient to show that r_C _, g X  A 
for any clause C of φ to have r_φ_, g X A.
Hence, let t, t' be the two tuples of r_C for some C = (l_1  l_2  l_3) 
∈φ.
At least one literal in C is true by the assignment μ. 
Without loss of generality, suppose μ(l_1)=1 and l_1∈{x_i,x̅_̅i̅} for 
some A_i ∈ R. 
We have two cases:



  * l_1 = x_i: then t[A_i]=3j-2, t'[A_i]=3j and f_A_i(t[A_i], 
t'[A_i])=a̅_̅i̅. 
Thus g_| A_i(a̅_̅i̅)=1-μ(x_i)=0 since μ(x_i)=1.
It follows {t, t'}_, g X  A since A_i ∈ X and 
g_|_A_i(f_A_i(t[A_i], t'[A_i])) = 0.
	

  * l_1=x̅_̅i̅: then t[A_i]=3j-2, t'[A_i]=3j-1 and f_A_i(t[A_i], 
t'[A_i])=a_i. 
Thus g_| A_i(a_i)=μ(x_i) = 0 since μ(x̅_̅i̅) = 1. 
It follows {t, t'}_, g X→ A with the same reasoning. 


Thus the tuples for every subrelation r_C cannot agree on X. 
We conclude that  X  A is always satisfied in the strong reality g and thus 
X  A is possible.



Now we show that φ is satisfiable if X  A is strongly possible.
Suppose that r_φ_, g X → A for some strong reality 
g.  
Then we construct a valid truth assignment μ for φ.
According to the reduction, two tuples t, t' of r_φ disagree on A_n + 
1 = A with respect to g if and only if they belong to the same subrelation r_C.
Thus, in order to satisfy r_φ_, g X → A, we must have 
g_| A_i(f_A_i(t[A_i],t'[A_i]))=0 for some A_i ∈ X.
As g is a strong reality, it guarantees that g_| A_i() = 0 and g_| 
A_i(⊤) = 1.
Furthermore, it is a homomorphism, so that g_| A_i(a_i) = g_| A_i(a̅_̅i̅) 
is not possible by <ref>.
Therefore we must have g_| A_i(a_i) ≠ g_| A_i(a̅_̅i̅).
Assume without loss of generality that g_| A_i(a_i)=1 and g_| 
A_i(a̅_̅i̅)=0.
As g_| A_i(f_A_i(t[A_i],t'[A_i]))=0 by assumption, it follows that 
f_A_i(t[A_i],t'[A_i]) = a̅_̅i̅ by construction of r_φ and hence that 
x_i ∈ C.
Put μ(x_i)=1. 
Then every clause containing x_i is satisfied.
Consider now a clause C' not containing x_i and let r_C' = {t_1,t_2}. 
We have by construction g_| A_i(f_A_i(t_1[A_i],t_2[A_i]))=1. 
Since X→ A is satisfied and g_| A_n+1(f_A_n+1(t_1[A_n+1], 
t_2[A_n+1]))=0 (t_1, t_2 do not agree on A_n + 1 = A), there exists another 
attribute A_k ≠ A_i, 1 ≤ k ≤ n such that g_| 
A_k(f_A_k(t_1[A_k],t_2[A_k]))  = 0. 
We use for x_k the same construction as for x_i.
The same construction is repeated until all clauses are satisfied. 
Note also that the assignment μ verifies μ(x_i) ≠μ(x̅_̅i̅). 
We conclude that φ is satisfiable.


We conclude this section with a summary of the complexity results we established for 
certain and possible functional dependencies.










§ RELATED WORKS



Incomplete information has been heavily studied in the database and artificial 
intelligence communities, see for example 
<cit.>.

Numerous researches on data dependencies have been conducted over the last years,  
leading to a plethora of propositions from seminal FDs to more elaborated forms of 
dependencies, among which we quote 
<cit.>.

Many papers have studied lattice representations of Functional dependencies, for instance 
<cit.>. 
However, they do not consider incomplete information as we do in this paper.
W. Ng <cit.> defined ordered domains in the relational data model, a 
partial 
order over every attribute domain is permitted. 
The paper studies the consequences on both FDs and relational languages (algebra and 
SQL). 
His work does not consider incomplete information as we do: our partial order is not 
defined on attribute domain, but on the abstract domain of attributes, and is required to 
form a lattice. 
It offers a new point of view on FDs in presence of incomplete information.


In <cit.>, order dependencies are based on a transitive 
relation, and 
approximate dependencies on a symmetric relation, leading to approximate-matching 
dependencies.

In  <cit.>, the authors study matching dependencies using boolean  
similarity functions (reflexive and symmetric) and matching functions (idempotent, 
commutative, and associative).  
The use of matching functions is to chase the relation instance to obtain a clean 
relation. 
The way we deal with incomplete information is completely different though.

In <cit.>, the author studies the semantics of SQL query answering in 
presence 
of incomplete information. 
He defines a multi-valued logic similar to our contribution, without considering data 
dependencies.

For evaluating the truth of a proposition like equality of two entities, it is usual to 
order the truth values in a lattice <cit.>. 
In addition to the well known true/false lattice, several other semantics that 
might be useful have been studied.
This is the case for instance of Kleene or Łukasiewicz 3-valued logic<cit.>, 
and 
Belnap's 4-valued logic where truth values can be ordered by both their degree of truth, 
and their degree of knowledge, or informativeness <cit.>. 
Belnap's logic has been generalized to bi-lattices that are more suitable for 
non-monotonic reasoning <cit.>.
In <cit.>, the authors define many-valued semantics and 
informativeness ordering for query answers in incomplete databases with missing
values represented by marked nulls. 
Recently, Grahne <cit.> used the 4-valued logic to capture 
inconsistencies 
in database and for query answering in the presence of inconsistencies.
In fuzzy logic, the truth values or degree of belief is ordered in a 
chain-lattice where the interpretation is a threshold function, known as α-cut.

Many contributions have been proposed to deal with uncertain FDs, among which we quote  
<cit.>, and 
<cit.> for a survey.

The authors of <cit.> have considered minimal relaxations for query 
conditions  involving  comparison operators (as selection or join queries) to obtain an 
answer.
Their works concern numerical attributes where the relaxation is quantified as value 
differences, but it also works for any “blackbox” function that quantifies the 
relaxation.

Our contribution is an extension of these works within a declarative perspective, using 
lattice theory.








§ CONCLUSION



Defining equality between two tuples is a central problem in databases, notably due to 
data quality problems such as missing values and uncertainty.
In practice, domain experts should be able to easily give a meaningful semantic for 
equality.
In this paper we have introduced a lattice-based formalism which allows to deal with many 
possible interpretations of data values equalities.
Our approach is able to deal with missing values (represented as nulls) and with 
uncertain values, which makes it better suited for practical applications where 
values are known to be imprecise and dirty. 
In order to determine whether an attribute agrees on two tuples, the pair of the two 
tuples is first mapped to a (truth) lattice element representing the truth value.
Then, an interpretation maps this value either to true (1) or false (0). 
In other words, the equality between x and y is then the composition of two 
functions: a comparability function that maps (x, y) to an element of a finite domain 
of truth values of an attribute, and an interpretation  that maps each such element to 
true or false.
We introduced realities as particular interpretations satisfying two reasonable 
consistency rules: they are increasing and  guarantee that the result of true and 
true is true.
Strong realities further satisfy the rule that  false or false should be 
false.
It is worth noticing that our framework could be instantiated on top of DBMS and 
provide a declarative view on equality. 

We studied this framework with respect to functional dependencies.
In this set up, we associate an abstract lattice to any relation.
This abstract lattice naturally induces abstract functional dependencies.
We have shown that realities preserve the semantic of classical FDs.
Furthermore, we exhibited a relationship between abstract FDs and FDs based on realities.
On the other hand, we studied the problem of deciding whether a functional 
dependency over an incomplete database is certain (it holds in all possible worlds 
represented by the realities) or possible (there exists a possible world in which it 
holds).

As future work, we plan to investigate more deeply abstract dependencies and their 
interactions with realities.
There is also an ongoing work on SQL queries.
An interesting question features covering by (abstract) functional dependencies.
More precisely, if we are given a cover of an abstract lattice by abstract FDs, is it 
true that for any reality, the interpretation of this cover will contain a cover of the 
lattice interpretation?
There also pending questions towards possible functional dependencies.
For instance, can we decide in polynomial time that there exists a reality in which a 
given set of FDs holds?


acm


	
