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 t1 1 1995 36.4 Milan and uncertainty in real-world data, or simply, t2 1 1996 33.8 Milan to mine and discover more complex patterns tt43 55 11999976 5693..61 RRoommee and constraints within data when the seman- t5 1 1998 41.4 Dallas tics of FDs have shown to be too restrictive for tt67 15 11999996 8446..58 HDoaulsltaosn modeling certain attribute domains. For exam- t8 5 1998 80.2 Houston ple, consider the database in the table above as ? Note: A longer version of this paper has been accepted at the conference Concept
Lattices and their Applications, Moscow, Russia, July 2016. 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 [
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 before to conclude. 2
2.1
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.
4 Example from The University of Dayton, that shows the month average
temperatures for di erent cities: http://academic.udayton.edu/kissock/http/Weather/
De nition 1 (Functional dependency [
On the bottom-right gure, we illustrate this characterization with the set of tuples from Table 1 where each possible pair of tuples is an object in the formal context. Attributes remain the same. Object (ti; tj ) has attribute m i ti(m) = tj (m).
The concept lattice in the bottom right: there are two
implications, namely d ! c and d ! a, which are also the
functional dependencies in the original set of tuples. However, this K a b c d
approach implies that a formal context much larger than the (t1; t2)
original dataset must be processed. It was then shown that ((tt11;; tt43))
this formal context can actually be encoded with a pattern (t2; t3)
structure [
As we will show next, 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
Characterization of Order Dependencies with FCA
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 [
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 [
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 3,4 and 5. 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. Since the characterization of these dependencies cannot be performed in terms of equivalence classes nor blocks of tolerance, it requires for a more general approach: general ordinal scaling. 4
Characterization of Restricted Order Dependencies 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- tt23 1100::2400 110035 dering due to value variations should sometimes not t4 11:00 77 be considered in many real world scenarios. Consider tt65 1111::4200 8805 the example given in Table 6: it gives variations on the number of people waiting at a bus station over time. Table 6 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 on X is: ti vx tj , 8x 2 X : 0 tj [x] ti[x]
U , the 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 i : 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 : vX = T 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 ()
KX = KXY Proof. This proposition can be proved similarly to Proposition 1. Example. For the previous example, we calculate the corresponding formal contexts shown in Tables 7 and 8 (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.
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 [
The current approach has the potential to implement some other FD
generalizations of such as sequential dependencies and trend dependencies [
We have presented a characterization of order dependencies with FCA, which can be potentially extended to other types of order-like dependencies, used in di erent elds of 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 similarity 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.
Nevertheless, the present work needs to be extended to other kinds of orderlike dependencies while 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, the MINECO project APCOM (TIN2014-57226-P) and the French National Project FUI AAP 14 Tracaverre.