rfc2533.txt

RFC 的详细文档！

         which case the corresponding conjunction can never be
         satisfied).

   7. If the remaining disjunction contains at least one satisfiable
      conjunction, then the constraints are shown to be satisfiable.

   The final expression obtained by this procedure, if it is non-empty,
   can be used as a statement of the resulting feature set for possible
   further matching operations.  That is, it can be used as a starting
   point for combining with additional feature set constraint predicate
   to determine a feature set that is constrained by the capabilities of
   several entities in a message transfer path.




Klyne                       Standards Track                    [Page 18]

RFC 2533       A Syntax for Describing Media Feature Sets     March 1999


      NOTE: as presented, the feature matching process evaluates (and
      stores) all conjunctions of the disjunctive normal form before
      combining feature tag comparisons and eliminating unsatisfiable
      conjunctions.  For low-memory systems an alternative approach is
      possible, in which each normal form conjunction is enumerated and
      evaluated in turn, with only those that are satisfiable being
      retained for further use.

5.2 Formulating the goal predicate

   A formal statement of the problem we need to solve can be given as:
   given two feature set predicates, '(P x)' and '(Q x)', where 'x' is
   some feature collection, we wish to establish the truth or otherwise
   of the proposition:

      EXISTS(x) : (P x) AND (Q x)

   i.e. does there exist a feature collection 'x' that satisfies both
   predicates, 'P' and 'Q'?

   Then, if feature sets to be matched are described by predicates 'P'
   and 'Q', the problem is to determine if there is any feature set
   satisfying the goal predicate:

      (& P Q)

   i.e. to determine whether the set thus described is non-empty.

5.3 Replace set expressions

   Replace all "set" instances in the goal predicate with equivalent
   "simple" forms:

      T = [ E1, E2, ... En ]  -->  (| (T=[E1]) (T=[E2]) ... (T=[En]) )
      (T=[R1..R2])            -->  (& (T>=R1) (T<=R2) )
      (T=[E])                 -->  (T=E)

5.4 Move logical negations inwards

   The goal of this step is to move all logical negations so that they
   are applied directly to feature comparisons.  During the following
   step, these logical negations are replaced by alternative comparison
   operators.

   This is achieved by repeated application of the following
   transformation rules:





Klyne                       Standards Track                    [Page 19]

RFC 2533       A Syntax for Describing Media Feature Sets     March 1999


      (! (& A1 A2 ... Am ) )  -->  (| (! A1 ) (! A2 ) ... (! Am ) )
      (! (| A1 A2 ... Am ) )  -->  (& (! A1 ) (! A2 ) ... (! Am ) )
      (! (! A ) )             -->  A

   The first two rules are extended forms of De Morgan's law, and the
   third is elimination of double negatives.

5.5 Replace comparisons and logical negations

   The predicates are derived from the syntax described previously, and
   contain primitive value testing functions '=', '<=', '>='.  The
   primitive tests have a number of well known properties that are
   exploited to reach a useful conclusion; e.g.

      (A = B)  & (B = C)  => (A = C)
      (A <= B) & (B <= C) => (A <= C)

   These rules form a core body of logic statements against which the
   goal predicate can be evaluated.  The form in which these statements
   are expressed is important to realizing an effective predicate
   matching algorithm (i.e. one that doesn't loop or fail to find a
   valid result).  The first step in formulating these rules is to
   simplify the framework of primitive predicates.

   The primitive predicates from which feature set definitions are
   constructed are '=', '<=' and '>='.  Observe that, given any pair of
   feature values, the relationship between them must be exactly one of
   the following:

      (LT a b): 'a' is less than 'b'.
      (EQ a b): 'a' is equal to 'b'.
      (GT a b): 'a' is greater than 'b'.
      (NE a b): 'a' is not equal to 'b', and is not less than
                or greater than 'b'.

   (The final case arises when two values are compared for which no
   ordering relationship is defined, and the values are not equal; e.g.
   two unequal string values.)

   These four cases can be captured by a pair of primitive predicates:

      (LE a b): 'a' is less than or equal to 'b'.
      (GE a b): 'a' is greater than or equal to 'b'.

   The four cases described above are prepresented by the following
   combinations of primitive predicate values:





Klyne                       Standards Track                    [Page 20]

RFC 2533       A Syntax for Describing Media Feature Sets     March 1999


      (LE a b)   (GE a b) | relationship
      ----------------------------------
         TRUE      FALSE  | (LT a b)
         TRUE       TRUE  | (EQ a b)
        FALSE       TRUE  | (GT a b)
        FALSE      FALSE  | (NE a b)

   Thus, the original 3 primitive tests can be translated to
   combinations of just LE and GE, reducing the number of additional
   relationships that must be subsequently captured:

      (a <= b)  -->  (LE a b)
      (a >= b)  -->  (GE a b)
      (a = b)   -->  (& (LE a b) (GE a b) )

   Further, logical negations of the original 3 primitive tests can be
   eliminated by the introduction of 'not-greater' and 'not-less'
   primitives

      (NG a b)  ==  (! (GE a b) )
      (NL a b)  ==  (! (LE a b) )

   using the following transformation rules:

      (! (a = b) )   -->  (| (NL a b) (NG a b) )
      (! (a <= b) )  -->  (NL a b)
      (! (a >= b) )  -->  (NG a b)

   Thus, we have rules to transform all comparisons and logical
   negations into combinations of just 4 relational operators.

