CN107016065A - It is customizable to rely on semantic effective origin filter method - Google Patents

Abstract

The present invention proposes a high-efficiency origin filtering method that can customize dependency semantics, including the following steps: Step 1: Check the origin graph to be filtered to ensure that it is a directed acyclic graph that conforms to the standardized origin model and its model constraints; Step 2 : Declare origin filtering requirements, that is, origin elements to be filtered, direct or indirect origin dependencies; Step 3: Process the nodes and node pairs to be filtered according to the filtering rules and repair rules in the origin filtering mechanism; Step 4: Organize according to the origin graph Organize and update the origin map according to the rules to obtain the origin filter view; Step 5: Quantitatively evaluate the effectiveness of the origin filter view according to the origin filter view evaluation model, and generate an origin filter report. The method of the invention can selectively filter or maintain the dependency semantics between origin elements, and can effectively maintain the utility of the published origin data while realizing the filtering requirement.

Description

High-Utility Origin Filtering Method with Customizable Dependency Semantics

technical field

The invention belongs to the technical field of data sharing, relates to the technical field of origin filtering for realizing safe sharing of origin data, and in particular to a high-efficiency origin filtering method with customizable dependency semantics.

Background technique

Data Provenance (Data Provenance, referred to as origin) is also known as data traceability, data lineage, etc. It records the source of data, the processing process experienced by data, and related information such as time, place, tools, methods, strategies, organizations, and personnel. Metadata of data evolution history. Provenance is an important basis for assessing the authenticity, credibility and reproducibility of data. In order to realize the release and sharing of origin data across organizations, W3C successively released the origin data model standards OPM and PROV-DM, which represent origin information with a marked directed acyclic graph, as shown in Figure 1. The core structure of the origin graph includes three types of origin elements, such as entities, activities, and agents, and various dependencies among them.

Origin data records describe the history of data evolution and may contain various sensitive information. For example, disclosing the origin information of legal documents, such as the information of its framers and the controversial draft content before its formation, may be sensitive. Direct publishing and sharing of original provenance information may result in the disclosure of sensitive information with serious consequences. The original origin also often contains some redundant details that the user does not need. Provenance Sanitization, also known as Provenance Revision and Provenance Abstraction, is a transformation of the Provenance Graph, which selectively filters sensitive or redundant information in the Provenance Graph before the Provenance data is released to obtain a safe and usable Provenance Filtered View (sanitized provenance view) new technology.

Existing provenance filtering techniques can filter specific nodes, edges and even subgraphs in the provenance graph, but there are still the following deficiencies. First of all, the existing technology cannot control the origin-dependent semantics, and cannot flexibly increase or decrease the origin-dependent semantics contained in the origin graph as needed, especially the origin-indirect-dependent semantics, and the coverage of filtering objects is not comprehensive. Secondly, the existing technologies focus on the realization of origin security. When filtering sensitive information, they often use group abstraction to aggregate related nodes, causing some nodes and related edges that should be disclosed to be over-abstracted and hidden, resulting in desensitization. The origin filter view for is low. Origin utility, on the other hand, is the degree to which origin users acquire and use origin to meet their business needs. A data origin with too little utility loses its value.

Contents of the invention

In order to overcome the shortcomings of the prior art, the purpose of the present invention is to provide a high-efficiency origin filtering method that can be customized and depend on semantics, so as to solve the problems of incomplete coverage of filtering objects and low origin utility after desensitization in the existing origin filtering technology. ; Can selectively filter or maintain the dependency semantics between the source elements, the filtering object not only includes the source elements and direct dependencies that can be processed by the existing source filtering technology, but also includes the source indirect dependencies that contain rich semantics; the filter of the present invention The mechanism includes filtering rules and matching repair rules, which can effectively maintain the effectiveness of the original data while realizing the filtering requirements.

In order to achieve the above object, the technical scheme adopted in the present invention is:

A high-efficiency origin filtering method with customizable dependency semantics, comprising the following steps:

Step 1: Check the origin graph to be filtered to ensure that it is a directed acyclic graph that conforms to the standardized origin model and its model constraints;

Step 2: Declare origin filtering requirements, that is, origin elements to be filtered, direct and indirect origin dependencies. Among them, origin elements are represented by nodes in the origin graph, and direct or indirect dependencies are represented by node pairs in the origin graph;

Step 3: Process the nodes and node pairs to be filtered according to the filtering rules and repairing rules in the origin filtering mechanism. The filtering order is nodes, pairs of nodes representing direct dependencies, pairs of nodes representing indirect dependencies. Select and apply appropriate filtering and repairing operations according to the type of the filtering object and the combination of the type of the direct cause node and the direct consequence node; in particular, the filtering and repairing operation suitable for indirect dependencies is selected according to the minimum cost decision method, and the cost includes Filter cost and repair cost.

Step 4: Arrange and update the origin graph according to the origin graph sorting rules to obtain the origin filter view; check the proxy nodes and activity nodes in the origin graph, and delete them if they are independent; check the edges in the origin graph, if the edges are attached If one of the vertices has been deleted, delete the edge; check the edge in the origin graph, if the dependency represented by the edge can be deduced from other edges, delete the edge; update the origin graph to get the final origin filter view.

