CN102073583A - Method for checking software package dependency relationship based on dependency - Google Patents

Abstract

The invention provides a method for checking the software package dependency relationship based on dependence, which comprises the following steps: reading dependency information from a software package dependency relationship description file, and generating a software package dependency relationship tree; converting the software package dependency relationship tree into a corresponding conjunctive normal form (CNF); and taking the CNF describing the dependency relationship as the input of an algorithm for solving the a satisfiability (SAT) problem, wherein a calculated result is a solution to judge whether software can be installed. The method looks on the software package dependency relationship management of Linux distribution ends, which can be used to check the SAT for the software package dependency relationship of the Linux distribution ends, improve the efficiency of the software package dependency relationship management, and reduce the complexity of the dependency relationship management among the software packages.

Description

Dependency-Based Package Dependency Checking Method

technical field

The invention relates to the technical field of software package management, in particular to a method for checking the satisfiability of software package dependencies under Linux, which is applicable to a Linux distribution terminal.

Background technique

The current tools or methods for managing complex dependencies between software packages are mainly divided into two types in terms of usage: client-based package dependency management tools and distribution-based package dependency management tools. In terms of client-side package dependency management tools, usually Linux distributions provide client-side dependency management tools to support client-side package management, such as apt-get of Debian Linux, yum of RedHatLinux, red carpet of Suse Linux, etc., and some researchers Aiming at the incompleteness of apt-get and yum, research has resulted in optimized or better-performing client package management tools, such as Smart and Optimal. In terms of distribution-side package dependency management tools, there are currently no related tools, and most of them are reused client-side package management tools, which are further managed by maintainers. However, as the scale of the distribution end continues to expand, the existing software package management tools cannot complete the integrity check of the software package dependencies at the distribution end, and the workload of maintenance personnel is increasing.

Therefore, with the continuous expansion and growth of Linux functions, how to effectively maintain the dependencies between a large number of software packages is a common challenge faced by all Linux operating system manufacturers: whether the new software package is compatible with the original software package set Conflicts between packages? Do all packages that the new package depends on exist in the original package collection? When a package in the original package collection gets updated, do the original dependencies persist, or do they cause conflicts? When a package in the original package collection is deleted or deprecated, can the original dependency still be maintained, or need to be readjusted, or cause the local dependency chain to be broken? According to the special needs of industry users, how to quickly formulate a dedicated Linux operating system release version, which only includes the required software packages? And when the user installs, uninstalls, and updates the software package, the updating and maintenance of the dependencies of the package set should be transparent to the user.

The solution to these problems can be boiled down to: in a set of software packages, is any package dependency satisfiable?

Contents of the invention

In view of this, the main purpose of the present invention is to solve the above problems, reduce the work intensity of maintenance personnel, improve the automation of software package management at the distribution end, and provide a method for checking software package dependencies based on dependencies. The technical problem to be solved is how Check the satisfiability of the dependency relationship of the Linux distribution terminal software package, so that it can determine the installation problem of the Linux distribution terminal software package, improve the efficiency of software package dependency management, and reduce the complexity of dependency management between software packages.

For above-mentioned technical problem, the present invention solves like this. Dependency-based software package dependency inspection method, comprising the following steps: Step 10: Read dependency information from the software package dependency description file graphml.xml and generate a software package dependency tree; Step 20: Convert the dependency tree into CNF paradigm; step 30: use the CNF paradigm file describing the dependency as the input of the SAT problem solving algorithm, and the calculation result is the solution of whether the software can be installed.

According to the analysis of the software package installability, when each software package in the distribution version or distribution pool package base R is satisfiable, that is, it is all installable, the dependency integrity check on the package base, that is, the composition Each package in the package base is evaluated for installability. Through the above steps, the software package installability decision problem can be mapped to a classical Boolean satisfiable problem. Boolean satisfiable (SAT) problem is a typical NP-complete problem. The installability determination problem has a solution if and only if its corresponding SAT problem has a solution, and the solution of the dependent subset of each software package in the software package set (referred to as the package base) is a search problem of the solution space of the corresponding SAT problem . Using the solution of the Boolean satisfiability problem, it is possible to find unsatisfiable dependent software packages, and further determine the completeness of the software package dependencies in the distribution pool.

