Computer Science
Computer Science-2021.gz:143266
Computer Science
135cad46f262f58c74172128b502538693d109e1
Essence of Factual Knowledge

Knowledge bases are collections of domain-specific and commonsense facts. Recently, the sizes of KBs are rocketing due to automatic extraction for knowledge and facts. For example, the number of facts in WikiData is up to 974 million! According to our observation, current KBs, especially domain KBs, show strong relevance in relations according to some topics. These patterns can be used to conclude and infer for part of facts in the KBs. Therefore, the original KBs can be minimzed by extracting patterns and essential facts.


I. INTRODUCTION
Knowledge bases are collections of domain-specific and commonsense facts. Recently, the sizes of KBs are rocketing due to automatic extraction for knowledge and facts. For example, the number of facts in WikiData is up to 974 million! According to our observation, current KBs, especially domain KBs, show strong relevance in relations according to some topics [1], [2]. These patterns can be used to conclude and infer for part of facts in the KBs. Therefore, the original KBs can be minimzed by extracting patterns and essential facts.
In this paper, we introduce a framework for extracting knowledge essence and reducing overall volume of KBs by mining semantic patterns in relations. Facts are formalized as first-order predicates and patterns are induced as Horn rules. Table I and Rule (1), (2) show an example of such extraction. By extracting the rules from listed facts, both table Ib and Ic can be inferred from other tables and then be removed.
The remaining is organized as follows: Section II analysed properties of rules as equivalence classes. Essence extraction problem is formally defined in Section III. And Section IV introduces the basic framework for essence extraction. Finally Section VI concludes the paper.

A. Semantic Length and Fingerprint of a Rule
First-order Horn rules are adopted in our technique to describe semantic patterns in relations. They can further be decomposed into equivalence classes. Elements in each of the classes are arguments that are assigned to the same variables, and if some argument is assigned to constants, then the corresponding equivalence class only consists of the argument and the constant. For example, Rule (1) is decomposed to the following equivalent classes (number in the brackets denotes the argument index of certain relation, starting from 0): The length of a rule is defined by the follwoing equation: where C i is one of these equivalence classes.
Fingerprints of rules are based on the equivalence classes with labels of arguments in the head that it applies to. For example, the last column of the above example shows the label of head arguments. Proof. (Necessity)If two rules are semantically equivalent, they can be written in syntactically identical form. Thus equivalence classes of corresponding variables or constants are identical.
(Sufficiency)Each equivalence class tells position of one variable. Therefore, equivalence of all classes ensures that the set of predicates in both rules are identical. The labels of head arguments further determine that the head predicates are the same. Thus, the two rules are identical.

B. Search Space for Rules
Let Ω be the search space for first-order Horn rules. Some elements in Ω make no sense and should be excluded. If some predicate in the body is identical to the head, then the predicate in the body is redundant. These rules are trivial rules. If some subset of the body does not share any variable with the remaining part (include the head), then the rule is either redundant nor unsatisfiable. The subset is called independent fragment. The new search space excluding these two types of rules is written as Ω m .