Step 5: Quantitatively evaluate the utility of the origin filtering view according to the origin filtering view evaluation model, and generate an origin filtering report. Among them, the origin utility is the synthesis of the following measurements: (1) the retention rate of nodes in the filtered view except for the nodes to be filtered; (2) the retention rate of edges in the filtered view except for the edges to be filtered; (3) In addition to the connected path node pairs to be filtered, the retention rate of connected path node pairs in the filter view; (4) the ratio of the number of connected node pairs with unchanged paths to the total number of connected node pairs in the filter view; the source filter report includes the original Origin graphs, filtering requirements, origin filtering views, satisfaction of filtering requirements, multi-filtering origin elements and dependencies, reasonable origin dependencies changed to fix origin dependency semantics, and utility values for origin filtering views.

Compared with prior art, the beneficial effect of the present invention is:

1. Solve the problem that the existing methods cannot customize the origin dependency semantics, realize the full coverage of filtering objects, not only support on-demand filtering of origin elements and direct dependencies, but also support on-demand filtering or maintaining indirect dependencies;

2. The origin utility maintenance mechanism is designed, that is, according to the inherent nature of the origin-dependent semantics, the restoration rules are designed in the origin filtering mechanism, which effectively maintains the origin utility while realizing the filtering requirements, and reduces the origin consumers' barriers to the use of the origin, It is convenient for it to use the source to achieve business goals such as authenticity assessment and credibility verification of relevant data.

3. Design the origin filter view evaluation model, quantitatively evaluate the effectiveness of the origin filter view, and generate the origin filter report, to provide a scientific basis for further making various business decisions by using the origin.

Description of drawings

Fig. 1 is a core structure diagram of the standard origin model PROV-DM referred to in the present invention.

Fig. 2 is a flow chart of the origin filtering method of the present invention.

Fig. 3 is a visual schematic diagram of filtering rules and repairing rules (Table 1) of entity class nodes.

Fig. 4 is a visual schematic diagram of filtering rules and repairing rules (Table 2) of activity class nodes.

Fig. 5 is a visual schematic diagram of filtering rules and repairing rules (Table 3) of proxy class nodes.

Figure 6 is an example of the original source graph before filtering.

FIG. 7 is an origin filtering view obtained by using the method of the present invention to process FIG. ₆ in the case of filtering requirement R1.

Fig. 8 is an origin filtering view obtained by processing Fig. 6 with other methods in the case of filtering requirement R ₁ .

Fig. 9 is an origin filtering view obtained by processing Fig. ₆ with the method of the present invention in the case of filtering requirement R2.

detailed description

Further illustrate the present invention below in conjunction with accompanying drawing and specific embodiment, should be understood that these embodiments are only for illustrating the present invention and are not intended to limit the scope of the present invention, after having read the present invention, those skilled in the art will understand various aspects of the present invention All modifications of the valence form fall within the scope defined by the appended claims of the present application.

The present invention assumes that the origin graph to be filtered has traceable dependency semantics, that is, if any node v can be traced back to another node u, then u is part of the cause of v. The embodiments refer to the standard origin model PROV-DM, and the related concepts involved in the method of the present invention are defined as follows:

Definition 1 origin graph ProvGraph=(V, E):

Node set V={v ₁ , v ₂ ,...,v _n }, in the origin graph, each node v represents an origin element, and the origin elements are divided into entities (EN), activities (AC) and agents (AG), etc. Three types, representing the intermediate morphological artifacts in the process of data evolution, the operating activities experienced, and the people or organizations that implement related operating activities;

Mapping τ: V → {EN, AC, AG} maps node v to its type, that is, for node v ∈ V, its type τ(v) ∈ {EN, AC, AG};

Edge set E={e _i =<u, v>|u∈V;v∈V; i=1, 2,..., m}, in the origin graph, edge e=<u, v> is from v to The directed arc of u indicates the direct dependence of v to u, that is, v is the direct consequence of u, and u is the direct cause of v.

Definition 2 Subsets of origin elements: entity set (Entity), activity set (Activity) and agent set (Agent):

According to the type of source elements, the source element set V can be divided into three mutually disjoint subsets: entity set (Entity), activity set (Activity) and agent set (Agent), there is V=Entity∪Activity∪Agent.

Entity set: Entity＝{ent|ent(id, attributes), τ(ent)＝EN}, an entity node e describes the state of a data object at a certain time period or point in the past, and e has a unique identifier (id ) and a series of attributes;

Activity set: Activity＝{act|act(id, startTime, endTime, attributes), τ(act)＝AC}, an activity node a represents the process that acts on the entity node within a period of time or will cause the state to change a series of operations;

Agent set: Agent={ag|ag(id, attributes), τ(ag)=AG}, an agent node ag represents an agent that takes some responsibility for the occurrence of an activity, the existence of an entity, or the activity of another agent person or organization.

The dependencies between different types of origin elements have different semantics, and the edges in the origin graph can be divided into different subclasses according to the types of interdependent origin elements.

Define 3 subsets of direct dependencies: Usage, Generation, Association, Attribution, Derivation, Communication, Delegation:

The edges in the origin graph represent the causal relationship between two adjacent nodes. The edge set E can be divided into seven mutually disjoint subsets, E=Usage∪Generation∪Association∪Attribution∪Derivation∪Communication∪Delegation, where:

Usage (use dependency) = {<ent, act>|ent∈Entity, act∈Activity, which means that the activity act uses the entity ent};

