Functional Dependencies (FDs) play a key role in many elds of the relational database model, one of the most widely used database systems. FDs have also been applied in data analysis, data quality, knowledge discovery and the like, but in a very limited scope, because of their xed semantics. To overcome this limitation, many generalizations have been de ned to relax the crisp de nition of FDs. FDs and a few of their generalizations have been characterized with Formal Concept Analysis which reveals itself to be an interesting uni ed framework for characterizing dependencies, that is, understanding and computing them in a formal way. In this paper, we extend this work by taking into account order-like dependencies. Such dependencies, well de ned in the database eld, consider an ordering on the domain of each attribute, and not simply an equality relation as with standard FDs.
Functional dependencies (FDs) are well-known constraints in the relational model
used to show a functional relation between sets of attributes [
Di erent generalizations of FDs have been id Month Year Av. Temp. City de ned in order to deal with imprecision, errors tt21 11 11999965 3336..84 MMiillaann and uncertainty in real-world data, or simply, t3 5 1996 63.1 Rome to mine and discover more complex patterns tt45 51 11999978 5491..64 DRaolmlaes and constraints within data when the seman- t6 1 1999 46.8 Dallas tics of FDs have shown to be too restrictive for t7 5 1996 84.5 Houston modeling certain attribute domains. t8 5 1998 80.2 Houston
For example, consider the database in Table 1 as an example4. Attributes of these 8 tuples are city names, month identi ers, years and average temperatures. From this table, we could expect that the value for average temperature is determined by a city name and a month of the year (e.g. the month of May in Houston is hot, whereas the month of January in Dallas is cold). Therefore, we would expect that this relationship should be somehow expressed as a (functional) dependency in the form city name, month ! average temperature. However, while the average temperature is truly determined by a city and a time of the year, it is very hard that it will be exactly the same from one year to another. Instead, we can expect that the value will be similar, or close throughout di erent years, but rarely the same. Unfortunately, semantics of FDs is based on an equivalence relation and fail to grasp the dependencies among these attributes.
To overcome the limitations of FDs while keeping the idea that some
attributes are functionally determined by other attributes, di erent generalizations
of functional dependencies have been de ned, as recently deeply reviewed in a
comprehensive survey [
The de nition of a variation of a functional dependency shows di erent
problems: characterization, axiomatization and computation. Formal Concept
Analysis (FCA [
In this paper we present an FCA-based characterization of order-like
dependencies, a generalization of functional dependencies in which the equality of
values is replaced by the notion of order. Firstly, we show that the
characterization of order dependencies in their general de nition [
The rest of this paper is organized as follows. In Section 2 we formally
introduce the de nition of functional dependencies, formal concept analysis and the
principle of the characterization of FDs with FCA. In Section 3, we characterize
order dependencies in their general de nition. We show that our formalization
can be adapted to restricted ordered dependencies in Section 4 and lexicographical
ordered dependencies [
Functional dependencies
We deal with datasets which are sets of tuples. Let U be a set of attributes and
Dom be a set of values (a domain). For the sake of simplicity, we assume that
Dom is a numerical set. A tuple t is a function t : U 7! Dom and then a table T is
a set of tuples. We de ne the functional notation of a tuple for a set of attributes
X U as follows, assuming that there exists a total ordering on U . Given a tuple
t 2 T and X = fx1; x2; : : : ; xng, we have: t(X) = ht(x1); t(x2); : : : ; t(xn)i.
De nition 1 (Functional dependency [
x g1 g2 x x g3 x x g4 x x 2.3
Characterization of Functional Dependencies with FCA
It has been shown in previous work that functional dependencies, can be
characterized with FCA. For example, Ganter & Wille [
However, this approach implies that a formal context much larger than the
original dataset must be processed. It was then shown that this formal context
can actually be encoded with a pattern structure [
In [
This way of characterizing FDs and similarity dependencies actually fails for order dependencies, as the relation in this case is not symmetric: it is neither an equality nor a similarity but a partial order in the general case. 3
Although functional dependencies are used in several domains they cannot be
used to express some relationships that exist in data. Many generalizations have
been proposed and we focus in this article on order dependencies [
We remark that this order on the set of values of a single attribute does not need to be a total order, although in many di erent instances, like numeric or character strings domains, this will be the case. In the following, we formalize operator vx (De nition 2) and de ne accordingly order dependencies (De nition 3).
De nition 2 (Attribute-wise ordering). Given two tuples ti; tj 2 T and a set of attributes X U , the attribute-wise order of these two tuples on X is: ti vX tj , 8x 2 X : ti[x] vx tj [x] This de nition states that one tuple is greater {in a sense involving the order of all attributes{ than another tuple if their attribute-wise values meet this order. This operator induces a partial order X = (T; X ) on the set T of tuples. De nition 3 (Order dependency). Let X; Y U be two subsets of attributes in a dataset T . An order dependency X ! Y holds in T if and only if: 8ti; tj 2 T : ti vX tj ! ti vY tj Example. Consider the table on the right with six tuples and three id a b c attributes. Taking va, vb and vc de ned as the ordering . The t1 1 3 1 orders induced by the sets of attributes fag,fbg,fcg and fa; bg are: tt32 32 47 42 a = (T; a) = fft1g ft2g ft3; t6g ft5g ft4gg t4 5 3 9 b = (T; b) = fft5g ft1; t4g ft3g ft2g ft6gg t5 4 2 5 ab = (T; ab) = fft1g ft2g ft6g; t6 3 8 4 ft1g ft3g; Table 3 ft1g ft4g; ft5g ft4gg c = (T; c) = fft1g ft2g ft3; t6g ft5g ft4gg
These orders are such that the order dependency fa; bg ! fcg holds. Remark that De nition 3 is generic since the orders that are assumed for each attribute need to be instantiated: we chose in this example for all attributes, while taking the equality would produce standard functional dependencies.
To achieve the characterization of order dependencies with FCA, we propose
to represent the partial order X = (T; X ) associated to each subset of
attribute X U as a formal context KX (a binary relation on T T thanks to
a general ordinal scaling [
De nition 4 (General ordinal scaling of the tuple set). Given a subset
of attributes X U and a table dataset T , we de ne a formal context for X =
(T; X ) (the partial order it induces) as follows:
where @X = f(ti; tj ) j ti; tj 2 T; ti vX tj g. This formal context is the general
ordinal scale of X [
This way to characterize a partial order is only one among several
possibilities. However, the choice of formal contexts is due to their versatility,
since they can characterize binary relations, hierarchies, dependencies, di
erent orders [
x2X
We can now propose a characterization of order dependencies with FCA. Proposition 1. An order dependency X ! Y holds in T i KX = KXY . X ! Y
The fact that the order dependency fa; bg ! fcg holds can be illustrated
with the formal contexts in Tables 7,8 and 9. We have indeed that Kab = Kabc.
Order dependencies and other FDs generalizations. We have seen that
the de nition of order dependencies replaces the equality condition present in
FDs or other similarity measures present in other dependencies, by an order
relation. This may suggest that order dependencies and other kinds of FDs
generalizations are structurally very similar, whereas this is not the case. Functional
dependencies generate a re exive, symmetric and transitive relation in the set
of tuples, i.e. an equivalence relation. Then the set of tuples can be partitioned
into equivalence classes that are used to characterize and compute the set of
FDs holding in a dataset, as presented in a previous work [
In the generalization of functional dependencies that replaces the equality
condition by a similarity measure or a distance function, this measure generates
a symmetric relation in the set of tuples, but not necessarily a transitive relation.
In turn, this implies that the set of tuples can be partitioned into blocks of
tolerance instead of equivalence classes, as shown in [
In this article, the novelty is that we are dealing with a transitive relation, but not necessarily a symmetric relation. That means that we are not dealing with equivalence classes nor blocks of tolerance any longer, but, precisely, with orders. And since the characterization of these dependencies cannot be performed in terms of equivalence classes nor blocks of tolerance, will use a more general approach: general ordinal scaling. 4
Order dependencies allow taking into account the or- Time People waiting dering of the values of each attribute when looking for t1 10:00 101 dependencies in data. However, violations of the or- tt32 1100::4200 110035 dering due to value variations should sometimes not t4 11:00 77 be considered in many real world scenarios. Consider tt56 1111::2400 8805 the example given in Table 10: it gives variations on the number of people waiting at a bus station over Table 10 time. In such a scenario we can expect that more people will be waiting in the station as time moves on (P eople waiting ! T ime). However, at some point, a bus arrives and the number of people waiting decreases and starts increasing again. It is easy to observe that the order dependency P eople waiting ! T ime does not hold as we have the counter-example:
t4 vP eople waiting t3 and t3 vT ime t4
However, the gap between the values 77 and 105 is signi cant enough to be considered as a di erent instance of the ordering. We can formalize this idea by introducing a similarity threshold = 10 for the attribute P eople waiting such that the ordering between values is checked i the di erence is smaller than . In this way, the previous counter-example is avoided (restricting the binary relation) along with any other counter-example and we have that the restricted order dependency P eople waiting ! T ime holds.
We now formalize the tuple ordering relation, and consequently the notion of restricted order dependencies.
De nition 5. Given two tuples ti; tj 2 T and a set of attributes X attribute-wise order of these two tuples on X is: U , the ti vx tj , 8x 2 X : 0 De nition 6. Let X; Y U two sets of attributes in a table T such that jT j = n, and let X ; Y be thresholds values of tuples in X and Y respectively. A restricted order dependency X ! Y holds in T if and only if:
t[X] vX t0[X] ! t[Y ] vY t0[Y ]
Using these de nitions we can encode the tuple ordering relations as formal contexts for any subset of attributes X U . Indeed, the binary relations between tuples by operator vX can be encoded in a formal context KX = (T; T; vX ) which in turn, can be composed from single attributes x 2 U as follows: \ vX =
vx x2X
Moreover, we can use the same rationale we used to mine order dependencies to nd restricted order dependencies.
Proposition 2. A restricted order dependency X ! Y holds in T i X ! Y
() Proof. This proposition can be proved similarly to Proposition 1. KX = KXY Example. For the previous example, we calculate the corresponding formal contexts shown in Tables 11 and 12 (vT m for Time, and vP p for People waiting ). It is easy to observe that the restricted order dependency P eople waiting ! T ime holds as we have that KP p = KP p;T m.
vT m t1 t2 t3 t4 t5 t6 vP p t1 t2 t3 t4 t5 t6 vT m;P p t1 t2 t3 t4 t5 t6
t1 t1 t1
t2 t2 t2
t3 t3 t3
t4 t4 t4
t5 t5 t5
t6 t6 t6
Restricted order dependencies and other FDs generalizations.
Similarity dependencies (SDs) generalize functional dependencies through the use of
a tolerance relation instead of an equivalence relation between values of tuples
for a given set of attributes. A tolerance relation is a re exive, symmetric and
non-transitive binary association between two tuples given a threshold . In a
nutshell, a SD is established between two tuples if their values are within a
given distance controlled by the threshold. Such dependencies were studied in
a previous work [
Observe that the di erence between De nition 5 and tolerance relations is the drop of the absolute value for tj [x] ti[x] and the requirement that this is a positive number, i.e. ti[x] < tj [x]; 8x 2 X. There is an important di erence between this setting and SDs. While in SDs the threshold is used to relax the strict equivalence condition of standard functional dependencies, from the perspective of order dependencies the threshold is actually used to restrict tuple relations.
Restricted order dependencies have the potential to implement some other
generalizations of FDs such as sequential dependencies and trend
dependencies [
LODs use the notion of lexicographical ordering in a rather unconventional
manner5. While it could be expected that they compare the values of di erent
attributes using lexicographical order, instead new descriptions (or projections) are
composed from the Cartesian product of attribute domains on which the
lexicographical order is applied [
For example, in Table 14 we compose a description using the ordered set X = hb; ei such that the new descriptions or projections of tuples t1; t2 on X are t1X =< 3; 5 > and t2X =< 4; 0 > respectively. It is clear that t1X is lexicographically lower than t2X . However, considering Y = he; bi which is the inverse of X, we have t1Y = 53 and t2Y = 04 where t2Y is lexicographically lower than t1Y . De nition 7 formalizes lexicographical ordering for tuple projections.
De nition 7 ([
The main di erence between LODs and standard order dependencies is that LODs are established over ordered sets and thus, the LOD ha; bi hci does not imply that hb; ai hci holds, where is used to denote a LOD. De nition 8 formalizes lexicographical order dependencies.
De nition 8 ([
In Table 14, we have the LOD hc; a; bi follows. Let X = hc; a; bi and Y = hd; ei.
hd; ei which can be veri ed as
As pointed out in [
In our setting, we have described that a context can be build to encode tuple relations for a given order operator (e.g. vX ; vX ) w.r.t. a set of attributes X. Regarding LODs, this cannot be the case as the set of attributes X is required l to be ordered, meaning that the context Kxy is not necessarily the same as the context Klyx for x; y 2 U (Kl indicates a formal context encoding a lexicographical ordering l). For example, from Table 14 we can build a formal context encoding lhe;di (shown in Table 15) where t2 lhe;di t1, and a di erent formal context encoding lhd;ei (shown in Table 16) where t1 lhd;ei t2.
Nevertheless, a close inspection to a generic LOD X Y reveals that it requires a series of order-like dependencies to hold to be satis ed. For example, if X Y then the functional dependency X ! Y holds. We can prove this as follows. Consider two tuples such that tiX = tjX (their projections w.r.t. X are equivalent). Then, ti lX tj and tj lX ti which, if X Y holds, implies that ti lY tj and tj lY ti which is the same as tiY = tjY . Clearly, tiX = tjX regardless the order of attributes in X and thus we have a functional dependency X ! Y . Now, consider the rst attribute of X, x1 and the rst attribute of Y , y1. Necessarily, t[x1] < t0[x1] ! t[y1] t0[y1] which is an order-like dependency between x1 and y1. Similar analysis can be used to obtain su cient rules so X Y .
For the sake of brevity, we describe a simple algorithm verifying that the LOD X Y holds by checking a cascade of order-like dependencies obtained using the previous analysis. Table 5 presents an example of this algorithm applied to a table containing a LOD. For each attribute x 2 U we generate three di erent formal contexts, namely Kx= = (T; T; =x), Kx< = (T; T; <x) and Kx = (T; T; x). Then, we proceed as follows: { Check functional dependency X ! Y { For the i-th element of Y , yi:
Build K = Ky=1 \ Ky=2 \ Ky=3 \ \ Ky=i 1 For the j-th element of X, xj :
Build K = Kx=1 \ Kx=2 \ Kx=3 \ \ Kx=j 1 Check the order-like dependency (K \ Kx<j \ K ) Kyi Checking ha; bi
hc; di: { Ka=b is empty and the FD ab ! cd holds. a b c d { For the rst element of hc; di: t1 1 ? 1 ? Ka< = f(t1; t2)g Kc = f(t1; t2); (t1; t3); (t2; t3); (t3; t2)g t2 2 1 2 1
= < = f(t2; t3)g Kc = f(t1; t2); (t1; t3); (t2; t3); (t3; t2)g t3 2 2 2 2 { ForKtahe\sKebcond element of element of hc; di:
Ka< \ Kc= = ; Kd = f(t2; t3)g Ka= \ Kb< \ Kc= = f(t2; t3)g Kd = f(t2; t3)g Table Example 17: 6
Di erent generalizations of functional dependencies have been de ned. The definition of a new kind of generalization of functional dependencies needs to cover two di erent aspects: axiomatization and computation.
We have presented a characterization of order dependencies with FCA, which can be potentially extended to other types of order-like dependencies, and are used in many elds in database theory, knowledge discovery and data quality.
These dependencies are part of a set of functional dependencies generalizations where equality condition is replaced with a more general relation. In some cases, the equality is replaced by an approximate measure, in other cases, like in order dependencies, by an order relation.
We have seen that order dependencies are based on a transitive, but not necessarily symmetric relation, contrasting approximate dependencies, which are based on a symmetric, but not necessarily transitive relation. It is precisely this formalization in terms of FCA that allows us to nd these structural di erences between these types of dependencies. We have also seen that this same characterization can be extended to other kinds of approximate dependencies.
This characterization allows us to cover also the computation of these dependencies: they can use the di erent algorithms that already exist in FCA.
This present work needs to be extended to other kinds of order-like dependencies, and some experimentation needs to be performed in order to verify the computational feasibility of this approach.
Acknowledgments. This research work has been supported by the SGR2014-890 (MACDA) project of the Generalitat de Catalunya, and MINECO project APCOM (TIN2014-57226-P) and partially funded by the French National Project FUI AAP 14 Tracaverre 2012-2016.