C. Extension on Rules
Definition 2 (Limited Variable, Unlimited Variable, Generative Variable). A variable is unlimited in some Horn rule r if there is only one argument in r that is assigned to it. A variable is limited in r if there exist at least two arguments in r that are assigned to it. A variable is generative if there exist arguments in both the head and body of r that are assigned to it.
Searching for rules starts from most general forms, i.e. rules only with head predicate and arguments in the predicate are all unique unlimited variables. To construct new rules, new equivalence conditions are added to the equivalence classes. Syntactically, these operations fell in five extension operations, which is noted by ext(r): Case 1: Assign an existing limited variable to some argument. Case 2: Add a new predicate with unlimited variables to the rule and then assign an existing limited variable to one of these arguments. Case 3: Assign a new limited variable to a pair of arguments. Case 4: Add a new predicate with unlimited variables to the rule and then assign a new limited variable to a pair of arguments. In this case, the two arguments are not both selected from the newly added predicate. Case 5: Assign a constant to some argument.
According to the rule extension, ∀r, r e ∈ Ω m , if r e ∈ ext(r), then r e is the extension of r, and r is the origin of r e (denoted as r ∈ ext −1 (r e ) since one may have multiple origins). Neighbours of a rule in Ω m consist of all its extensions and origins. The above extension operations can be used arXiv:2107.00729v3 [cs.DB] 20 Oct 2021 person lily ginny to search on Ω m . Let S = {r|r has only a head predicate p and all arguments of p are unlimited variables}, every element in Ω m can be searched from some r 0 ∈ S. To prove this we define a property link between predicates in a certain rule: If two predicates p and q in a rule r share a limited variable X, then p and q are linked by X in r, written as p X q, or in short p q. Moreover, if there is a sequence of predicates p w 0 · · · w k q, then there is a linked path between p and q, written as: p ↔ q. With this property, we can prove the search completeness as follows: Lemma 3. ∀r ∈ Ω m , every predicate in r has a linked path with the head of r.
Proof. Suppose a predicate p in rule r has no linked path with the head. Then p is not itself the head. Let P = {q|p ↔ q}, every predicate in P has no linked path with the head. Then the fragment noted by P does not share any variables with remaining predicates. Namely, P denotes an independent fragment in rule r. According to the definition of Ω m , we have r ∈ Ω m , which contradicts with r ∈ Ω m .
Proof. Suppose p X q in r. During the searching process of r, when p is already in a intermediate status r , an extension of r can be constructed by adding a new predicate q and turning corresponding variables to X. Thus, predicate q is introduced into r . Therefore, if w ↔ q and w is already in a intermediate status, then q can be introduced into r . According to Lemma 3, all predicates in r has linked path with its head. Each predicate can be introduced into the rule iteratively starting from the head predicate where arguments are all different unlimited variables. Other limited variables and constants can be added to the rule by other extension operations to finally construct r.
Rules with independent fragments will not be constructed starting from S, as the extension operations do not introduce where |N | is the number of predicates in N , and so be |C|. |H| is defined as the sum of lengths of all rules in it.
Complexity of essence extraction can be proved by reducing minimum vertex cover problem to relational compression. Let G vc = V vc , E vc be the graph in the vertex cover problem. By the following settings we create a relational knowledge base aligning with G vc : Let v be a unary predicate in B for each v ∈ V vc ; let edge be a unary predicate in B for edges; add two constants e ij and e ij to C and six predicates edge(e ij ), edge(e ij ), v i (e ij ), v i (e ij ), v j (e ij ), v j (e ij ) to B for each (v i , v j ) ∈ E vc ; add the following predicates to B: edge(c 1 ), edge(c 2 ), . . . , edge(c 2·|Evc|+1 ); and add the following constants to C: d 1 , d 2 , . . . , d 4·|Evc|+1 .
For example, Figure 1 shows a graph with three vertices and two edges. The corresponding setting of relational compression is as follows: By reducibility from minimum vertex cover problem to relational compression we can prove the latter is NP-hard. The details are as follows: Lemma 7. edge(X) ← true is not in H.
Proof. Let arg + (p) = {c ∈ C|p(c) ∈ B}, then |arg + (edge)| = 2n + 2n + 1 = 4n + 1, where n = |E vc |. Thus, the number of predicates this rule entails is 4n + 1. Taking constants d 1 , . . . , d 4n+1 into consideration, the number of counter examples this rule entails is also 4n + 1. The size reduced is 4n + 1 − (4n + 1) − 1 = −1, no actual reduction. Therefore, it does not reduce the size of knowledge base. It is not in H. Proof. According to Lemma 8, proof of edge(e) ∈ S relies only on predicates of v i . No matter predicates of v i is provable or not, the rules of edge(X) ← v i (X) can always be applied to prove edge(e) ∈ S. Suppose ∃edge(e) ∈ S such that edge(e) ∈ R. Then there is another predicate edge(e ) ∈ S and edge(e ) ∈ R, where e and e correspond to some edge in E vc and its duplicate, since these two predicates are both entailed by some rule edge(X) ← v i (X) if one of them is entailed by the rule. Then a new rule can be applied to entail these two predicates to further reduce the size of given result. However, according to definition of relational compression, output cannot be further reduced. Contradiction occurs. Theorem 11. Relational compression is NP-hard.
Proof. Let V c be the set of minimum vertex cover of G vc . According to the lemmas above, V c = {v ∈ V vc |∃edge(X) ← v(X) ∈ H}. All the operations involved with reducibility are with polynomial cost. Thus minimum vertex cover problem can be polynomially reduced to relational compression. Relational compression is NP-hard.