Generation (generating dependency)={<act, ent>|act∈Activity, ent∈Entity, which means that the entity ent is generated by the activity act};

Association (association dependency) = {<ag, act>|ag∈Agent, act∈Activity, indicating that the agent ag takes responsibility in the activity act};

Attribution (attribution dependency) = {<ag, ent>|ag∈Agent, ent∈Entity, indicating that the agent ag is responsible for the entity ent};

Derivation (derived dependency)={<ent ₁ , ent ₂ >|ent ₁ , ent ₂ ∈ Entity, which means that entity ent ₂ is derived from entity ent ₁ };

Communication (communication dependence) = {<act ₁ , act ₂ >|act ₁ , act ₂ ∈ Activity, indicating that activity act ₂ uses the entity generated by activity act ₁ };

Delegation (agent dependency)＝{<ag ₁ , ag ₂ >|ag ₁ , ag ₂ ∈ Agent, means that agent ag ₂ represents agent ag ₁ , and ag ₁ is called the superior agent of ag ₂ }.

Definition 4 origin indirect dependency set PathSet:

Connected path P(u, v)={v _i |v ₀ =u; v _k =v; <v _i , v _i+1 >∈E;i=0,1,...,k-1;k>2 }, is the sequence of nodes in the origin graph, indicating the indirect dependency of node v on u, that is, v is the indirect consequence of u, and u is the indirect cause of v;

The set of connected paths PathSet(u, v)={P(u, v)|u∈V, v∈V} is a set of all connected paths between the node pair u and v, representing the indirect connection between node v and node u Depends on semantics.

In ProvGraph, if ent ₁ , ent ₂ , ent ₃ ∈ Entity, act ₁ , act ₂ , act ₃ ∈ Activity, ag ₁ , ag ₂ ∈ Agent, then the following theorem expresses the transitivity and reliability of related origin dependencies Reasonable:

Theorem 1 The Attribution relation is deducible:

(1) The agent ag ₁ responsible for the activity act ₁ is responsible for the entity ent ₁ generated by the activity; that is, if <ag ₁ ,act ₁ >∈E and <act ₁ ,ent ₁ >∈E, then <ag ₁ ,ent ₁ >established;

(2) The superior agent ag ₁ responsible for the agent ag ₂ is responsible for the entity ent ₁ responsible for the agent; that is, if <ag ₁ , ag ₂ >∈E and <ag ₂ , ent ₁ >∈E, then <ag ₁ , ent ₁ > established.

Theorem 2 Association relation is deducible:

The superior agent ag ₁ responsible for the agent ag ₂ is responsible for the activity act ₁ that the agent is responsible for; that is, if <ag ₁ , ag ₂ >∈E and <ag ₂ , act ₁ >∈E, then <ag ₁ , act ₁ > established.

Theorem 3Communication relation is deducible:

An entity ent ₁ generated by activity act ₁ is a necessary condition for the start of activity act ₂ and subsequent generation of other entities, which means that there is a communication relationship between these two entities; that is, if <act ₁ , ent ₁ >∈E and <ent ₁ , act ₂ >∈E, then <act ₁ , act ₂ > holds.

Theorem 4Communication relationship is transitive:

There is a communication relationship between act ₁ and act ₂ , and there is a communication relationship between act ₂ and act ₃ , so there is also a communication relationship between act ₃ and act ₁ ; that is, if <act ₁ , act ₂ >∈E And <act ₂ , act ₃ >∈E, then <act ₁ , act ₃ > holds.

Theorem 5Delegation relationship is transitive:

The superior agent of agent ag ₂ is ag ₁ , and the superior agent of ag ₃ is ag ₂ , then it can be said that ag ₁ is the superior agent of ag ₃ ; that is, if <ag ₁ , ag ₂ >∈E and <ag ₂ , ag ₃ >∈E, then <ag ₁ , ag ₃ > holds.

Theorem 6Derivation relation is transitive:

If entity ent ₁ is derived from entity ent ₂ , and entity ent ₂ is derived from entity ent ₃ , then to a certain extent, ent ₁ can be considered to be derived from ent ₃ ; that is, if <ent ₃ , ent ₂ >∈ E and <ent ₂ , ent ₁ >∈E, then <ent ₃ , ent ₁ > holds.

In order to express the filtering operation accurately, the basic operation of origin filtering is defined below.

Definition 5 Basic operation of origin filtering:

(1) GetNumVex(ProvGraph): Get the number of ProvGraph nodes in the origin graph;

(2) GetNumVexPair(ProvGraph): Get the number of connected node pairs in ProvGraph;

(3) GetPre(v): Get the direct antecedent node set of node v, if u∈GetPre(v), then there is e=<u, v>∈E, that is, u is one of the direct causes of v;

(3) GetSub(v): Get the direct consequence node set of node v, if u∈GetSub(v), then there is an edge e=<v, u>∈E, that is, u is one of the direct consequences of the occurrence of v;

(4) GetPreAct(v): Get the nearest antecedent activity node set of node v, if u∈GetPreAct(v), then there is P(u, v)∈PathSet(u, v), u is the closest direct path to v Or an indirect antecedent active node, that is, any s∈P(u, v), if s≠u and s≠v, then τ(s)≠AC;

(5) GetSubAct(v): Get the nearest consequence activity node set of node v, if u∈GetSubAct(v), then there is P(v,u)∈PathSet(u,v), u is the closest direct or Indirect consequence active node, that is, any s∈P(v,u), if s≠u and s≠v, then τ(s)≠AC;

