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 ,

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. ,

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. ,

The Description Logic Handbook: Theory, Implementation, and Applications, 2003. ,

DOI : 10.1017/CBO9780511711787

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 semantics and complete algorithm for subsumption in the classic description logic, Journal of Artificial Intelligence Research (JAIR), vol.1, pp.277-308, 1994. ,

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. ,

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

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

Answering queries using views, ACM Transactions on Internet Technology, vol.4, issue.3, pp.255-288, 2004. ,

DOI : 10.1145/1013202.1013204

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

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

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

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

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

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

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

Querying heterogeneous information sources using source descriptions, VLDB'96, Proceedings of the International Conference on Very Large Data Bases, pp.251-262, 1996. ,

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

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

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

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

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 ,

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 ,

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 ,

?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 ,

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 (*) ,

? 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 ,

¬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 ,

? 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 ,

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 ,

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) ,

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 ,

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 ,

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 ,

Rv) (E, X) is true ,

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 ,

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

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 ,