V. , ?. U. Ei, ?. Vi, V. , ?. Ei et al., Computation of specific ALN (Ov) rewritings * Condition d) of lemma 3 */ 17: if P = E then 18: /* Computation of the rewritings RewS1 w) 22: end if 23: /* Condition e) of lemma 3 *, Rv ? Rv then 25: /* Computation of the rewritings RewS2 RewS2(n, w.Rv) = {?V i ?U Vi | U ? S2(n, w.Rv)} 28: B(w, P ) := B(w, P ) ? RewS2(n, w.Rv) 29: end if 30: /* Computation of both classical ALN and specific ALN (Ov) implicit inconsistencies* Condition f) of lemma 3 */ 32: II = min ? (U ? 2 V | ?w ? .(? 0v) ? Q ? ? ? (Vi ? U ) and w

N. Foto, C. Afrati, P. Li, and . Mitra, Answering queries using views with arithmetic comparisons, PODS'02, Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp.209-220, 2002.

R. Agrawal and R. Srikant, Fast algorithms for mining association rules in large databases, VLDB'94, Proceedings of the International Conference on Very Large Data Bases, pp.487-499, 1994.

F. Baader, D. Calvanese, D. L. Mcguinness, D. Nardi, and P. F. Patel-schneider, The Description Logic Handbook: Theory, Implementation, and Applications, 2003.
DOI : 10.1017/CBO9780511711787

C. Beeri, A. Halevy, and M. C. Rousset, Rewriting queries using views in description logics, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems , PODS '97, pp.99-108, 1997.
DOI : 10.1145/263661.263673

A. Borgida and P. F. Patel-schneider, A semantics and complete algorithm for subsumption in the classic description logic, Journal of Artificial Intelligence Research (JAIR), vol.1, pp.277-308, 1994.

F. De, M. , and J. Petit, Zigzag: a new algorithm for mining large inclusion dependencies in database, ICDM'03, Proceedings of the IEEE International Conference on Data Mining, pp.27-34, 2003.

T. Eiter and G. Gottlob, Identifying the Minimal Transversals of a Hypergraph and Related Problems, SIAM Journal on Computing, vol.24, issue.6, pp.1278-1304, 1995.
DOI : 10.1137/S0097539793250299

F. Flouvat, F. De-marchi, and J. Petit, iZi: A New Toolkit for Pattern Mining Problems, ISMIS'08, International Symposium on Methodologies for Intelligent Systems, pp.1-6, 2008.
DOI : 10.1007/978-3-540-68123-6_14

F. Goasdoué and M. Rousset, Answering queries using views, ACM Transactions on Internet Technology, vol.4, issue.3, pp.255-288, 2004.
DOI : 10.1145/1013202.1013204

D. Gunopulos, R. Khardon, H. Mannila, and S. Saluja, Discovering all most specific sentences, ACM Transactions on Database Systems, vol.28, issue.2, pp.140-174, 2003.
DOI : 10.1145/777943.777945

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.1494

Y. Alon and . Halevy, Answering queries using views: A survey, VLDB Journal, vol.10, issue.4, pp.270-294, 2001.

I. Horrocks and U. Sattler, Ontology reasoning in the shoq(d) description logic, IJCAI'01, International Joint Conferences on Artificial Intelligence, pp.199-204

Y. Huhtala, J. Kärkkäinen, P. Porkka, and H. Toivonen, Tane: An Efficient Algorithm for Discovering Functional and Approximate Dependencies, The Computer Journal, vol.42, issue.2, pp.100-111, 1999.
DOI : 10.1093/comjnl/42.2.100

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.3544

L. Khachiyan, E. Boros, K. M. Elbassioni, and V. Gurvich, An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation, Discrete Applied Mathematics, vol.154, issue.16, pp.2350-2372, 2006.
DOI : 10.1016/j.dam.2006.04.012

R. Küsters, Non-Standard Inferences in Description Logics, volume 2100 of Lecture Notes in Computer Science, 2001.

M. Lenzerini, Data integration, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , PODS '02, 2002.
DOI : 10.1145/543613.543644

Y. Alon, A. Levy, J. J. Rajaraman, and . Ordille, Querying heterogeneous information sources using source descriptions, VLDB'96, Proceedings of the International Conference on Very Large Data Bases, pp.251-262, 1996.

H. Mannila and H. Toivonen, Levelwise search and borders of theories in knowledge discovery, Data Mining and Knowledge Discovery, vol.1, issue.3, pp.241-258, 1997.
DOI : 10.1023/A:1009796218281

R. Pottinger and A. Y. Halevy, Minicon: A scalable algorithm for answering queries using views, VLDB Journal, vol.10, issue.2-3, pp.182-198, 2001.

A. Schaerf, Reasoning with individuals in concept languages, Data & Knowledge Engineering, vol.13, issue.2, pp.141-176, 1994.
DOI : 10.1016/0169-023X(94)90002-7

URL : http://doi.org/10.1007/3-540-57292-9_49

J. D. Ullman, Information integration using logical views, Theoretical Computer Science, vol.239, issue.2, pp.189-210, 2000.
DOI : 10.1016/S0304-3975(99)00219-4

URL : http://avid.cs.umass.edu/courses/645/s2006/645-paper3.pdf

. Lemma-4, Let V be a terminology in ALN (O v ) Let Q 1 and Q 2 two consistent conjunctions of views in V. Q 1 ? Q 2 iff Q 2 is made of a subset of views occurring in Q 1

?. {1, Since V is a primitive terminology that is normalized and expanded, each view V ij is a conjunction between a concept description D ij and a unique atomic concept V ij

Q. Assume, ?. .. ??-?-v-1, ?. V-j+1, ?. , and ?. {1, n}, is subsumed by Q (i.e. Q ?? ? Q) We have also Q ? ? Q ?? . We are going to show that in this case, Q ? is not maximally contained in Q. To achieve that, we show that Q ?? is not equivalent to Q ?, ? V n . According to the open word assumption, Q ?? ? (D 1 ? . . . ? D (j?1) ? D (j+1) ? . . . ? D n ) ? (A 1 ? . . . ? A (j?1) ? A (j+1) ? . . . ? A n

Q. ??-are, ?A (j?1) ?A (j+1) ?. . . ?A n . Indeed A i is an atomic concept associated with a single view V i that occurs only once in Q ? . Then there exists Q ?? s

Q. ??-?-v-i1, ?. .. {v-i1, }. .. {v-1,, }. We-have, Q. ??-?-q et al., V n is a maximally-contained rewriting of Q. In other words, we have to show that there is no Q ?? s We refer by (*) the following assumption: for all ? V in?1 , s.t. {V i1 , According to hypothesis of lemma 2 Q ? ? V 1 ? . . . V n is subsumed by Q. Assume that Q ? is not a maximally-contained rewriting of Q. Then there exists a conjunction of views Q 1 s.t. Q ? ? Q 1 ? Q et Q ? ? Q 1 . According to lemma 4, Q 1 subsumes strictly Q ? if Q 1 refers only a strict subset of views occurring in Q ? and in this case, ? D (j?1) ? D (j+1) ? . . . ? D n ) ? (A 1 ? . . . ? A (j?1) ? A (j+1) ? . . . ? A n ) and Q ? ? (D 1 ?. . .?D (j?1) ?D (j+1) ?. . . ?D n )?(A 1 ?. . . ?A (j?1) ?A (j+1) ?. . .?A n )., V n } and that is subsumed by Q. Then each conjunction of views that uses supersets of views from Q 1 is subsumed by Q. That contradicts the assumption (*)

Q. We-have and ?. , ? V i k s.t. Q ? is maximally-contained in Q. Therefore, according to lemma 2, Q ? is formed of a minimal subset of views s

?. If and P. {a, ¬A} then according to theorem 1, one of the views contains ?w.P . Since the set {V i1 , . . . V i k } is minimal, one view is sufficient to rewrite Q ? ?w

?. If and P. , ? nr) then according to theorem 1, one of the views contains ?w.(? mr), with m ? n. Since the set {V i1 , . . . V i k } is minimal, one view is sufficient to rewrite Q ? ?w

?. If and P. , then according to theorem 1, one of the views contains ?w.(? m r) with m ? n. As above, one view is sufficient to rewrite Q ? ?w

?. If and P. , according to normalization rules 8) and 9) and theorem 1, we can find (k ? 1) views that contain respectively a conjunct ?w.r.E ij s.t. ? k j=1 E ij ? E ? and card(E ? ) ? n. The worst case occurs when the E ij 's have in pairs a single distinct value and, we have to infer ?w.(? n r), with n = 0. If the maximal number of values in the E ij 's is l then in worst case, (l + 1) sets of values are necessary to obtain the empty set, Therefore if r ? R v and P = (? n r)