(6) AddEdge(u, v): add edge e=<u, v>;

(7) DeleteVex(v): delete node v;

(8) DeleteEdge(u, v): delete edge e=<u, v>.

A high-efficiency origin filtering method with customizable dependency semantics of the present invention processes directed acyclic origin graphs conforming to the origin standard model and its constraints, and filters according to the proposed origin according to the filtering requirements including nodes to be filtered and node pairs The filtering rules and repairing rules in the mechanism process the provenance graph, and finally the proposed provenance filtering view evaluation model is used to evaluate the effectiveness of the filtering view and generate the provenance filtering report.

Step 1: Check the origin data to be filtered to ensure that it is a directed acyclic graph conforming to the standardized origin model and its model constraints.

Model Constraint 1: There are no separate activities and agents in origin;

Model Constraint 2: An entity cannot be produced by more than two activities;

Model constraint 3: When a direct dependency can be deduced from other direct dependencies, the corresponding edge should be omitted in the origin graph;

Model constraint 4: The origin graph cannot contain a cycle, and the topological sorting algorithm can be used to detect whether there is a cycle in the origin graph.

Step 2: Declare origin filtering requirements, that is, origin elements to be filtered, direct and indirect origin dependencies; among them, origin elements are represented by nodes in the origin graph, and direct or indirect dependencies are represented by node pairs in the origin graph.

When declaring filtering requirements, you should pay attention to: (1) When declaring the source element, you need to specify the identifier or some attributes of the element (attributes). When the element type is an activity, you can also indicate the start and end time of the activity (startTime and endTime); ( 2) When declaring the source dependency, regardless of the direct dependency or the indirect dependency, it is necessary to specify the identifiers or partial attributes of the two source elements to which the dependency is attached.

Step 3: Process the nodes and node pairs to be filtered according to the following filtering rules and repairing rules.

The method of the present invention sequentially processes the objects to be filtered according to the order of elements, direct dependencies, and indirect dependencies, ie, nodes, edges, and paths. The specific process is shown in FIG. 2 .

First, take the node v to be filtered in turn, judge the type of node v and its direct cause node and direct consequence node, select and apply appropriate filtering and repair rules to delete node v and the edges related to node v, and repair the damaged Origin dependencies, update the origin graph; different node types, corresponding filtering and repair rules are also different: when the node type is entity (EN), the rules are shown in Table 1; when the node type is activity (AC), the rules are as follows Table 2; when the node type is agent (AG), the rules are shown in Table 3. Among them, sv ∈ GetSub(v) represents the immediate consequence node of v, pv ∈ GetPre(v) represents the direct cause node of v, sav ∈ GetSubAct(v) represents the nearest consequence activity node of v, and pav ∈ GetPreAct(v) represents The most recent antecedent active node of v, "—" in the table indicates that the situation is not used or cannot be repaired. Among them, the visual schematic diagram of entity class filtering rules and repair rules is shown in Figure 3, the visual schematic diagram of activity class node filtering rules and repair rules is shown in Figure 4, and the visual schematic diagram of agent class node filtering rules and repair rules is shown in Figure 5 Show.

Table 1 Filtering and repairing rules of entity node v

Table 2 Filtering and repairing rules of active node v

Table 3 Filtering and repairing rules of proxy node v

Then, take the node pair (u, v) to be filtered in turn, check whether the two points exist and are connected in the current origin graph, if they do not exist or are not connected, no processing is required; if the two points exist and are connected, judge whether u and v If they are not adjacent, they are marked as connected path node pairs to be filtered, otherwise, delete the edge between u and v, and judge the types of u and v, as well as the direct cause node of u and the direct consequence node type of v, Select the appropriate repair operation in the dependency repair rules, repair the damaged origin dependencies, and update the origin graph. The restoration rules are shown in Table 4 and Table 5, where sv ∈ GetSub(v) represents the immediate consequence node of v, pu ∈ GetPre(u) represents the immediate cause node of u, and sav ∈ GetSubAct(v) represents the nearest Consequence activity node, pau∈GetPreAct(u) means u's recent antecedent activity node, "—" in the table means that the situation does not need to be repaired or cannot be repaired, and "×" means that the situation does not exist.

Table 4 Repair rules for edge (u, v) and path p(u, v)

Table 5 Repair rules for edge (u, v) and path p(u, v)

Finally, take the node pair (u, v) of the connected path to be filtered in turn, traverse the origin graph, and obtain the connected path p between u and v in turn, and use the minimum cost decision method to filter the path p, that is, calculate and delete through the cost function The filter cost and repair cost sum of each edge on the path p, select and delete the edge <s, t> with the smallest total cost; according to the types of u and v and the direct cause node of u and the direct consequence node of v type, select and apply appropriate repair rules, and repair the damaged origin indirect dependencies; if the direct cause node of s and the direct consequence node of t are not on the path p at the same time, then it must also be based on the types of s and t As well as the type of the immediate cause node of s and the immediate consequence node of t, an appropriate repair rule is selected and applied to repair the broken origin graph. The repair rules are shown in Table 4 and Table 5.