5.6 Conversion to canonical form

      NOTE: Logical negations have been eliminated in the previous step.

   Expand bracketed disjunctions, and flatten bracketed conjunctions and
   disjunctions:

      (& (| A1 A2 ... Am ) B1 B2 ... Bn )
        -->  (| (& A1 B1 B2 ... Bn )
                (& A2 B1 B2 ... Bn )
                 :
                (& Am B1 B2 ... Bn ) )
      (& (& A1 A2 ... Am ) B1 B2 ... Bn )
        -->  (& A1 A2 ... Am B1 B2 ... Bn )
      (| (| A1 A2 ... Am ) B1 B2 ... Bn )
        -->  (| A1 A2 ... Am B1 B2 ... Bn )




Klyne                       Standards Track                    [Page 21]

RFC 2533       A Syntax for Describing Media Feature Sets     March 1999


   The result is in "disjunctive normal form", a disjunction of
   conjunctions:

      (| (& S11 S12 ... )
         (& S21 S22 ... )
          :
         (& Sm1 Sm2 ... Smn ) )

   where the "Sij" elements are simple feature comparison forms
   constructed during the step at section 5.5.  Each term within the
   top-level "(|...)" construct represents a single possible feature set
   that satisfies the goal.  Note that the order of entries within the
   top-level '(|...)', and within each '(&...)', is immaterial.

   From here on, each conjunction '(&...)' is processed separately.
   Only one of these needs to be satisfiable for the original goal to be
   satisfiable.

   (A textbook conversion to clausal form [5,11] uses slightly different
   rules to yield a "conjunctive normal form".)

5.7 Grouping of feature predicates

      NOTE:  Remember that from here on, each conjunction is treated
      separately.

   Each simple feature predicate contains a "left-hand" feature tag and
   a "right-hand" feature value with which it is compared.

   To arrange these into independent groups, simple predicates are
   grouped according to their left hand feature tag ('f').

5.8 Merge single-feature constraints

   Within each group, apply the predicate simplification rules given
   below to eliminate redundant single-feature constraints.  All
   single-feature predicates are reduced to an equality or range
   constraint on that feature, possibly combined with a number of non-
   equality statements.

   If the constraints on any feature are found to be contradictory (i.e.
   resolved to FALSE according to the applied rules), the containing
   conjunction is not satisfiable and may be discarded.  Otherwise, the
   resulting description is a minimal form of that particular
   conjunction of the feature set definition.






Klyne                       Standards Track                    [Page 22]

RFC 2533       A Syntax for Describing Media Feature Sets     March 1999


5.8.1 Rules for simplifying ordered values

   These rules are applicable where there is an ordering relationship
   between the given values 'a' and 'b':

      (LE f a)  (LE f b)      -->  (LE f a),   a<=b
                                   (LE f b),   otherwise
      (LE f a)  (GE f b)      -->  FALSE,      a<b
      (LE f a)  (NL f b)      -->  FALSE,      a<=b
      (LE f a)  (NG f b)      -->  (LE f a),   a<b
                                   (NG f b),   otherwise

      (GE f a)  (GE f b)      -->  (GE f a),   a>=b
                                   (GE f b),   otherwise
      (GE f a)  (NL f b)      -->  (GE f a)    a>b
                                   (NL f b),   otherwise
      (GE f a)  (NG f b)      -->  FALSE,      a>=b

      (NL f a)  (NL f b)      -->  (NL f a),   a>=b
                                   (NL f b),   otherwise
      (NL f a)  (NG f b)      -->  FALSE,      a>=b

      (NG f a)  (NG f b)      -->  (NG f a),   a<=b
                                   (NG f b),   otherwise

5.8.2 Rules for simplifying unordered values

   These rules are applicable where there is no ordering relationship
   applicable to the given values 'a' and 'b':

      (LE f a)  (LE f b)      -->  (LE f a),   a=b
                                   FALSE,      otherwise
      (LE f a)  (GE f b)      -->  FALSE,      a!=b
      (LE f a)  (NL f b)      -->  (LE f a)    a!=b
                                   FALSE,      otherwise
      (LE f a)  (NG f b)      -->  (LE f a),   a!=b
                                   FALSE,      otherwise

      (GE f a)  (GE f b)      -->  (GE f a),   a=b
                                   FALSE,      otherwise
      (GE f a)  (NL f b)      -->  (GE f a)    a!=b
                                   FALSE,      otherwise
      (GE f a)  (NG f b)      -->  (GE f a)    a!=b
                                   FALSE,      otherwise







Klyne                       Standards Track                    [Page 23]

RFC 2533       A Syntax for Describing Media Feature Sets     March 1999


      (NL f a)  (NL f b)      -->  (NL f a),   a=b
      (NL f a)  (NG f b)      -->  (NL f a),   a=b

      (NG f a)  (NG f b)      -->  (NG f a),   a=b

6. Other features and issues

6.1 Named and auxiliary predicates

   Named and auxiliary predicates can serve two purposes:

      (a)  making complex predicates easier to write and understand, and

      (b)  providing a possible basis for naming and registering feature
           sets.

6.1.1 Defining a named predicate

   A named predicate definition has the following form:

      named-pred =  "(" fname *pname ")" ":-" filter
      fname      =  ftag        ; Feature predicate name
      pname      =  token       ; Formal parameter name

   'fname' is the name of the predicate.

   'pname' is the name of a formal parameter which may appear in the
   predicate body, and which is replaced by some supplied value when the
   predicate is invoked.