The purpose of the present invention and its technical problems can also be further realized by adopting the following technical measures.

The aforementioned dependency-based software package dependency checking method, wherein the software package dependency description file graphml.xml in step 10 is a software package obtained according to the patent application "A Modeling Method for Software Package Dependency" A dependency description file, which is described in an extended GraphML file format.

"A Method for Modeling Software Package Dependency", its steps include:

The first step is to analyze the dependencies in the software package and express it as a unified software package metadata format Package format. This step can be subdivided into the following three small steps. According to various Linux software package formats, from the perspective of dependency modeling , propose a unified software package metadata format Package format and its XML representation method; according to the input package format, read the package file or description file of the package base in this package format, parse and extract The dependency information of the software package metadata; the obtained dependency information is converted into the package format of the unified software package metadata format, and expressed in XML as the package base description file described by the unified software package metadata.

The second step is to describe and visualize the dependencies expressed in the unified package metadata format Package format with the extended GraphML language. This step can be subdivided into the following three small steps: Based on the package base modeling requirements, the GraphML Extend to get the extended GraphML format; convert the Package structure into an extended GraphML file format description to generate a graphmlxml file; read graphml.xml and visualize it.

Among them, the unified software package metadata format is proposed from the perspective of dependency modeling, which only contains the necessary information required for dependency modeling, and its definition is shown in Table 1; the extended GraphML is based on GraphML, through the It is extended by adding attributes to its elements and adding content of <data> elements. Figure 2 shows the extended GraphML format.

Table 1 Definition of unified software package metadata format

The aforementioned dependent-based software package dependency checking method, wherein said step 10 further includes: Step 101: reading dependency information from the software package dependency description file graphml.xml; Step 102: selecting from the software package collection A software package; Step 103: Generate a dependency tree according to the selected software package and the read dependency information.

Compared with the prior art, the present invention has obvious advantages and beneficial effects. By means of the above technical solution, the dependency-based software package dependency checking method of the present invention has the following advantages and beneficial effects:

1. In the present invention, the algorithm for converting the dependency tree into the CNF paradigm adopts an incomplete algorithm, which will give up converting a large amount of redundant dependencies, and the space occupied by the program will be within a controllable range, and there is no limit to the number of software packages.

2. The DPLL complete algorithm can prove the unsatisfiability of the satisfiability (SAT) problem, so when checking the software package dependencies, it can accurately find the unsatisfiable software packages. When no software package with unsatisfiable dependencies is found in the distribution pool, it can be judged that the distribution pool has complete dependencies.

3. The present invention can well check the integrity of the distribution pool in the DEB package format, and can also perform integrity check on the distribution pool in the RPM package format.

To sum up, the present invention has the above advantages and beneficial effects, has great improvement in method and function, has significant progress in technology, and has wide application value in industry.

The above description is only an overview of the technical solution of the present invention. In order to better understand the technical means of the present invention, it can be implemented according to the contents of the description, and in order to make the above and other purposes, features and advantages of the present invention more obvious and understandable , the following preferred embodiments are specifically cited below, and are described in detail as follows in conjunction with the accompanying drawings.

Description of drawings

FIG. 1 is a flow chart of a dependency-based software package dependency checking method.

Figure 2 is the extended GraphML format.

Fig. 3 is an "and-or graph" of inter-package dependencies of a package base composed of nine software packages.

Fig. 4 is a flow chart of dependency tree transformation to CNF paradigm.

Detailed ways

In order to further explain the technical means and effects of the present invention to achieve the intended purpose of the invention, the specific implementation methods, methods, Steps, structures, features and effects thereof are described in detail below.

The aforementioned and other technical contents, features and effects of the present invention will be clearly presented in the following detailed description with reference to the drawings. Through the description of specific embodiments, the technical means and effects of the present invention to achieve the intended purpose can be understood more deeply and specifically. However, the accompanying drawings are only for reference and description, and are not used to explain the present invention. be restricted.

In order to better understand the content of the present invention, some related concepts are given below:

A Formal Representation of Package Direct Dependency Constraints