In the minimum cost decision-making method, the filtering cost is the reduction rate of connected node logarithms in the origin filter view, and the restoration cost is estimated as the ratio of the connected node logarithms of path changes after repairing. Let the logarithm of connected nodes in the original source graph be VP, the logarithm of connected nodes in the filter view be VP _S , and the logarithm of connected nodes whose paths change in the filter view be VP _SC , then the filtering cost The algorithm of the minimum cost decision-making method to filter the connected path between the node pair (u, v) is as follows:

Step 4: Arrange and update the origin graph according to the following arrangement rules to obtain the origin filter view.

Further organize the obtained filtered view: (1) check the proxy node and active node in the origin graph, and delete the node if it is independent; (2) check the edge in the origin graph, if one of the vertices attached to the edge has been deleted , then delete the edge; (3) check the edge in the origin graph, if the dependency represented by the edge can be deduced from other edges, delete the edge; (4) update the origin graph to obtain the final origin filter view.

Step 5: Quantitatively evaluate the effectiveness of the origin filtering view according to the following origin filtering view evaluation model, and generate an origin filtering report.

First, utility evaluation is performed on the origin filtered view obtained in the previous step. Among them, the evaluation calculation value includes: (1) the retention rate of nodes in the filter view except for the nodes to be filtered; (2) the retention rate of edges in the filter view except for the edges to be filtered; In addition to path node pairs, the retention rate of connected path node pairs in the filter view; (4) the ratio of the number of connected node pairs with unchanged paths to the total number of connected node pairs in the filter view; (5) according to the importance of each origin graph structure assign weights ω ₁ , ω ₂ , ω ₃ , ω ₄ to (1)(2)(3)(4) respectively, where ω ₁ +ω ₂ +ω ₃ +ω ₄ =100%.

Suppose the number of nodes to be filtered is V _R , the number of edges is E _R , the number of connected paths is _VPR , the number of nodes in the original source graph is V, the number of edges E, and the number of connected paths are VP, and the number of nodes in the filter view is V _S , the number of edges is E _S , the number of connected paths is _{VPS , and the logarithm of connected nodes with path changes is VP SC ,} then the calculation formula of origin filter view utility is as follows:

The origin original image in the embodiment conforms to the standardized origin model PROV-DM, as shown in FIG. 6 . Declare two different security requirements:

R ₁ : the nodes to be filtered include E ₂ , Act ₃ , Ag ₁ , and the node pairs to be filtered include (E ₁ , Act ₁ );

R ₂ : the nodes to be filtered include E ₂ and Ag ₁ , and the node pairs to be filtered include (E ₃ , E ₅ ).

Using the proposed origin filtering mechanism to process the origin graph shown in Figure 6, the origin filtering view obtained by realizing requirement R ₁ is shown in Figure 7, and the origin filtering view obtained by realizing requirement R ₂ is shown in Figure 9. As a comparison of experimental results, an existing origin filtering method is selected to filter the origin graph 6 to realize the filtering requirement R ₁ , and the obtained origin filtering view is shown in FIG. 8 .

Use the origin filter view evaluation model to perform quantitative evaluation of the effectiveness of each origin filter view in the embodiment. In order to ensure comparability, each origin view is assigned a value of ω ₁ = ω ₂ = ω ₃ = 30%, ω ₄ = 10%. It needs to be pointed out Yes, other assignment combinations for ω ₁ , ω ₂ , ω ₃ , and ω ₄ also fall within the scope of this patent.

The source filter view utility shown in Figure 8 is 65.78%; the source filter view utility shown in Figure 7 is 81.04%, compared with the source filter view shown in Figure 8, the utility has improved by 15.26%, illustrating the source filter of the present invention Compared with other methods, the effectiveness of the origin filtering view is significantly improved; the origin filtering view shown in Figure 9 has an effectiveness of 81.11%, which shows that the origin filtering method of the present invention can not only handle complex origin dependencies, but also ensure a relatively high utility.

Finally, summarize the content related to origin filtering, and generate an origin filtering report, which includes the original origin map, filtering requirements, origin filtering view, satisfaction of filtering requirements, multi-filtering origin elements and dependencies, and repairing origin dependency semantics. Changed reasonable origin dependencies, utility evaluation values for origin filter views. Table 6 shows the report of the source filtering view shown in FIG. 9 obtained from FIG. 6 in the embodiment.

Table 6 Origin Filtering Report Summary Table

Claims (9)

1. a kind of customizable effective origin filter method for relying on semanteme, it is characterised in that comprise the following steps：

Step 1：Check provenance graph to be filtered, it is ensured that it is to meet the directed acyclic for having standardized source model and its model constraint Figure；

Step 2：Statement origin filtration needs, i.e., to be filtered plays source element, the direct and dependence that originates from indirectly；Wherein, mistake The source element that rises to be filtered is represented with the node in provenance graph in filter demand, direct or indirect dependence to be filtered in filtration needs Node in relation provenance graph is to representing；

Step 3：To be filtered playing source element and rely on is handled according to the filtering rule and reparation rule in the strobe utility of origin to close System；

Step 4：Arranged according to the arrangement rule in the strobe utility of origin and update the result of step 3, obtain origin filtering View；

Step 5：The effectiveness of origin filtered view, generation origin filtering report are quantitatively assessed according to origin filtered view assessment models Accuse.