IV. EXTRACTION FRAMEWORK
To tell whether a fact is provable by others, we employ a directed graph G = V, E to encode dependency among facts with respect to inference. V = B ∪ { }, where each vertex is either a fact in B or an assertion of truth under no condition. (b, h) ∈ E if b is involved in the proof of h by some rule. ( , h) ∈ E if h can be inferred by some rule with empty body. The extraction for essence is given by Algorithm 1.
If the dependency graph is a DAG, then essential predicates are represented by the vertices with zero in-degree. However, if cycles appear in G, then at least one vertex in each cycle should be included in N . This assertion is proved bellow: Lemma 12. If some cycle in G is not overlapping with other cycles, then at least one vertex should be included in N .
Proof. A vertex in the dependency graph is guaranteed provable if it is in N or all of its in-neighbours are guaranteed provable. In the following proof, we assume that all other parts in G are guaranteed provable except the cycles. If none of vertices in a single cycle (not overlapping with other cycles) is included in N , then for each of these vertices, there is one in-neighbour not guaranteed provable. Thus, none of vertices in the cycle is guaranteed provable. At least one vertex should be selected in N .
Lemma 13. If some cycles in G are overlapping, then at least one vertex should be included in N .
Proof. Suppose two cycles are overlapping in G. If none of vertices in these cycles is in N , then none of them are guaranteed provable. If one of the vertices in the non-overlapping part is in N , then from this vertex to the one before intersection, all of these vertices are guaranteed provable. The other cycle is remained equivalent to circumstances of non-overlapping cycle and at least one of these vertices should be in N . If one of the vertices in the overlapping part is in N , then both cycles are guaranteed provable. In this case, still, at least one vertex is selected in each cycle. Cases are similar for more than two over lapping cycles.
Lemma 14. If there are cycles in the dependency graph, then at least one vertex should be included in N .
Proof. It is clear by Lemma 12 and 13.
In the framework, two components may be implemented in different strategies according to specific domains: find-SingleRule and CoverCycle. To implement findSingleRule, pruning techniques are needed as the search space is large and useful candidates are sparse in the space. Given that semantic correlations may be strong in domain specific KBs, cycles are predicted to be large and frequent. Therefore, efficient coverage procedure is also required in the framework.

V. RESTORE THE ORIGINAL KB
As the dependency graph implies, if all the in-neighbours of some vertex in G is in the KB, the vertex can be inferred by applying some rule in H. Thus, in order to restore the original KB, we can iteratively apply each rule on current database until there is no more records inferred. Inference by a single rule can be done without full join in the relational data model. The algorithm is shown in Algorithm 2.
The cost of single inference is proportional to the number of equivalence classes and to the size of relevant relations. The number of equivalence classes is proportional to the number of columns in B . The cost for single inference is: where φ(f ) is the arity of functor f . From the implication of the dependency graph, inference operations are the same as visiting vertices along paths in the graph. Thus, the maximum number of iterations is no larger than the maximum length of simple paths in G. The overall cost of decompression is: where d max the maximum length of simple path in G.
Lemma 15. When d max has reached to its maximum, the worst case cost of restoring is O(|B| 3 ).
Proof. According to the definition, d max ≤ |B| − 1. When d max = |B| − 1, all vertices in G form one single simple path. In this case, there can only be one rule in H and only one relation in B. And the maximum number of arguments is also |B| − 1, otherwise the rule cannot summarize B. Therefore, the worst case cost is: Other cases are the same. T ← T + w t 22: end for 23: return T

VI. CONCLUSION
In this paper, we introduced a framework for extracting essence from factual knowledge. Theoretical proofs are also given for key properties of the framework. To put it into practice, more concrete work is required to design and analyze in findSingleRule and CoverCycle.