，其中，集合D(p)的元素y为软件包或软件包析取组合(p_i∨...∨p_j)。如果p与其它软件包不存在依赖或冲突，则

直接依赖集合D的λ赋值D^λ(P)，表示对集合中析取式的一次赋值。即对D中每一析取组合，选取其中的某一软件包表示该组合，赋值后，D^λ(P)为p的一个直接依赖软件包集合。Let D _r and D _c be the dependent and conflicting software package sets of p respectively, and the direct dependent set

, where the element y of the set D(p) is a software package or a disjunctive combination of software packages (p _i ∨...∨p _j ). If p has no dependencies or conflicts with other packages, then

The λ assignment D ^λ (P) directly dependent on the set D represents an assignment to a disjunction in the set. That is, for each disjunctive combination in D, select one of the software packages to represent the combination. After assignment, D ^λ (P) is a set of directly dependent software packages of p.

Package dependency satisfiability

中任一软件包x，使得

，

For a set of software packages R, the dependency satisfiability of software package p in R means that in the set of software packages R, there exists an assignment λ, D ^λ (X) is a dependency function, and D ^λ (X) is defined as the direct A collection of dependent packages. D ^nλ (p) denotes D ^λ (D ^λ (D ^λ (...(D ^λ (p)...))), for the subset

Any package x such that

,

A subset of package dependencies

According to the definition of dependency satisfiability, P determined by assignment λ is called a dependency subset of software package p, and dependency subset P is generated recursively, which is a special transitive closure. λ is the dependency satisfiability assignment relative to the entire package set R.

Installability of packages

For a package set R, given a package p, if p satisfies dependency satisfiability with respect to the package set R, then p is said to be installable on the package set R.

The software package contained in the Linux operating system in the present invention is a subset of the Linux distribution pool, and one Linux distribution pool contains one or more Linux operating systems.

为冲突关系。关系C是对称的。例如对于所有的(p₁，p₂)∈C当且仅当(p₂，p₁)∈C。对于一个Linux分发版本来说标识名相同版本号不同的软件包默认为相互冲突。例如，p₁＝(u，v₁)，p₂＝(u，v₂)，并且v₁≠v₂，则(p₁，p₂)∈C。Linux distribution pool/operating system package set R=(P, D, C). Where P is a set of software packages, D:P→ψ(ψ(P)) is a dependency function, and ψ(X) represents a collection of subsets of X.

for the conflict relationship. Relationship C is symmetric. For example, for all (p ₁ , p ₂ )∈C if and only if (p ₂ , p ₁ )∈C. For a Linux distribution, packages with the same identifier but different version numbers conflict with each other by default. For example, p ₁ =(u, v ₁ ), p ₂ =(u, v ₂ ), and v ₁ ≠v ₂ , then (p ₁ , p ₂ )∈C.

Features that a Linux distribution pool/OS package set R should have:

Completeness: Every package in R is dependency-satisfiable, i.e., installable.

Software package installability determination problem

For package base R, given a package p, if p satisfies dependency satisfiability with respect to package base R, then p is said to be installable on package base R. Correspondingly, the decision problem is called software package installability decision problem.

Boolean Satisfiable (SAT) Problem (Boolean Satisfiablity Problem)

Given a Boolean function F(X): {0, 1} ⁿ →{0, 1}, find out a set of variable assignments X ^* such that F(X ^* )=1 or prove that there is no such assignment.

The software package installability determination problem can be mapped to a SAT problem, so that the installability determination problem can be solved based on SAT.

Basic mapping rules for converting package dependencies into CNF clause sets

，表示标识名称为u的软件包将以版本号v安装。R_u代表R中标识名为u的软件包的不同版本的集合。向SAT问题映射的基本规则定义如下。Boolean functions in SAT problems are usually expressed as Conjunctive Normal Form (CNF). A CNF is a set of clauses, and each clause in the set is a disjunction composed of literals or their negations. A CNF formula is said to be satisfiable if at least one set of variable assignments makes the CNF true. Define a predicate variable for each package p(u, v) in package base R

, which means that the software package with the identification name u will be installed with the version number v. R _u represents the set of different versions of the software package named u identified in R. The basic rules for mapping to SAT questions are defined below.

For the set of direct dependencies D _r ＝{p ₁ ∨...∨p _n ，...，p _j ∨...∨p _k },

Introduce predicate logic

For the direct conflict set D _c ={p ₁ ,...,p _j }, predicate logic is introduced

For the conflict relationship between software packages with the same identification name but different version numbers, for all software packages with the identification name u determined in (1) and (2), introduce

Linux package dependency tree

The Linux package dependency tree is also known as the dependency tree. The dependency relationship between the Linux operating system and the software packages on the distribution side is a directed graph, and the relationship between nodes is a dependency relationship and a conflict relationship. The "and-dependence" and "or-dependence" in the dependency-conflict relationship can use the extended "and- or" Fig. In order to better map dependencies to SAT problems, this paper defines the concept of dependent nodes, which are divided into direct dependent nodes (similar to software package b in Figure 3) and compound dependent nodes (similar to Node c or d). The relationship between dependent nodes is "and dependent".

CNF paradigm

CNF paradigm is a common input file format in SAT problem solving algorithm. The specific description is as follows:

The file can start with c, and add the description information of the file in this line.

Add a line such as "p cnf nbvar nbclauses" after the description information, indicating that the file format is CNF. Among them, nbvar represents the total number of variables appearing in the file, and nbclauses represents the factor items appearing in the file. and add the factor term after this line

Each factor item occupies a line that contains the factor to be described and ends with "0"

Specific examples are as follows:

c

c comments Max-SAT

c

p cnf 34

1-20

-1 2-3 0

-3 2 0

1 3 0

Please refer to Fig. 1, which is a flow chart of the dependency-based software package dependency inspection method proposed by the present invention, including the following steps:

Step 10: Read dependency information from the package dependency description file graphml.xml and generate a package dependency tree.

In general, dependencies between software packages can be divided into two categories: requirement dependencies and conflict dependencies. Requirement dependency is a common dependency relationship, that is, to install software package P1, software package P2 must be installed first, and P1 has a requirement dependency on P2; conflict dependency is relatively rare, and it is a negative dependency relationship, that is, software packages P1 and P2 cannot co-exist.

Read dependency information from the package dependency description file graphml.xml and generate a package dependency tree for detailed description, which includes the following three steps:

Step 101: Read dependency information from the software package dependency description file graphml.xml.

The dependency information extracted in the present invention is read from the software package dependency description file graphml.xml, wherein graphml.xml is the software obtained according to the patent invention application "A Modeling Method for Software Package Dependency" The package dependency description file is described by using the extended GraphML file, and the package dependency graph is expressed based on the extended GraphML, as shown in Figure 2. The illustration shows that the dependency graph is composed of nodes, edges and hyperedges. In the figure, the node node is used to represent the software packages that make up the package base, the edge edge represents the dependency relationship between two software packages, and the hyperedge represents the "or dependency" relationship between software packages. Each software package will have a version number (version) as an important identifier, and the format of the version number of the RPM and DEB software packages is the same. Version numbers are an important basis for identifying dependencies between software packages. Most of the dependency types described in RPM and DEB package metadata are the same, only some special-purpose dependencies are different (for example: obsoletes, replaces), and these dependencies have no impact on the package dependency integrity big. Therefore, the present invention only extracts three main dependency relationships as the basis for judging the completeness of software package dependencies. details as follows:

run (Depends relationship): Used to indicate the main dependent software package, if the current software package is to be installed or run, the software package must exist in the system.

Conflict (Conflicts relationship): It is used to indicate a software package that conflicts with the current software package. If the current software package is to be installed or run, the software package cannot exist in the system. For a software package to be installed or run, there must be no conflicting software packages in the system.

install (Pre-Depends relationship): Similar to the depends relationship, it means that the current software package must be installed or run, and the software package must exist in the system. The difference is that the software package that depends depends on may not exist when the current software package is installed. In the system, but after the installation is complete, it will be expanded to the system at the same time as the current software package; the software package that Pre-Depends depends on must already exist in the system when the current software package is installed.

The present invention uses a simplified GraphML file as a preferred embodiment, assuming that the content of graphml.xml is as follows:

<graphml>

<graph edgedefault='directed'version_type='rpm'>

<node package='a'id='a'/>

<node package='b'id='b'/>

<node package='c'id=c'/>

<node package='c'id=d'/>

<node package='c'id=e'/>

<node package='c'id=f'/>

<node package='c'id=g'/>

<node package='c'id=h'/>

<node package='c'id=i'/>

<edge type='run'source='a'target='b'/>

<edge type='run'source='b'target='f'/>

<edge type='run'source='b'target='g'/>

<edge type='run'source='c'target='g'>/

<edge type='run'source='e'target='i'/>

<edge type='conflict'source='c'target='e'/>

<edge type='conflict'source='g'target='h'/>

<hyperedge type='run'>

<endpoint type="out"node="a"/>

<endpoint type="in"node="c"/>

<endpoint type="in"node="d"/>

</hyperedge>

<hyperedge type='run'>

<endpoint type="out"node="a"/>

<endpoint type="in"node="d"/>

<endpoint type="in"node="e"/>

</hyperedge>

<hyperedge type='run'>

<endpoint type="out"node="d"/>

<endpoint type="in"node="g"/>

<endpoint type="in"node="h"/>

<endpoint type="in"node="i"/>

</hyperedge>

</graph>

</graphml>

It can be seen from the above that in order to simplify the problem, the graphml.xml file only contains 9 software package nodes, namely a, b, c, d, e, f, g, h, i, and each node element only gives the packagename Attributes, version and privade are omitted; package a depends on b, a depends on c and d, a depends on d and e, b depends on f and g, c depends on g, d depends on g, h and i , e conflicts with dependency i, c conflicts with e, and g conflicts with h.

Step 102: Select a software package from the software package collection.

Select a software package in the software package set, assuming that software package a is selected, it is necessary to determine whether the software package a can be installed is an example of a dependency-based software package dependency checking method to be described.

Step 103: Generate a dependency tree according to the selected software package and the read dependency information.

The software package dependency tree is a directed graph, and the relationship between nodes is a dependency relationship and a conflict relationship. The "and-dependence" and "or-dependence" in the dependency-conflict relationship can be represented by an extended "and-or" graph, and the extended Dashed lines indicate conflicting relationships. According to the software package a to be judged in the preferred embodiment, a total of 8 software packages directly or indirectly related to it are extracted, namely b, c, d, e, f, g, h, i. Dependency information extracted according to the preceding step 102: software package a depends on b, a depends on c and d, a depends on d and e, b depends on f and g, c depends on g, d depends on g, h and i , e conflicts with dependency i, c conflicts with e, g conflicts with h, and the generated software package dependency tree is shown in Figure 3. Package a is the root of the dependency tree, and there are conflicts between c and e, g and h, and the conflict relationship is represented by an extended dotted line. It can be seen from Figure 3 that if a is to be installed, b, c or d, d or e must be installed first. c and e cannot be installed at the same time. a can be installed that there is at least one dependency satisfaction solution. The dependency integrity of a distribution pool or Linux version means that all software packages in it have a dependency satisfaction solution, that is, they are all installable.

Step 20: Convert the dependency tree into CNF paradigm.

According to the basic mapping rule of converting software package dependency into CNF clause set, the conversion of software package dependency tree to CNF paradigm is completed. The present invention adopts a recursive algorithm. There are two types of algorithms for converting software package dependency tree to CNF paradigm, complete and incomplete. The complete algorithm contains all the special cases, but it will convert a large number of redundant dependencies, resulting in a huge space required by the program; the incomplete algorithm will give up converting a large number of redundant dependencies, but the space occupied by the program will be within the available space. Within the scope of control, there is no limit to the number of software packages. The main difference between the incomplete algorithm and the complete algorithm is the difference in traversing the depth of the dependency tree when the composite node is converted to the CNF paradigm: the complete algorithm traverses the dependency tree until the leaves, and the incomplete algorithm traverses the dependency tree when the depth It will stop traversing downwards when it reaches a certain value. Please refer to FIG. 4 for the specific flow of the incomplete algorithm used in the realization of the present invention.

According to a preferred embodiment, the software package dependency is converted into a CNF algorithm process, and the tree width traversal algorithm is used to convert the software package dependency tree shown in Figure 3 into a CNF paradigm text, and the specific process is as follows:

(1) Add root node a to the node queue;

(2) Obtain node a in the queue;

Obtain the directly dependent nodes of node a, as can be seen from Figure 3, a directly depends on b, then add b to the node queue, and convert b to CNF paradigm output, the output format is b 0; obtain the composite of node a Dependent nodes, as can be seen from Figure 3, the compound dependent nodes of a are c∨d and d∨e, then add c, d, and e to the node queue, and convert c∨d to CNF paradigm output, The output format is c d 0, convert d∨e to CNF paradigm output, and the output format is d e 0; obtain the conflicting node with a, as can be seen from Figure 3, there is no conflicting node with a;

Remove a from the node queue.

(3) Obtain node b in the queue;

Obtain the directly dependent nodes of node b. From Figure 3, we can see that the directly dependent nodes of b are f and g, then add f and g to the node queue, and convert f to CNF paradigm output, and the output format is f0 , convert g to CNF paradigm output, and the output format is g 0; obtain the compound dependent node of node b, as can be seen from Figure 3, b has no compound dependent node; obtain conflicting nodes with b, as can be seen from Figure 3, There are no nodes that conflict with b;

Remove b from the node queue.

(4) Obtain node c in the queue;

Obtain the directly dependent node of node c, as can be seen from Figure 3, the directly dependent node of c is g, because g is already in the node queue, so it is no longer necessary to add it to the node queue; because c∨d, so Take the OR of the directly dependent nodes g and d of c, and convert it into CNF paradigm output, and the output format is g d 0; get the node that conflicts with c, as can be seen from Figure 3, the node that conflicts with c is e, and convert it into CNF The normal form output is -c-e 0;

Remove c from the node queue.

(5) Get the node d in the queue;

Obtain the direct dependent nodes of node d, as can be seen from Figure 3, d has no direct dependent nodes; obtain the composite dependent nodes of node d, as can be seen from Figure 3, the composite dependent nodes of d are g∨h∨i, Then add the nodes h and i that are not yet in the node queue to the node queue, because c∨d, so the compound dependent node g∨h∨i of c and d is ORed, and converted into the CNF paradigm Output, the output format is cg h i 0; because of d ∨ e, the compound dependent node g ∨ h ∨ i of e and d is taken or, converted into CNF paradigm output, the output format is g h i e 0; because g ∨ d, so take or the compound dependent node g∨h∨i of g and d, and convert it into CNF paradigm output, and the output format is g h i 0; obtain conflicting nodes with d, as can be seen from Figure 3, there is no connection with d the point of conflict;

Remove d from the node queue.

(6) Get the node e in the queue;

Obtain the direct dependent node of node e, as shown in Figure 3, the direct dependent node of e is i, and add node i to the node queue; because d∨e, the direct dependent node i of d and e Take or, convert to CNF normal form output, the output format is di 0; get the node that conflicts with e, as can be seen from Figure 3, the node that conflicts with e is c, which already exists in the CNF normal form, so it does not need to be output;

Remove e from the node queue.

f, g, h, and i in the node queue have neither direct dependent nodes nor complex dependent nodes, but only node g and h conflict, converted to CNF paradigm, and the output format is -g-h 0; then they are All are deleted from the node queue, the node queue is empty, and the software package dependency tree is converted to the CNF paradigm.

Generate a CNF paradigm file. The specific content of the file is as follows:

The specific content of the file is as follows:

p cnf 9 12

b 0

c d 0

d e 0

f 0

g 0

g d 0

-c -e 0

c g h i 0

g h i e 0

g h i 0

d i 0

-g -h 0

From the description information in the first line of the above data, it can be seen that the data in the file follows the CNF paradigm, a total of 9 variables and 12 paradigms, each paradigm occupies a line, and 0 in each line represents the end of a line.

Step 30: The CNF paradigm file describing the dependency relationship is used as the input of the SAT problem solving algorithm, and the calculation result is the solution of whether the software can be installed.

In the part of the SAT problem-solving algorithm, the present invention considers the rigor of software package satisfiability judgment, and selects a complete method——DPLL (Davis-Putnam-Logemann-Loveland) algorithm. The DPLL algorithm is a complete, high-level, backtracking-based algorithm for solving the satisfiability of logical propositions.

The specific algorithm pseudo code is as follows:

function DPLL(Φ)\\where Φ is the input in CNF format.

ifΦis a consistent set of literals

  then return true;

if Φcontains an empty clause

then return false;

tor every unit clause l inΦ

Φ＝unit-propagate(l, Φ);

for every literal l that occurs pure inΦ

Φ＝pure-literal-assign(l, Φ);

l:=choose-literal(Φ);

return DPLL(ΦAl) OR DPLL(ΦAnot(l));

According to a preferred embodiment, the first line of the data obtained in the above step 20 describes the information, indicating that the data in the file follows the CNF paradigm, with a total of 9 variables and 12 paradigms. Judging whether the software package a can be installed is to judge whether the above 12 CNF paradigms are Boolean satisfiable. Using the above data as the input of the SAT solving algorithm can get the solution: {Sat; (b d f g)}, where the SAT problem solving algorithm just judges whether the software package has a satisfiable solution, and if so, gives a satisfiable solution If there is no assignment, UNSAT is returned, indicating that there is no satisfiable solution for the software package.

In addition, the package-based dependency integrity check algorithm is summarized as follows:

Dependency-based package dependency checking method: DependIntegritySolver(R)

input: package base R;

Output: the package base dependency integrity check result, including the installable solution or no solution determination result of each package;

for(each package p∈R){

Extract the dependency graph PDG of package p in package base R;

Convert the dependencies between software packages in PDG into CNF clause sets CSet;

MiniSAT_Solver.InitCNF(CSet);

result = MiniSAT_Solver.Solve(CSet);

If (result is NULL) output "no result"; else save the solution result;

}

The above description is only a preferred embodiment of the present invention, and does not limit the present invention in any form. Although the present invention has been disclosed as above with preferred embodiments, it is not intended to limit the present invention. Anyone familiar with this field Those skilled in the art, without departing from the scope of the technical solution of the present invention, can use the method and technical content disclosed above to make some changes or modify equivalent embodiments with equivalent changes, but if they do not depart from the technical solution of the present invention, according to The technical essence of the present invention Any simple modifications, equivalent changes and modifications made to the above embodiments still fall within the scope of the technical solutions of the present invention.

Claims (6)

1. A method for checking software package dependencies based on dependence, used for the software package dependency management of Linux distribution end, is characterized in that, it comprises the following steps: Step 10: Read dependency information from the package dependency description file graphml.xml and generate a package dependency tree; Step 20: Convert the software package dependency tree into CNF paradigm; Step 30: The CNF paradigm describing the dependency relationship is used as the input of the SAT problem solving algorithm, and the calculation result is the solution of whether the software can be installed. 2. according to the described method of claim 1, it is characterized in that, wherein said step 10 also comprises: Step 101: read dependency information from the software package dependency description file graphml.xml; Step 102: choose a software package from the software package collection; Step 103: Generate a dependency tree according to the selected software package and the read dependency information. 3. The dependency-based software package dependency inspection method according to claim 1, characterized in that it maps the software package installability determination problem to a SAT problem, and solves the installability determination problem based on SAT. 4. according to claim 1 based on the dependent software package dependency inspection method, it is characterized in that, to software package dependency tree definition dependent node, dependent node is divided into directly dependent node and compound dependent node, depends on The relationship between nodes is and dependency. 5. The dependency-based software package dependency inspection method according to claim 1, characterized in that, the algorithm used for converting the software package dependency tree into CNF paradigm described in step 20 is an incomplete algorithm. 6. according to claim 1 based on dependent software package dependency inspection method, it is characterized in that, described in step 30 will describe the CNF paradigm of dependency as the input of SAT problem-solving algorithm, and calculation result is whether this software can For the solution of the installation, the algorithm adopted is a complete DPLL algorithm.

Images