2. customizable according to claim 1 rely on semantic effective origin filter method, it is characterised in that the origin Figure has retrospective dependence semantic, i.e. if arbitrary node v can trace back to another node u, u is the part cause that v occurs In provenance graph, each node v represents that is played a source element, and according to the type for playing source element, origin element set is divided into three Individual mutually disjoint subset：In entity set, active set and agency's collection, the entity set, an entity node describes some data Object is gone in the state at some period or time point, the active set, and an active node represents to make within a period of time With the process on entity node or the sequence of operations that state can be caused to change, the agency concentrates, an agency Node is expressed as a movable generation, the presence or another activity acted on behalf of of an entity and undertakes the agent of certain responsibility Or tissue；

The relation that directly relies on is expressed as follows：

If v is u direct result, u is v direct cause, is designated as<U, v>, claim v to u's to directly rely on relation, or v direct Dependent on u, directly relying on relation includes such as Types Below：

(1) Usage (using relying on)：Active node uses entity node；

(2) Generation (producing dependence), entity node is produced by active node；

(3) Association (association is relied on), agent node is undertaken the responsibility in active node；

(4) Attribution (ownership is relied on), agent node is undertaken the responsibility to entity node；

(5) Derivation (derive from and rely on), certain entity node is derived from by another entity node；

(6) Communication (communication is relied on), certain active node v communications depend on another active node u, v to use u institutes Some entity node produced；

(7) Delegation (agency relies on), certain agent node represents another agent node；

The relation that indirectly relies on is expressed as follows：

If v is u indirect consequence, u is v indirect cause, then node v indirectly relies on relation to u；

By following theorem represent related origin dependence transitivity and can be inferential：

(1) entity node one for being responsible for a pair of activities of agent node generation of active node one is responsible for, i.e. a pair of entity node The ownership dependence of agent node one has can be inferential；

(2) entity node one that a pair of the agencies of superior agency node for being responsible for agent node two are responsible for is responsible for, i.e. entity node The ownership dependence of a pair of agent nodes one has can be inferential；

(3) active node one that a pair of the agencies of superior agency node for being responsible for agent node two are responsible for is responsible for, i.e. active node The association dependence of a pair of agent nodes one has can be inferential；

(4) some entity node one that active node one is produced is that active node two starts and then produces necessity of other entities Condition, then the communication of active node two is dependent on the communication dependence of active node one, i.e. active node two to active node one With can be inferential；

(5) communication of active node one depends on active node two, and the communication of active node two depends on active node three, then active section The communication of point one has transitivity dependent on the communication dependence between active node three, i.e. active node；

(6) agent node three represents superior agency node two, and agent node two represents its higher level's agent node one, then agent node Three dependences of acting on behalf of that can be represented to a certain extent between superior agency node one, i.e. agent node have transitivity；

(7) if entity node one, which derives from, depends on entity node two, entity node two, which derives from, depends on entity node three, then entity Node one derives from has transitivity dependent on the derivation dependence between entity node three, i.e. entity node.

3. customizable according to claim 1 rely on semantic effective origin filter method, it is characterised in that the step 3, filtering order for represent the node of element, represent to directly rely on the node of relation to, represent to indirectly rely on the node pair of relation, According to filtering object type and its directly before because the type combination of node and direct result node is selected and is filtered and is repaiied Multiple operation.

4. customizable according to claim 1 rely on semantic effective origin filter method, it is characterised in that the step 3, handle rise source element and dependence to be filtered and include following sub-step：

Step 31：Take node v to be filtered successively, and according to the node and its directly before because of the class of node and direct result node Type, chooses and application filtering and reparation rule, deletion of node and the side related to node, and the destroyed origin of reparation, which is relied on, closes System, updates provenance graph；

Step 32：Take undressed node pair to be filtered<U, v>, if entering step 34 without if, otherwise check that u, 2 points of v are rising It whether there is and connect in the figure of source, without processing if being not present or not connecting；Determined whether if existing and connect if 2 points Whether u, v are adjacent, and step 33 is entered if the two is adjacent, otherwise labeled as communication path node pair to be filtered, step 32 is returned to；

Step 33：Delete the side between u, v, and type according to 2 points of u, v and u it is direct before because node and v it is direct after The type of fruit node, chooses and applies reparation rule, repairs destroyed origin dependence, updates provenance graph, return to step 32；

Step 34：Communication path node pair to be filtered is taken successively<U, v>, the communication path p between u, v is obtained successively, using most The method filtering p of small cost decision-making, i.e., calculated the filtering cost of each edge on the p of path and repair cost respectively by cost function With the minimum side of the total cost Cost values of deletion<S, t>；According to 2 points of u, v type and u it is direct before it is straight because of node and v The type of consequence node is connect, chooses and applies reparation rule, destroyed origin is repaired and indirectly relies on relation；If s it is direct before Because when node is different with t direct result node on the p of path, then must also be according to 2 points of s, t type and s direct cause The type of node and t direct result node, selects and applies reparation rule, repairs destroyed provenance graph.

5. customizable according to claim 4 rely on semantic effective origin filter method, it is characterised in that the cost Function is：Wherein VP is the connection node logarithm in former provenance graph, VP_SFor the company in filtered view Logical node logarithm, VP_SCFor the connection node logarithm of path change in filtered view.

6. customizable according to claim 4 rely on semantic effective origin filter method, it is characterised in that described all kinds of Filtering and reparation rule are：

Entity class node is filtered and reparation rule is as follows：

(1) when before directly because node is empty and direct result node is entity class or activity class when, filtering rule：Delete the node And its side between direct result node；The situation is without repairing；

