From 5c2b1f74c9c6ed932e5a430a1d1d9562b488d89c Mon Sep 17 00:00:00 2001
From: Zac Medico <zmedico@gentoo.org>
Date: Sat, 19 Apr 2008 13:12:11 +0000
Subject: Add a new part for "Dependency Resolution". (trunk r9926)

svn path=/main/branches/2.1.2/; revision=9927
---
 doc/dependency_resolution/decision_making.docbook | 65 +++++++++++++++++++++++
 1 file changed, 65 insertions(+)
 create mode 100644 doc/dependency_resolution/decision_making.docbook

(limited to 'doc/dependency_resolution/decision_making.docbook')

diff --git a/doc/dependency_resolution/decision_making.docbook b/doc/dependency_resolution/decision_making.docbook
new file mode 100644
index 000000000..5bcf84388
--- /dev/null
+++ b/doc/dependency_resolution/decision_making.docbook
@@ -0,0 +1,65 @@
+<chapter id='dependency-resolution-decision-making'>
+<title>Decision Making</title>
+<sect1 id='dependency-resolution-decision-making-dependency-expression-evaluation'>
+	<title>Dependency Expression Evaluation</title>
+	<para>
+	In terms of boolean logic, a dependency expression can
+	be expressed in disjunctive normal form (DNF), which is
+	a disjunction of conjunctive clauses. Each conjunctive clause
+	represents one possible alternative combination of dependency
+	atoms capable of satisfying the dependency expression.
+	</para>
+</sect1>
+<sect1 id='dependency-resolution-decision-making-look-ahead'>
+	<title>Look-Ahead</title>
+	<para>
+	When there are multiple combinations to choose from,
+	a look-ahead mechanism will choose an optimal combination
+	to satisfy constraints and minimize cost. The
+	following package states influence the cost calculation for
+	a given combination:
+	<itemizedlist>
+	<listitem>
+		installed
+	</listitem>
+	<listitem>
+		selected (for installation)
+	</listitem>
+	<listitem>
+		not selected (for installation)
+	</listitem>
+	</itemizedlist>
+	</para>
+	<para>
+	In cost calculations, virtual packages by themselves are
+	considered to cost nothing since they do not directly install anything.
+	It is the dependencies of a virtual package that contribute to it's cost.
+	</para>
+	<sect2 id='dependency-resolution-decision-making-look-ahead-constraint-propagation'>
+		<title>Constraint Propagation</title>
+		<para>
+		Combinations that include packages from the "installed" or
+		"selected" categories are less costly than those that
+		include packages from the "not selected" category.
+		When a package is chosen for installation, it transitions to the
+		"selected" state. This state change propagates
+		to the cost calculations of later decisions,
+		influencing later decisions to be consistent with earlier decisions.
+		This feedback mechanism serves to propagate constraints and can
+		influence the modeling process to
+		converge on a more optimal final state.
+		</para>
+	</sect2>
+	<sect2 id='dependency-resolution-decision-making-look-ahead-expanded-search-space'>
+		<title>Expanded Search Space</title>
+		<para>
+		When evaluating virtual atoms, an expanded search space is
+		considered which recursively traverses
+		the dependencies of virtual packages
+		from all slots matching a given virtual atom. All combinations in
+		this expanded search space are considered when choosing an optimal
+		combination to satisfy constraints with minimal cost.
+		</para>
+	</sect2>
+</sect1>
+</chapter>
-- 
cgit v1.2.3-1-g7c22