?. If, P. =. , and E. , according to normalization rule 8 and theorem 1, k ? 1 views contain respectively a conjunct ?w.E ij such that ? k j=1 The worst case occurs when E ij have in pairs a single distinct value, and we have to infer ?w.E, with E = ?. If the maximal number of values in the E ij 's is l then (l + 1) sets of values are necessary to obtain the empty set, Therefore if P = E, in the worst case

T. ??-in, H. Such, and T. Q. , rewriting of Q built with the elements of the Q's buckets and T Q ? the set of views forming Q ? . Assume that T ? Q is not a minimal transversal of H B . Therefore there exists a minimal transversal As T Q ?? meets every edge in E B and thus every bucket of Q, the conjunction Q ?? of views from T Q ?? is a rewriting of Q and Q ? cannot be a maximally

}. .. and Y. =. {e-j1, X) is true. We have to prove that for all Y ? L S1(E,w) s.t ) is true, E j k }, with Y ? X As P S1(E,w) (E, X) is true

P. As and . S2, Rv) (E, X) is true

. Proof, I. Let, and . S2, Rv) s.t. P S2(n,w.Rv) (E, X) is true }. Bd + (IEN ) gathers the most specialized true patterns. The negative border Bd ? (IEN ) gathers the most generalized false patterns, i.e., the minimal subsets of views whose cardinality of the intersection of their restricted set of values for the word w

. Proof and X. Let, X) is true. We have to prove that for all Y ? L TH B s.t

. Proof and N. T. Let, X) is true }. By definition, the negative border Bd ? (N T ) gathers the most generalized false patterns w.r.t. set inclusion, i.e., the minimal subsets of views which are transversal in H B