(2) when direct result node be it is empty and directly before because node be entity class, activity class or proxy class when, filtering rule：Delete Except the node and its with directly before because of the side between node；The situation is without repairing；

(3) when before directly because node is proxy class and direct result node is entity class or activity class when, filtering rule：Deleting should Node and its with directly before because of the side between node and direct result node；The situation can not be repaired；

(4) when before directly because node is entity class and direct result node is activity class when, filtering rule：Delete the node and with It is directly preceding because of the side between node and direct result node；Reparation rule：Because of node before being searched directly first in provenance graph It is nearest before because of active node, if increasing direct result node in the presence of if to preceding because of the communication dependence of active node recently；

(5) when before directly because node is activity class and direct result node is entity class when, filtering rule：Delete the node and its With directly before because of the side between node and direct result node；Reparation rule：Direct result node is searched first in provenance graph Nearest consequence active node, if increase in the presence of if nearest consequence active node to directly before because of the communication dependence of node；

(6) when because of node and direct result node being all activity class before directly, filtering rule：Delete the node and its with it is direct The preceding side because between node and direct result node；Reparation rule：Increase from direct result node to directly preceding leading to because of node Believe dependence；

(7) when because of node and direct result node being all entity class before directly, filtering rule：Delete the node and its with it is direct The preceding side because between node and direct result node；Reparation rule：Increase from direct result node to directly before because of the group of node Raw dependence；

Activity class node is filtered and reparation rule is as follows：

(1) when before directly because node is empty and direct result node is entity class or activity class when, filtering rule：Delete the node And its side between direct result node；The situation is without repairing；

(2) when direct result node be it is empty and directly before because node be entity class, activity class or proxy class when, filtering rule：Delete Except the node and its with directly before because of the side between node；The situation is without repairing；

(3) when directly before because node be agency and direct result node be activity class when, filtering rule：Delete the node and its with Because of the side between node and direct result node before directly；The situation can not be repaired；

(4) when directly before because node be agency and direct result node be entity class when, filtering rule：Delete the node and its with Because of the side between node and direct result node before directly；Reparation rule：Increase direct result node to directly preceding because of node Belong to dependence；

(5) when before directly because node is entity class and direct result node is activity class when, filtering rule：Delete the node and its With directly before because of the side between node and direct result node；Reparation rule：Because of node before being searched directly first in provenance graph It is nearest before because of active node, if increasing in the presence of if from direct result node to being closed because the communication of active node is relied on before recently System；

(6) when before directly because node is activity class and direct result node is entity class when, filtering rule：Delete the node and its With directly before because of the side between node and direct result node；Reparation rule：Direct result node is searched first in provenance graph Nearest consequence active node, if increase in the presence of if from nearest consequence active node to directly before because node communication rely on close System；

(7) when because of node and direct result node being all activity class before directly, filtering rule：Delete the node and its with it is direct The preceding side because between node and direct result node；Reparation rule：Increase from direct result node to directly preceding leading to because of node Believe dependence；

(8) when because of node and direct result node being all entity class before directly, filtering rule：Delete the node and its with it is direct The preceding side because between node and direct result node；Reparation rule need to divide situation discussion：Depended on when direct result node derives from When before directly because of node, without repairing；Otherwise in provenance graph respectively search directly before because node it is nearest before because of active node And the nearest consequence active node of direct result node, if exist if increase from nearest consequence node to recently before because of node Communication dependence；

Proxy class node is filtered and reparation rule is as follows：

(1) when before directly because node is empty and direct result node is entity class, activity class or proxy class when, filtering rule：Delete Except the node and its side between direct result node；The situation is without repairing；

(2) when direct result node be it is empty and directly before because node be proxy class when, filtering rule：Delete the node and its with it is straight Connect the side between consequence node；The situation is without repairing；

(3) when before directly because node is proxy class and direct result node is proxy class when, filtering rule：Delete the node and its With the side between direct result node；Reparation rule：Increase to rely on from direct result node to the directly preceding agency because of node and close System；

(4) when before directly because node is proxy class and direct result node is entity class when, filtering rule：Delete the node and its With the side between direct result node；Reparation rule：Increase direct result node to directly preceding because of the ownership dependence of node；

(5) when before directly because node is proxy class and direct result node is activity class when, filtering rule：Delete the node and its With the side between direct result node；Reparation rule：Increase direct result node to directly preceding because of the association dependence of node；

Delete Usage classes side<U, v>Available origin dependence reparation rule is as follows afterwards：

(1) when u it is direct before because node be empty or during proxy class, the situation can not be repaired；

(2) when u it is direct before because node be entity class when, first in provenance graph u it is direct before because node nearest cause live Dynamic node, it is preceding because of the communication dependence of active node recently from v to this if increasing in the presence of if；

(3) when u it is direct before because node be activity class when, then increase before direct from v to u because of the communication dependence of node；

Delete Generation classes side<U, v>Available origin dependence reparation rule is as follows afterwards：

(1) when u it is direct before because node be proxy class when, then can increase before direct from v to u and to be closed because the ownership of node is relied on System；

(2) when v direct result node is empty and u it is direct before because node be not proxy class when, it is impossible to repair；

(3) when v direct result node is entity class, v nearest consequence active node is searched first in provenance graph, if depositing Then increasing from the node to the communication dependence u；

