And-parallelism arises whenever subgoals belonging to a given query are concurrently solved by different computing agents. Agents exploiting and-parallelism are named and-agents.
And-parallelism is probably the most promising form of parallelism. Every application contains a reasonable amount of it. The same is not true for or-parallelism (since programmers are often tempted to write determinate programs, in which the amount of don't know non-determinism is extremely limited).
Also for and-parallelism it is useful to distinguish different levels of exploitation of parallelism, depending on the degree of dependence allowed between parallel threads. In the case of and-parallelism, dependencies are originated by the presence of variables whose instantiation state can be modified by different concurrent threads of execution. In this way, the execution of a subgoal can affect the execution of others by binding one of these shared variables (also known as dependent variables). Furthermore, it is important to observe that the different and-agents are computing different parts of the same solution to the original query. For this reason it is necessary to create a sufficient amount of sharing between the different and-agents, in order to allow an efficient combination of the partial solutions computed by each of them.
Figure 7: Need for Sharing of Data Structures
