The development of conjunctive decomposition tools focused on building logical network models is the main topic of this article. The possibility of using such tools for the development of linguistic information processing systems determines the relevance of the chosen topic. The relationship between operations in relational algebra and in the algebra of finite predicates is de-scribed. With the help of relational statements about dependencies, the algebraological apparatus of decomposition of predicates was further developed. The method of binary decomposition of functional predicates is founded, which differs from the general method of Cartesian decomposition in that the number of values of the auxiliary variable is minimized.
Among the many formalisms applicable to one degree or another to the tasks of processing informal information, the most appropriate is the use of predicate algebra, systems of equations which are technically implemented in the form of a logical network. One of the advantages of this approach is its direct applicability to all the following types of problems, which is provided by the declaratives of the logical network as a method of solving systems of predicate equations. The notation of the predicate equations itself becomes possible due to the algebra of predicates.
On the example of processing test information by artificial intelligence, we can consider the general classification of tasks that arise in the process of working with primary informal information: analysis (for example, recognition - obtaining from informal information specific parameters necessary for the application of some formalism); normalization - bringing information to some reference form, which is relevant in the search for information; synthesis - the expression of the internal representation of information stored in accordance with the formal requirements in a form adapted for human perception; mixed tasks.
Another advantage of logical networks is the wide parallelization of calculations, which, provided the correct construction of the task model guarantees high efficiency.
In addition, the brain-like computer, based on the technology of logical networks, is close in structure to the structure of the human brain, which gives reason to hope for the creation of information technology-based systems based on the capabilities of human [1].
The study of categories quickly became an independent abstract discipline and is now an important branch of pure mathematics. In addition, it influenced the conceptual foundations of mathematics and the language of mathematical practice. It offers elegant and powerful tools for expressing connections between major branches of mathematics and provides mathematicians with tools for mathematical research that occupy more and more space in the arsenal of mathematics.
However, to date, the theory of categories still does little to solve problems such as the description of the mechanisms of human intelligence, such as the development of artificial intelligence, the creation of parallel computers, intelligent radar systems, and so on.
Therefore, it is necessary to establish a connection between the theory of categories and modeling of systems based on artificial intelligence using an intermediate field of knowledge - the algebra of finite predicates, by which a predicate interpretation of the category can be built. Based on this interpretation, elements of the theory of the modified category for the processes of modeling the functions of artificial intelligence are developed.
A distinctive feature of artificial intelligence tasks is that they are difficult to formalize, necessary to enable the automation of their solutions. Thus, it is expedient to study the universal tool of informal information processing – the human brain and to model some of its functions related to the tasks based on modern technologies. The essence of the approach is that human intelligence is seen as logic in action, as some material embodiment of the mechanism of logic. Works on logic algebraization were performed.
Schematic implementation of formulas describing algebraic-logical structures leads to characteristic engineering networks that have not been used before, and which are called logical networks. When comparing these networks with the main types of neural structures, a deep similarity in the structure of technical and biological structures is revealed. Based on this similarity, we can determine the functions of different types of neural structures and describe in exact mathematical and technical terms the principles of brain function.
The main thing in this method is the movement from top to bottom: from general system considerations to algebraic-logical structures, and from them to logical networks, which are then identified with biological neural structures.
Unlike the traditional information technology algorithmic approach, the declarative task model is not an algorithm. The task model presented in a declarative form is usually a set of facts, knowledge of facts and rules, according to which actions are taken on facts that allow to obtain new knowledge based on old ones.
A logical network is a method for solving systems of predicate equations and has descriptive capabilities of predicate algebra. The property of a logical network is the parallel execution of all elementary logical operations – that is, the maximum possible at the logical level of parallel calculations. This approach guarantees high efficiency in solving problems that are reduced to a logical conclusion or to the solution of logical equations.
To formalize the tasks of processing informal information using logical networks, it is necessary to explore the possibilities of rational application of the algebra of finite predicates. To this end, it is necessary to model the most common tasks from different areas of the subject area. Examples include areas such as: the task of modeling the recognition mechanisms of inconspicuous radar objects.
The mathematical tools developed for the decomposition of relations and predicates are designed primarily to create logical networks, which, in turn, are the basis for building a parallel-action computer. The mathematical results of the work can be used in automatic language processing systems, computer-aided design systems for information systems. Logical networks can be effective in creating specialized parallel-action devices designed to simulate complex computing systems, for example, a system of complete adequate morphological analysis of natural language texts.
Mathematical model suitable for implementation in the form of a logical network should be represented by a system of binary equations, i.e., each equation of such a system should have two variables. This form of presentation is a logical network model. In this case, the system of binary equations should be as compact as possible in order to save hardware resources when implementing the model.
Converting a model into a compact binary form requires conjunctive decomposition of predicates. In the area of the decomposition apparatus, a shortage of justified methods, that does not require checking the equivalence of the obtained result to the original predicate, and at the same time rational methods that allow obtaining a compact binary representation for a given formal model. When developing models of logical networks for processing linguistic information, developers mostly used their own intuitive methods, rather than strict, justified methods. The logical network models obtained in this way need experimental verification of their adequacy to the described object.
Almost all available formal means of decomposition of predicates in these works do not consider the relationship between variables. Taking these features into account in the structure of a predicate allows one to decompose it in a more rational way. Meanwhile, the theory of relational databases offers a means of decomposing relations in the form of statements about the dependencies between attributes (in the section on normalizing relations). Given the deep connection between relations and predicates, the means of decomposition of relations can be applied to solve the problem of decomposition of predicates. As an analysis of the literature has shown that such tools are currently not available in the apparatus of predicate algebra.
The only difference between category theory and predicate algebra is that the former moves from top to bottom, aims to learn higher logical mechanisms and therefore uses as starting points the concept of a record level of commonality. The second, starting from the needs of informatization, moves in the study of the same logic of thinking from the bottom up. If it were possible to give a convincing interpretation of the concepts formed by the theory of categories and the methods developed by it in terms of predicate algebra, i.e., concretizing, to bring them closer to informatization, it would significantly enrich the tools of predicate algebra. It is the algebra of predicates that we are going to use as such an intermediate field of knowledge.
A logical network copies a person's actions, but with the only difference that a person acts sequentially and a network acts in parallel. The network works in cycles. In the first half-bar of the th bar, the network for each of its equations of the form ( is the relation given by such equation) finds: 1. according to the known knowledge of about the value of the variable x at the beginning of i- th bar knowledge about the value of the variable at the end of the -th bar; 2. according to the known knowledge of about the value of the variable at the beginning of the -th bar, knowledge of about the value of the variable at the end of the -th bar.
Mathematically, these two operations are expressed by formulas: where and are the variable areas of .
In the second half of each bar, the network finds the common part of all knowledge about the value of each of its objective variables parties, which come through the branches of the network from all to the pole . This operation is expressed as follows:
The obtained knowledge is then used as the state of the pole at the initial moment of the st cycle. The symbol denotes the number of branches approaching the pole x. Before the beginning of the st bar, knowledge of the set is formed in each pole, which is always included in the knowledge of the set , which was kept in the same pole at the beginning of the -th bar. Thus, the only result of the logical network is the refinement of the knowledge contained in all its poles in accordance with the original data.
With the introduction of the theory of categories, along with the usual concept of category, there was a more general concept of objectless category.
Let be some set. Its elements, denoted by the symbols are called morphisms. Suppose, moreover, that some, in the general case, partial operation is given, which acts with . It is called the multiplication of the morphisms and . The morphism is called the product of the morphisms and . Any morphism is called singular or identical if it satisfies the following conditions: for any for which there is a product , the equality ; for any for which there is a product , the equality holds.
This definition tacitly allows the existence in the category of many units. It is the presence of many units (and only this) that distinguishes a category from other known algebraic structures. The singular morphisms and are named according to the right and left for the morphism , if and . For any morphism there are a single right and a single left morphisms. This statement is called the law of identity. Thus, for each there is a single right unit ef and a single left unit , such that .
Multiplication of morphisms is associative: for any for which there are products: and . The set , which contains at least single morphisms, and on which the operation of multiplication of morphisms with the above properties is called an object-free classical category . Write . is the set of all morphisms of category . If , then we say that the morphism is a -Morphism.
Next, we will talk about the development of new predicate decomposition tools based on statements about dependencies from the normalization of relational relations. At the beginning, an exact definition of the decomposition procedure with respect to relational relations and predicates is given; statements about dependencies that allow decomposition of relational relations are considered; their generalizations are proposed. Based on the relations between relational algebra and predicate algebra, dependency statements are transformed into new predicate decomposition tools.
A predicate in the basis of a disjunctive conjunctive predicate algebra (DCPA) is usually regarded as an analytic notation of a relation. Therefore, a predicate decomposition is a decomposition of a relation at the analytical level (simply manipulating formulas), when not the relations themselves are processed, but the corresponding predicate formulas.
We clarify the concept of decomposition, as it is understood in relational databases. To do this, we give the concept of the dependence of the compound, which is used in the theory of dependencies.
Let be a subset family of sets . If , then is called overlapping of set . An overlapping is called a partition of a set
Let be some relation, and the family of sets The relationship satisfies the connection if the sets are pairwise disjoint.
forms the covering of the set dependencies if .
Other types of dependencies that are used in the theory of dependencies – functional and
multivalued dependencies – are special cases of the connection dependency. Therefore, any dependence
made in allows us to represent in the form of a natural connection of their projections
(
However, splitting a relation can be carried out in different ways: along with projection, for
example, sampling can be used as a decomposition operator. Then the composition operator will no
longer be a natural join, but a join operation. When in database theory we are talking about the
decomposition of relations, then almost always we mean a decomposition of the form (
dependences
A predicate decomposition of is the derivation of some predicates based on a predicate with the possibility of its reverse recovery from these predicates, which is called the predicate compositionof . An important particular case of decomposition is the so-called binary predicate decomposition of , characterized in that each of the predicates resulting from the decomposition of the predicate has exactly two significant arguments. If the conjunction serves as the composition (restoration) operator, then decomposition is called conjunctive.
The predicate analogues of relational projection operations are existence quantifiers. Then the predicate analogue of the projection-connective decomposition will be the quantifier-conjunctive form of decomposition.
Let be a spanning tree with a finite set of variable names ,
Let be some predicate from , and the family of sets form a covering of the set . We say that a predicate satisfies conjunction if where , .
Representation of the predicate in the form of (
Some methods for decomposing predicates boil down to replacing the original predicate with
some auxiliary predicate , which is built based on the original predicate by introducing one or
more auxiliary variables . The idea of these methods is that the auxiliary predicate is
constructed in advance so that it satisfies some required quantifier-conjunctive dependence. Then,
using the existential quantifiers, the predicate is decomposed directly. This predicate is related to
the original predicate by equality
(
Although in fact a quantifier-conjunctive decomposition of the auxiliary predicate is performed,
the original predicate is restored using equality (
Thus, the predicate decomposition can be performed either without the help of auxiliary variables,
or with the help of them. In the first case, decomposition is called equivalent, in the second –
nonequivalent. So, the decomposition of the mentioned predicate is equivalent, and the
decomposition of the original is nonequivalent. Quantifier conjunctive decomposition is
equivalent.
(
Let us consider the concepts of dependencies and some statements regarding them. The latter allow for a given relationship to resolve the question of the admissibility of a projection-connective decomposition. Consider special cases: functional and multi-valued dependencies.
Let a relation be given and , be arbitrary subsets of the set . It is said that depends functionally on if for any two functional data from equality follows the equality . If depends functionally on , it is written and said that the relation satisfies the functional dependence or that the functional dependence is fulfilled in the relation
It follows directly from the definition that if the dependence is satisfied in , then it is executed in any of its projections containing many attributes .
If is an arbitrary relation, then the set of pairs such that in by . It is called the structure of the functional dependencies of the relationship .
Let be an arbitrary relation . It is proved that the structure of functional dependencies the following properties ( is a subset of a set ).
, then
If (
If and , then (
For a deductive system defined by rules (
Statement 1. Haag's theorem. Let
forms a partition of the set
. If
be some relation from
in , then
, and the family of sets
(
In other words, Haag's theorem says that functional dependence in relation implies connection dependence for it.
Let us consider the concept of multi-valued dependence. Let a relation be given and let and be arbitrary subsets of the set . It is said that ambiguously determines if , where . If defines ambiguously, it is written and said that the relation satisfies the ambiguous dependence or that the ambiguous dependence is fulfilled in the relation .
The above definition shows that a multi-valued dependence is a special case of a connection dependence and is also determined through an algebraic integrity constraint.
If is an arbitrary relation, then the set of pairs such that in is denoted by . It is called the structure of multi-valued relationship dependencies .
Let be an arbitrary relation. It is proved that the structure of multivalued dependencies has the following properties ( , , , - subsets of a set ).
If , then
If and , then
, then
(
If , then (10)
Property (10) suggests that multi-valued dependencies always form connected pairs; therefore, the
notation is used to relate to and the dependence . As for
functional dependencies, for the deductive system defined by rules (
Statement 2. Let be an arbitrary relation, and and be arbitrary subsets of the set . The relation satisfies the dependence if and only if for every and every .
Equality (11) shows, that for every from set . It means that multivalued dependency (11) in
does not depend on defines the displaying of from to Boolean that can be related as multivalued function from in .
This statement in less formal form is chosen as a definition to multivalued dependency by Date. Except for the notation, this definition is as follows.
Let there be some relation , and , and the sets do not intersect in pairs. multivalued depends on if and only if the set of values corresponding to a given pair (value and value ) of the ratio depends only on but does not depend on .
At the same time, Date cites the definition of multivalued dependence adopted in this paper as Feigin's theorem, which is formulated in terms of “if and only if”.
Statement 3. Let be an arbitrary relation, and and be arbitrary subsets of the set , . The relation satisfies the dependence if and only if for every .
Note that the natural combination of two relations that have no common attributes can be viewed as an extended version of the Cartesian product. Equality (12) expresses just such a case. In fact, Statement 3 expresses another way that multivalued dependency can be defined.
According to Statement 3, the presence of a multivalued relationship in a relation means that its attributes and are mutually independent: the set of values of each of them depends only on the value of the attribute . In other words, multivalued dependencies appear when, for a meaningful group of characteristics , the set of values of characteristics from groups and must occur in any combinations with a fixed value of the component.
Each functional dependence is a multivalued dependence, i.e. if at , then at . Therefore . Thus, multivalued dependencies are a generalization of functional dependencies.
However, there is a significant difference between functional and multivalued dependencies. According to (10) dependences and always form connected pairs, which is denoted as , where . Property (10) has no analogue for functional dependencies, therefore, in the general case, they do not form connected pairs.
The following statement generalizes Statement 2, and this time uses the notion of connection dependency.
Statement 4. Let be some relation from , and the family of sets forms a partition of the set . The relation satisfies the connection dependence if and only if (12) (13) for each .
Statement 5. Generalization of Feigin's theorem. Let be some relation from , and the family of sets forms a partition of the set . A relation satisfies the connection dependency if and only if it simultaneously satisfies multivalued dependencies .
According to Statement 3, the multivalued dependence performed in relation to with expresses the mutual independence of attributes and in relation to considering that the set of values of each of them is determined by the value of the attribute . In the same way, Statement 3 allows us to consider the dependence performed in , : it expresses the mutual independence of attributes , from each other, given that the set of values of each of them is determined by the value of the attribute .
According to Haag's theorem, functional dependence acts as a sufficient condition for decomposition of a given relation into two of its projections. Statements 2 and 3 can be considered as criteria for the presence of a certain multivalued dependence in a given relation. Statement 4 is a criterion for the presence of a connection dependence of a certain type, and Statement 5 establishes the equivalence of such a dependence to a group of multivalued dependencies with the same determinant. Due to this, Statement 4 can be viewed as a generalization of Statement 3 to the case of a group of multivalued dependencies.
(14)
Any functional dependence of one group of predicate variables on another group can be specified either by several formulas of the form (14), or by one such formula in which, after implication, there will be a conjunction of several equality predicates. If and are subsets of predicate variables and functionally depends on , then we the predicate satisfies the functional dependence .
The multi-valued dependence for predicates can be expressed in terms of the conjunction dependence. We say that a predicate satisfies a multi-valued dependence if it satisfies the dependency of the conjunction , where . In this case the dependence will also be fulfilled, which together can be denoted as .
As with relational relationships, dependency structures can also be defined for predicates. Let be , . Then the set of pairs such that in , is denoted by and will be called the structure of the functional dependences of the predicate. Similarly, the set of pairs such that in, is denoted by and will be called the structure of multivalued dependencies of the predicate.
Apparently, sets and will have the same properties as dependency structures for relationships. But to verify this assumption, additional research is required, which is beyond the scope of this paper.
Connection dependency properties are derived from the properties of a natural join operation. An analogue of the natural connection of relations is the conjunction of predicates, which, like the natural connection, is idempotent, commutative, and associative. Two other properties of the natural compound are easily extended to the conjunction operation. If we show the fulfillment of the latter for the conjunction, then it can be argued that the dependencies of the conjunction have the same properties as the dependencies of the connection.
The only justified binary predicate decomposition method that guarantees the correctness of the result is the Cartesian decomposition, which allows decomposition of any finite predicates, not just functional ones. Although the disadvantages of this method were discussed earlier, we will consider the Cartesian decomposition as a starting point for finding a more rational method in the sense of saving hardware resources.
To perform the Cartesian decomposition of a predicate , it is necessary to explicitly represent its region of truth. As such, you can use the PDNF (Principal Disjunctive Normal Form) for predicate . Let be the region of truth of the predicate , . Then where is the number of tuples of the relation the predicate ).
According to the Cartesian decomposition method, an auxiliary variable is introduced with values that are interpreted as unique names of relationship tuples.
Cartesian decomposition is performed by constructing an auxiliary predicate and subsequent binary decomposition using existential quantifiers. (15
) (which will of course be due to the finiteness of As noted above, the disadvantage of this decomposition is that the variable takes as many values within the predicate and its projections as the number of tuples contains the region of truth of the predicate . We assume that this is the maximum number of values of the auxiliary variable that is required for binary decomposition of the predicate, since such a quantity is always sufficient. In real language models, this number is usually large. It was previously explained that this complicates the circuitry implementation of such models on a microcircuit. In addition, during Cartesian decomposition, no structural features of the predicate are considered in order to reduce the number of values of the auxiliary variable.
The task is to use a binary function (and other dependencies if they exist in the predicate) to perform binary decomposition either directly using existence quantifiersor with the preliminary introduction of one auxiliary variable with a minimum number of values.
The principle of the proposed method of binary decomposition consists in the methods of constructing auxiliary predicates, based on which with the help of existential quantifiers (by eliminating variables) many binary predicates are formed. The latter are the result of binary decomposition of the original predicate. The construction of auxiliary predicates can be performed in different ways, or it may not be necessary at all. From the point of view of the structure of the initial functional predicate, three different situations are possible that determine the sequence of actions to achieve binary decomposition at a minimum price.
When binary decomposition of a functional predicate is necessary, firstly, it is necessary to check whether the arguments of the described function are independent of each other. Mutual independence of variables in a predicate means that the dependency is fulfilled. To strictly check the predicate for a dependency , it is necessary to perform a disjunctive expansion of the predicate by variables . After that, the form of this decomposition will allow us to establish exactly whether the dependence in the predicate is fulfilled or not.
If the predicate satisfies the dependencies , then binary decomposition is quite simple. There are two possible situations.
The first situation occurs when a group of variables consists of one variable – . Then an auxiliary variable is not required: binary decomposition is performed using existence quantifiers directly based on a given conjunction dependence, which can be represented as ..., . This is the simplest case. A slightly more complicated case is when a group consists of two or more variables; then the second situation takes place.
In the second situation, it is necessary to replace the group of variables with one auxiliary variable , and then make the transition to two auxiliary predicates – and , which are the result of intermediate decomposition of the predicate . The binary decomposition of predicates and is carried out using existence quantifiers based on conjunction dependencies ..., and ..., respectively, which, as will be shown below, are performed by virtue of the construction of these predicates.
When does not satisfy the dependency , then the most difficult situation of the three possibly takes place. Here, the transition to auxiliary predicates and also follows, followed by binary decomposition of the latter. However, the method of generating these auxiliary predicates in this case is much more complicated.
The last and most difficult situation from the point of view of binary decomposition of a functional predicate occurs when the dependence is not satisfied. In this case, an auxiliary variable is also required. It will be introduced after the system of special subsets of the set is formed. The values of the auxiliary variable in this case will act as the names of these subsets. With this approach, on the one hand, dependencies will be built in auxiliary predicates that will allow their binary decomposition to be performed. On the other hand, the minimum required number of the indicated subsets will be formed, which will minimize the number of values of the auxiliary variable.
As with Cartesian decomposition, the advantage of this algorithm for executing the binary decomposition of functional predicates is the ability to process the formula or relation not in whole but in parts: for each complete inverse image, its minimum parallelepiped coverage is selected separately.
All available methods of nonequivalent decomposition, i.e., decompositions involving auxiliary variables oriented to static predicates or relations. The described method is no exception. Meanwhile, relationships in databases are dynamic objects that are constantly updated. Therefore, nonequivalent decomposition methods are not suitable for use in databases. However, they are good at describing natural language grammar, which (in comparison with industrial or commercial databases) can be considered a static object.
On the way to creating a logical network that simulates a significant part of the natural language, there are several goals that can be described as follows. The first goal is to present the entire model of inflection by the logical network, and not just the individual parts of speech. The next goal is to provide a logical model of a word; this model should accurately express the entire morphology of the language, so the size of such a network seems quite impressive. The main goal is to provide the logical network with a general model of semantic-syntactic processing of phrases, which should cover most of the language.
In order to consistently move towards achieving your goals, you need to start with a model of inflection. So, to date, models of logical networks for the inflectional processing of some nominal parts of the speech of the language are already available: a model of inflections (end declension mechanism) of full non-possessive adjectives, a model of inflections of nouns of substantive declension. Other parts of speech, from existing models of inflectional processing, are not yet presented in the form of a logical network.
All formulas are presented in the basis of the disjunctive conjunctive predicate algebra (DCPA); therefore, the size or length of the formula is determined by the number of predicates of recognition of the subject contained in it. The binary predicate formulas obtained by decomposing and are written in compact form, which we will call the disjunctive-bracket form. It is in this form that the DCPA binary formulas form the basis of the circuitry implementation. The amount of hardware resources for the implementation of a model presented in the DCPA language is proportional to the number of recognition predicates in it. Therefore, the number of recognition predicates in the formulas of a certain model makes it possible to approximately estimate the amount of hardware resources that will be spent on its implementation.
Predicates serve as a means of describing finite discrete relations; therefore, one can also evaluate the result of decomposition by the size of relations corresponding to the obtained formulas. The size of a finite relationship is determined, like the size of any finite set, by the number of its elements. The dimension of relations (the number of attributes) can be ignored, since only binary relations are to be compared. Therefore, it is proposed for each method to calculate the total number of binary tuples in the obtained relations and, thereby, compare these methods with each other.
Such a calculation will be carried out by calculating the constituent units in the formulas, since the number of these constituents in the PDNF predicate coincides with the number of tuples of the corresponding relation. To move from the disjunctive-bracket form of a formula to its PDNF, you just need to open all the brackets in this formula. Therefore, to determine the number of constituents in the PDNF of a certain formula, it is necessary to calculate how many terms will be contained in the formula after the brackets are opened.
Based on the obtained binary formulas, one can calculate the length of each of them and the number of tuples in the corresponding relation. Cartesian decomposition of predicates and was not carried out, but the above parameters can be accurately calculated by determining the number of tuples in the relations corresponding to these predicates.
Cartesian decomposition is a rather trivial way to decompose, so the structure of the resulting binary predicates is very simple. Each such predicate is everywhere defined, surjective, and contains an auxiliary variable that uniquely determines the value of another variable. The length of the formula of such a predicate in the minimum disjunctive-bracket form is determined as the sum of the areas of variation of its variables.
The main types of dependencies of attributes in relational relations are considered: functional, multivalued and connection dependencies. Considered assertions about dependencies that allow decomposition of relational relations.
The decomposition of the model of inflectional processing of regular verb word forms was performed using the method of binary decomposition of functional predicates developed in this work. As a result, a logical network was built for this model.
The analysis of the hardware implementation of the constructed logical network showed that such a network, implemented on a modern inexpensive programmable logic integrated circuit, works three orders of magnitude faster than a computer program that simulates the same logical network on a modern personal computer of average power. 10.References