(4) when v direct result node is activity class, then the communication dependence from the node to u is increased；

Delete Derivation classes side<U, v>Available origin dependence reparation rule is as follows afterwards：

(1) when u it is direct before because node be empty or during proxy class, the situation can not be repaired；

(2) u it is direct before because direct result node that node is activity class and v be entity class when, v is searched in provenance graph first Nearest consequence active node, if increasing in the presence of if before direct from the node to u because of the communication dependence of node；

(3) when u it is direct before because direct result node that node is entity class and v be activity class when, looked into first in provenance graph Look for u it is nearest before because of active node, if increasing in the presence of if from v direct result node to the communication dependence of the node；

(4) when u it is direct before because the direct result node of node and v be all entity class when, first in provenance graph search u most Nearby because of active node and v nearest consequence active node, increase if existing from nearest consequence active node to most nearby Because of the communication dependence of active node；

(5) when u it is direct before because the direct result node of node and v be all activity class when, then increase the direct result node from v To the direct preceding because of the communication dependence of node of u；

Delete Communication classes side<U, v>Available origin dependence reparation rule is as follows afterwards：

(1) when u it is direct before because node be empty or during proxy class, the situation can not be repaired；

(2) when u it is direct before because direct result node that node is entity class and v be activity class when, then increase from v it is direct after Communication dependence of the fruit node to u；

(3) when u it is direct before because direct result node that node is activity class and v be entity class when, then increase straight from v to u Because of the communication dependence of node before connecing；

(4) when u it is direct before because the direct result node of node and v is all entity class when have two kinds of optional reparation rules：The It is a kind of that the nearest preceding because of active node of u is searched first in provenance graph, rely on pass if increasing the communication from v to the node in the presence of if System；The nearest consequence active node for first looking for v second, if increasing the communication dependence from the node to u in the presence of if；

(5) when u it is direct before because the direct result node of node and v is all activity class when have two kinds of optional reparation rules：The A kind of increase is direct preceding because of the communication dependence of node from v to u；Second of increase is from v direct result node to the logical of u Believe dependence；

Delete Association classes side<U, v>Available origin dependence reparation rule is as follows afterwards：

(1) when v direct result node is space-time, the situation can not be repaired；

(2) when v direct result node is entity class, increase from v direct result node to u ownership dependence；

(3) when u it is direct before because direct result node that node is proxy class and v be activity class when, increase direct from v to u It is preceding because of the association dependence of node；

Delete Attribution classes side<U, v>Available origin dependence reparation rule is as follows afterwards：

(1) when u it is direct before because node be proxy class when, because of the ownership dependence of node before direct from v to u of increase；

Delete Delegation classes side<U, v>Available origin dependence reparation rule is as follows afterwards：

(1) when u it is direct before because the direct result node of node and v be all space-time, the situation can not be repaired；

(2) when u it is direct before because node be empty or when proxy class and v direct result node are entity class, increase is from the direct of v Ownership dependence of the consequence node to u；

(3) when u it is direct before because node be empty or when proxy class and v direct result node are activity classes, increase is from the direct of v Association dependence of the consequence node to u；

(4) when u it is direct before because node be empty and when v direct result node is proxy class, increase the direct result node from v Dependence is acted on behalf of to u；

(5) when u it is direct before because direct result node that node is proxy class and v be proxy class when, have two kinds of optional reparations Rule：The first increase acts on behalf of dependence from v direct result node to u；Direct cause of second of increase from v to u Node acts on behalf of dependence.

7. customizable according to claim 1 rely on semantic effective origin filter method, it is characterised in that the step 4, according to arrangement rule arrange step 3 obtained by provenance graph, obtain origin filtered view include following sub-step：

Step 41：The proxy class node and activity class node in provenance graph are checked, is deleted if node disjoint；

Step 42：The side in provenance graph is checked, if one of summit that side is depended on has been deleted, the side is deleted；

Step 43：Check provenance graph in side, if the dependence represented by can by it is other while reasoning obtain, delete should Side；

Step 44：Provenance graph is updated, final origin filtered view is obtained.

8. customizable according to claim 1 rely on semantic effective origin filter method, it is characterised in that the step 5, the filtering report of generation origin includes following sub-step：

Step 51：Calculate nodes V to be filtered_R, side number E to be filtered_R, communication path number VP to be filtered_R；

Step 52：Extreme saturation original provenance graph, calculates total node number V, side number E, communication path number VP；

Step 53：Extreme saturation origin filtered view, calculates the nodes V retained after filtering_S, side number E_S, communication path number VP_S、 The connection node logarithm VP of path change compared with former provenance graph_SC；

Step 54：Calculate the effect assessment value of origin filtered view：

Wherein, ω₁、ω₂、ω₃、ω₄Point 30%, 30%, 30%, 10% is not entered as；It should be noted that according to demand, ω₁、ω₂、ω₃、ω₄Assignment may be selected Other combinations, but ω need to be met₁+ω₂+ω₃+ω₄=100%；

Step 55：The filtering report of generation origin.

9. customizable according to claim 8 rely on semantic effective origin filter method, it is characterised in that the origin Filtering report content includes original provenance graph, filtration needs, origin filtered view, filtration needs and meets situation, filters more Rise source element and dependence, for repair origin rely on it is semantic changes can reasoning originate from dependence and the filtering that originates from is regarded The value of utility of figure.