One document matched: draft-ietf-conneg-feature-syntax-00.txt
IETF media feature registration WG Graham Klyne
INTERNET-DRAFT Content Technologies/5GM
Category: Work-in-progress September 1998
Expires: March 1999
A syntax for describing media feature sets
<draft-ietf-conneg-feature-syntax-00.txt>
Status of this memo
This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other
documents at any time. It is inappropriate to use Internet-Drafts
as reference material or to cite them other than as ``work in
progress''.
To view the entire list of current Internet-Drafts, please check
the "1id-abstracts.txt" listing contained in the Internet-Drafts
Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net
(Northern Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au
(Pacific Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US
West Coast).
[[INTENDED STATUS:
This document specifies an Internet standards track protocol for
the Internet community, and requests discussion and suggestions for
improvements. Please refer to the current edition of the "Internet
Official Protocol Standards" (STD 1) for the standardization state
and status of this protocol. Distribution of this memo is
unlimited.]]
Copyright Notice
Copyright (C) The Internet Society 1998. All Rights Reserved.
Abstract
A number of Internet application protocols have a need to provide
content negotiation for the resources with which they interact [1].
A framework for such negotiation is described in [2]. Part of this
framework is a way to describe the range of media features which
can be handled by the sender, recipient or document transmission
format of a message. A format for a vocabulary of individual media
features and procedures for registering media features are
presented in [3].
Klyne Work-in-progress [Page 1]
RFC nnnn A syntax for describing media feature sets
September 1998
This document introduces and describes a syntax that can be used to
define feature sets which are formed from combinations and
relations involving individual media features. Such feature sets
are used to describe the media feature handling capabilities of
message senders, recipients and file formats.
This document also outlines an algorithm for feature set matching.
Table of contents
1. Introduction.............................................3
1.1 Structure of this document ...........................4
1.2 Document terminology and conventions .................4
1.3 Discussion of this document ..........................4
1.4 Amendment history ....................................5
1.5 Unfinished business ..................................6
2. Content feature terminology and definitions..............6
3. Media feature combinations and capabilities..............6
3.1 Media features .......................................6
3.2 Media feature collections and sets ...................7
3.3 Media feature set descriptions .......................7
3.4 Media feature combination scenario ...................8
3.4.1 Data resource options............................8
3.4.2 Recipient capabilities...........................8
3.4.3 Combined options.................................9
3.5 Feature set predicates ...............................9
4. Feature set representation...............................10
4.1 Textual representation of predicates .................11
4.2 Named and auxiliary predicates .......................12
4.2.1 Defining a named predicate.......................12
4.2.2 Invoking named predicates........................13
4.2.3 Auxiliary predicates in a filter.................13
4.3 Feature set definition examples ......................14
4.3.1 Single predicate.................................14
4.3.2 Predicate with auxiliary predicate...............14
5. Processing feature set descriptions......................15
5.1 Matching feature sets ................................15
5.1.1 Feature set matching strategy....................17
5.1.2 Formulating the goal predicate...................17
5.1.3 Replace set expressions..........................18
5.1.4 Replace comparisons and logical negations........18
5.1.5 Conversion to canonical form.....................20
5.1.6 Grouping of feature predicates...................20
5.1.7 Merge single-feature constraints.................21
5.1.7.1 Rules for simplifying ordered values 21
5.1.7.2 Rules for simplifying unordered values 22
5.2 Effect of named predicates ...........................22
5.3 Unit designations ....................................22
5.4 Unknown feature value data types .....................24
Klyne Work-in-progress [Page 2]
RFC nnnn A syntax for describing media feature sets
September 1998
5.5 Worked example .......................................24
5.6 Algorithm source code ................................24
6. Security considerations..................................24
7. Copyright................................................25
8. Acknowledgements.........................................26
9. References...............................................26
10. Author's address........................................28
1. Introduction
A number of Internet application protocols have a need to provide
content negotiation for the resources with which they interact [1].
A framework for such negotiation is described in [2]. A part of
this framework is a way to describe the range of media features
which can be handled by the sender, recipient or document
transmission format of a message.
Descriptions of media feature capabilities need to be based upon
some underlying vocabulary of individual media features. A format
for such a vocabulary and procedures for registering media features
within this vocabulary are presented in [3].
This document defines a syntax that can be used to describe feature
sets which are formed from combinations and relations involving
individual media features. Such feature sets are used to describe
the media handling capabilities of message senders, recipients and
file formats.
This document also outlines an algorithm for feature set matching.
The feature set syntax is built upon the principle of using feature
set predicates as "mathematical relations" which define constraints
on feature handling capabilities. This allows that the same form
of feature set expression can be used to describe sender, receiver
and file format capabilities. This has been loosely modelled on
the way that relational databases use Boolean expresions to
describe a set of result values, and a syntax that is based upon
LDAP search filters.
Klyne Work-in-progress [Page 3]
RFC nnnn A syntax for describing media feature sets
September 1998
1.1 Structure of this document
The main part of this memo addresses the following main areas:
Section 2 introduces and references some terms which are used with
special meaning.
Section 3 introduces the concept of describing media handling
capabilities as combinations of possible media features, and the
idea of using Boolean expressions to express such combinations.
Section 4 contains a description of a syntax for describing feature
sets based on the previously-introduced idea of Boolean expressions
used to describe media feature combinations.
Section 5 discusses some feature set description processing issues,
including a description of an algorithm for feature set matching.
1.2 Document terminology and conventions
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [RFC2119].
NOTE: Comments like this provide additional nonessential
information about the rationale behind this document.
Such information is not needed for building a conformant
implementation, but may help those who wish to understand
the design in greater depth.
1.3 Discussion of this document
Discussion of this document should take place on the content
negotiation and media feature registration mailing list hosted by
the Internet Mail Consortium (IMC):
Please send comments regarding this document to:
ietf-medfree@imc.org
To subscribe to this list, send a message with the body 'subscribe'
to "ietf-medfree-request@imc.org".
To see what has gone on before you subscribed, please see the
mailing list archive at:
http://www.imc.org/ietf-medfree/
Klyne Work-in-progress [Page 4]
RFC nnnn A syntax for describing media feature sets
September 1998
1.4 Amendment history
00a 28-Sep-1998 This memo created to contain a description of the
syntax-related features from a previous.draft "An
algebra for describing media feature sets".
Theoretical background material is replaced by a
more practically oriented introduction to the
concepts, and references to ASN.1 representation
have been removed.
Revision history of "An algebra for describing media feature sets":
00a 11-Mar-1998 Document initially created.
01a 05-May-1998 Mainly-editorial revision of sections describing
the feature types and algebra. Added section on
indicating preferences. Added section describing
feature predicate syntax. Added to security
considerations (based on fax negotiation scenarios
draft).
01b 25-Jun-1998 New Internet draft boilerplate in 'status'
preface. Review and rationalization of sections
on feature combinations. Added numeric
expressions, named predicates and auxiliary
predicates as options in the syntax. Added
examples of text string predicate representation.
02a 08-Jul-1998 Added chapter on protocol processing
considerations, and in particular outlined an
algorithm for feature set matching. Added
restrictions to the form of arithmetic expression
to allow deterministic feature set matching.
03a 27-Jul-1998 Simplified feature set handling by removing
options for expressions on the RHS of feature
comparison expressions. Syntax elements have been
added as placeholders for possible future
extensions in this area; examples have been
adjusted accordingly, and the feature set matching
algorithm greatly simplified. Add simple unit
designations.
Klyne Work-in-progress [Page 5]
RFC nnnn A syntax for describing media feature sets
September 1998
1.5 Unfinished business
. Discuss determination of qvalues in the feature set matching
algorithm.
. Use of unknown data types for feature values (section 5.3)
. Add worked example and source code for feature matching
implementation.
2. Content feature terminology and definitions
Feature Collection
is a collection of different media features and
associated values. This might be viewed as describing a
specific rendering of a specific instance of a document
or resource by a specific recipient.
Feature Set
is a set of zero, one or more feature collections.
Feature set predicate
A function of an arbitrary feature collection value which
returns a Boolean result. A TRUE result is taken to mean
that the corresponding feature collection belongs to some
set of media feature handling capabilities defined by
this predicate.
Other terms used in this draft are defined in [2].
3. Media feature combinations and capabilities
3.1 Media features
This memo assumes that individual media feature values are simple
atomic values:
. Boolean values.
. Enumerated values.
. Text string values (treated as atomic entities, like enumerated
value tokens).
. Numeric values (Integer or rational).
Klyne Work-in-progress [Page 6]
RFC nnnn A syntax for describing media feature sets
September 1998
These values all have the property that they can be compared for
equality ('='), and that numeric and ordered enumeration values can
be compared for less-than and greater-than relationship ('<=',
'>='). These basic comparison operations are used as the primitive
building blocks for more comprehensive capability expressions.
3.2 Media feature collections and sets
Any single media feature value can be thought of as just one
component of a feature collection that describes some instance of a
resource (e.g. a printed document, a displayed image, etc.). Such
a feature collection consists of a number of media feature tags
(each per [3]) and associated feature values.
A feature set is a set containing a number of feature collections.
Thus, a feature set can describe a number of different data
resource instances. These can correspond to different treatments
of a single data resource (e.g. different resolutions used for
printing a given document), a number of different data resources
subjected to a common treatment (e.g. the range of different images
that can be rendered on a given display), or some combination of
these (see examples below).
Thus, a description of a feature set can describe the capabilities
of a data resource or some entity that processes or renders a data
resource.
3.3 Media feature set descriptions
A feature set may be unbounded. For example, in principle, there
is no limit on the number of different documents that may be output
using a given printer. But for practical use, a feature set
description must be finite.
The general approach to describing feature sets is to start from
the assumption that anything is possible; i.e. the feature set
contains all possible document instances (feature collections).
Then constraints are applied that progressively remove document
instances from this set; e.g. for a monochrome printer, all
document instances that use colour are removed, or for a document
that must be rendered at some minimum resolution, all document
instances with lesser resolutions are removed from the set. The
mechanism used to remove document instances from the set is the
mathematical idea of a "relation"; i.e. a Boolean function (a
"predicate") that takes a feature collection parameter and returns
a Boolean value that is TRUE if the feature collection describes an
acceptable document instance, or FALSE if it describes one that is
excluded.
Klyne Work-in-progress [Page 7]
RFC nnnn A syntax for describing media feature sets
September 1998
P(C)
P(C) = TRUE <- : -> P(C) = FALSE
:
+----------:----------+ This box represents some
| : | set of feature collections (C)
| Included : Excluded | that is constrained by the
| : | predicate P.
+----------:----------+
:
The result of applying a series of such constraints is a smaller
set of feature collections that represent some media handling
capability. Where the individual constraints are represented by
predicates that each describe some media handling capability, the
combined effect of these constraints is some subset of the
individual constraint capabilities that can be represented by a
predicate that is the logical-AND of the individual constraint
predicates.
3.4 Media feature combination scenario
3.4.1 Data resource options
The following expression uses the syntax introduced later to
describe a data resource that can be displayed either:
(a) as a 750x500 pixel image using 15 colours, or
(b) at 150dpi on an A4 page.
(| (& (pix-x=750) (pix-y=500) (color=15) )
(& (dpi>=150) (papersize=iso-A4) ) )
3.4.2 Recipient capabilities
The following expression describes a receiving system that has:
(a) a screen capable of displaying 640*480 pixels and 16 million
colours (24 bits per pixel), 800*600 pixels and 64 thousand
colours (16 bits per pixel) or 1024*768 pixels and 256 colours
(8 bits per pixel), or
(b) a printer capable of rendering 300dpi on A4 paper.
Note that this expression says noting about the colour or grey-
scale capabilities of the printer. In the scheme presented here,
it is presumed to be unconstrained in this respect (or, more
realistically, any such constraints are handled out-of-band by
anyone sending to this recipient).
Klyne Work-in-progress [Page 8]
RFC nnnn A syntax for describing media feature sets
September 1998
(| (& (| (& (pix-x<=640) (pix-y<=480) (color<=16777216) )
(& (pix-x<=800) (pix-y<=600) (color<=65535) )
(& (pix-x<=1024) (pix-y<=768) (color<=256) ) )
(media=screen) )
(& (dpi=300)
(media=stationery) (papersize=iso-A4) ) )
3.4.3 Combined options
The following example describes the range of document
representations available when the resource described in the first
example above is sent to the recipient described in the second
example. This is the result of combining their capability feature
sets:
(| (& (pix-x=750) (pix-y=500) (color=15) )
(& (dpi=300) (media=stationery) (papersize=iso-A4) ) )
The feature set described by this expression is the intersection of
the sets described by the previous two capability expressions.
3.5 Feature set predicates
There are many ways of representing a predicate. The ideas in this
memo were inspired by the programming language Prolog [5], and its
use of predicates to describe sets of objects.
For the purpose of media feature description in networked
application protocols, the format used for LDAP search filters
[7,8] has been adopted, because it is a good match for the
requirements of capability identification, and has a very simple
structure that is easy to parse and process.
Observe that a feature collection is similar to a directory entry,
in that it consists of a collection of named values. Further, the
semantics of the mechanism for selecting feature collections from a
feature set is in many respects similar to selection of directory
entries from a directory.
A feature set predicate used to describe media handling
capabilities is implicitly applied to some feature collection.
Within the predicate, members of the feature collection are
identified by their feature tags, and are compared with known
feature values. (Compare with the way an LDAP search filter is
applied to a directory entry, whose members are identified by
attribute type names, and compared with known attribute values.)
Klyne Work-in-progress [Page 9]
RFC nnnn A syntax for describing media feature sets
September 1998
Differences between directory selection (per [7]) and feature set
selection are:
. Directory selection provides substring-, approximate- and
extensible- matching for attribute values. Directory selection
may also be based on the presence of an attribute without regard
to its value.
. Directory selection provides for matching rules that test for the
presence or absence of a named attribute type.
. Directory selection provides for matching rules which are
dependent upon the declared data type of an attribute value.
. Feature selection provides for the association of a quality value
with a feature predicate as a way of ranking the selected value
collections.
The idea of substring matching does not seem to be relevant to
feature set selection, and is excluded from these proposals.
Testing for the presence of a feature may be useful in some
circumstances, but does not sit comfortably within the semantic
framework. Feature sets are described by implied universal
quantification over predicates, and the absence of reference to a
given feature means the set is not constrained by that feature.
Against this, it is difficult to define what might be meant by
"presence" of a feature, so the "test for presence" option is not
included in these proposals. An effect similar to testing for the
presence of a feature can be achieved by a Boolean-valued feature.
The idea of extensible matching and matching rules dependent upon
data types are facets of a problem not addressed by this memo, but
which do not necessarily affect the feature selection syntax. An
aspect which might have a bearing on the syntax would be a
requirement to specify a matching rule explicitly as part of a
selection expression.
4. Feature set representation
The foregoing sections have described a framework for defining
feature sets with predicates applied to feature collections. This
section presents a concrete representation for feature set
predicates.
Klyne Work-in-progress [Page 10]
RFC nnnn A syntax for describing media feature sets
September 1998
4.1 Textual representation of predicates
The text representation of a feature set is based on RFC 2254 "The
String Representation of LDAP Search Filters" [8], excluding those
elements not relevant to feature set selection (discussed above),
and adding elements specific to feature set selection (e.g. options
to associate quality values with predicates).
The format of a feature predicate is defined by the production for
"filter" in the following, using the syntax notation and core rules
of [10]:
filter = "(" filtercomp *( ";" parameter ) )"
parameter = "q" "=" qvalue
/ ext-param "=" ext-value
qvalue = ( "0" [ "." 0*3DIGIT ] )
/ ( "1" [ "." 0*3("0") ] )
ext-param = ALPHA *( ALPHA / DIGIT / "-" )
ext-value = <parameter value, according to the named parameter>
filtercomp = and / or / not / item
and = "&" filterlist
or = "|" filterlist
not = "!" filter
filterlist = 1*filter
item = simple / set / ext-pred
set = attr "=" "[" setentry *( "," setentry ) "]"
setentry = value "/" range
range = value ".." value
simple = attr filtertype value
filtertype = equal / greater / less
equal = "="
greater = ">="
less = "<="
attr = ftag
value = fvalue
ftag = <Feature tag, as defined in [3]>
fvalue = number / token / string
number = integer / rational
integer = 1*DIGIT
rational = 1*DIGIT "." 1*DIGIT
token = ALPHA *( ALPHA / DIGIT / "-" )
string = DQUOTE *(%x20-21 / %x23-7E) DQUOTE
; quoted string of SP and VCHAR without DQUOTE
ext-pred = <Extension constraint predicate, not defined here>
(Subject to constraints imposed by the protocol that carries a
feature predicate, whitespace characters may appear between any
pair of syntax elements or literals that appear on the right hand
side of these productions.)
Klyne Work-in-progress [Page 11]
RFC nnnn A syntax for describing media feature sets
September 1998
As described, the syntax permits parameters (including quality
values) to be attached to any "filter" value in the predicate (not
just top-level values). Only top-level quality values are
recognized. If no explicit quality value is given, a value of
'1.0' is applied.
NOTE
The flexible approach to quality values and other
parameter values in this syntax has been adopted for two
reasons: (a) to make it easy to combine separately
constructed feature predicates, and (b) to provide an
extensible tagging mechanism for possible future use (for
example, to incorporate a conceivable requirement to
explicitly specify a matching rule).
4.2 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.
[[[TODO: Decide how to treat named predicates. Support
for named predicates in the capability syntax has not
(currently) been made a requirement. However, its
inclusion as an option may be useful for publication
purposes, even if not used in actual protocol
elements.]]]
4.2.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.
Klyne Work-in-progress [Page 12]
RFC nnnn A syntax for describing media feature sets
September 1998
'filter' is the predicate body. It may contain references to the
formal parameters, and may also contain references to feature tags
and other values defined in the environment in which the predicate
is invoked. References to formal parameters may appear anywhere
where a reference to a feature tag ('ftag') is permitted by the
syntax for 'filter'.
The only specific mechanism defined by this memo for introducing a
named predicate into a feature set definition is the "auxiliary
predicate" described later. Specific negotiating protocols or
other memos may define other mechanisms.
NOTE
There has been some suggestion of creating a registry for
feature sets as well as individual feature values. Such
a registry might be used to introduce named predicates
corresponding to these feature sets into the environment
of a capability assertion. Further discussion of this
idea is beyond the scope of this memo.
4.2.2 Invoking named predicates
Assuming a named predicate has been introduced into the environment
of some other predicate, it can be invoked by a filter 'ext-pred'
of the form:
ext-pred = fname *param
param = expr
The number of parameters must match the definition of the named
predicate that is invoked.
4.2.3 Auxiliary predicates in a filter
A auxiliary predicate is attached to a filter definition by the
following extension to the "filter" syntax:
filter =/ "(" filtercomp *( ";" parameter ) ")"
"where" 1*( named-pred ) "end"
The named predicates introduced by "named-pred" are visible from
the body of the "filtercomp" of the filter to which they are
attached, but are not visible from each other. They all have
access to the same environment as "filter", plus their own formal
parameters. (Normal scoping rules apply: a formal parameter with
the same name as a value in the environment of "filter" effectively
hides the environment value from the body of the predicate to which
it applies.)
Klyne Work-in-progress [Page 13]
RFC nnnn A syntax for describing media feature sets
September 1998
NOTE
Recursive predicates are not permitted. The scoping
rules should ensure this.
4.3 Feature set definition examples
The following sub-sections give examples of feature predicates that
describes a number of image size and resolution combinations.
4.3.1 Single predicate
(| (& (Pix-x=1024)
(Pix-y=768)
(| (& (Res-x=150) (Res-y=150) )
(& (Res-x=150) (Res-y=300) )
(& (Res-x=300) (Res-y=300) )
(& (Res-x=300) (Res-y=600) )
(& (Res-x=600) (Res-y=600) ) )
(& (Pix-x=800)
(Pix-y=600)
(| (& (Res-x=150) (Res-y=150) )
(& (Res-x=150) (Res-y=300) )
(& (Res-x=300) (Res-y=300) )
(& (Res-x=300) (Res-y=600) )
(& (Res-x=600) (Res-y=600) ) ) ;q=0.9
(& (Pix-x=640)
(Pix-y=480)
(| (& (Res-x=150) (Res-y=150) )
(& (Res-x=150) (Res-y=300) )
(& (Res-x=300) (Res-y=300) )
(& (Res-x=300) (Res-y=600) )
(& (Res-x=600) (Res-y=600) ) ) ;q=0.8
4.3.2 Predicate with auxiliary predicate
(| (& (Pix-x=1024) (Pix-y=768) (Res Res-x Res-y) )
(& (Pix-x=800) (Pix-y=600) (Res Res-x Res-y) );q=0.9
(& (Pix-x=640) (Pix-y=480) (Res Res-x Res-y) );q=0.8 )
where
(Res Res-x Res-y) :-
(| (& (Res-x=150) (Res-y=150) )
(& (Res-x=150) (Res-y=300) )
(& (Res-x=300) (Res-y=300) )
(& (Res-x=300) (Res-y=600) )
(& (Res-x=600) (Res-y=600) ) )
end
Klyne Work-in-progress [Page 14]
RFC nnnn A syntax for describing media feature sets
September 1998
Note that the formal parameters of "Res", "Res-x" and "Res-y",
prevent the body of the named predicate from referencing similarly-
named feature values.
5. Processing feature set descriptions
This section addresses some issues that may arise when using
feature set predicates as part of some content negotiation or file
selection protocol.
5.1 Matching feature sets
Matching a feature set to some given feature collection is
esentially very straightforward: the feature set predicate is
simply evaluated for the given feature collection, and the result
(TRUE or FALSE) indicates whether the feature collection matches
the capabilities, and the associated quality value can be used for
selecting among alternative feature collections.
Matching a feature set to some other feature set is less
straightforward. Here, the problem is to determine whether or not
there is at least one feature collection that matches both feature
sets (e.g. is there an overlap between the feature capabilities of
a given file format and the feature capabilities of a given
recipient?)
This feature set matching is accomplished by logical manipulation
of the predicate expressions as described in the following
sections.
For this procedure to work reliably, the predicates must be reduced
to a canonical form. One such form is "clausal form", and
procedures for converting general expressions in predicate calculus
are given in [5] (section 10.2), [11] (section 2.13), [12] (chapter
4) and [13] (section 5.3.2).
"Clausal form" for a predicate is similar to "conjunctive normal
form" for a proposition, which consists of a conjunction (logical
ANDs) of disjunctions (logical ORs). A related form that is better
suited to feature set matching is "disjunctive normal form", which
consists of a logical disjunction (OR) of conjunctions (ANDs). In
this form, it is sufficient to show that at least one of the
disjunctions can be satisfied by some feature collection.
Klyne Work-in-progress [Page 15]
RFC nnnn A syntax for describing media feature sets
September 1998
A syntax for disjunctive normal form is:
filter = orlist
orlist = "(" "|" andlist ")" / term
andlist = "(" "&" termlist ")" / term
termlist = 1*term
term = "(" "!" simple ")" / simple
where "simple" is as described previously in section 6.1. Thus,
the canonicalized form has at most three levels: an outermost
"(|...)" disjunction of "(&...)" conjunctions of possibly negated
feature value tests.
NOTE (a theoretical diversion):
Is this consideration of "clausal form" really required?
After all, the feature predicates are just Boolean
expressions, aren't they?
Well, no. A feature predicate is a Boolean expression
containing primitive feature value tests (comparisons),
represented by 'item' in the feature predicate syntax.
If these tests could all be assumed to be independently
TRUE or FALSE, then each could be regarded as an atomic
proposition, and the whole predicate could be dealt with
according to the (relatively simple) rules of
Propositional Calculus.
But, in general, the same feature tag may appear in more
than one predicate 'item', so the tests cannot be
regarded as independent. Indeed, interdependence is
needed in any meaningful application of feature set
matching, and it is important to capture these
dependencies (e.g. does the set of resolutions that a
sender can supply overlap the set of resolutions that a
recipient can handle?). Thus, we have to deal with
elements of the Predicate Calculus, with its additional
rules for algebraic manipulation.
This section aims to show that these additional rules are
more unfamiliar than complicated. In practice, the way
that feature predicates are constructed and used actually
avoids some of the complexity of dealing with fully-
generalized Predicate Calculus.
Klyne Work-in-progress [Page 16]
RFC nnnn A syntax for describing media feature sets
September 1998
5.1.1 Feature set matching strategy
The overall strategy for matching feature sets, expanded in the
following sections, is:
1. Formulate the feature set match hypothesis.
2. Replace "set" expressions with equivalent comparisons.
3. Eliminate logical negations, and express all feature comparisons
in terms of just four comparison operators
4. Reduce the hypothesis to canonical disjunctive normal form (a
disjunction of conjunctions).
5. For each of the conjunctions, attempt to show that it can be
satisfied by some feature collection. Any that cannot be
satisfied are discarded.
5.1 Separate the feature value tests into independent groups,
such that each group contains tests involving just one
feature value. That is: no group contains a predicate
involving any feature tag that also appears in a predicate
in some other group.
5.2 For each group, merge the various constraints to a minimum
form. This process either yields a reduced expression for
the allowable range of feature values, or an indication that
no value can satisfy the constraints (in which case the
corresponding conjucntion can never be satisfied).
6. If the remaining disjunction is non-empty, then the constraints
are shown to be satisfiable. Further, it can be used as a
statement of the resulting feature set for possible further
matching operations.
5.1.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'?
Klyne Work-in-progress [Page 17]
RFC nnnn A syntax for describing media feature sets
September 1998
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.1.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.1.4 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 and not related to '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.)
Klyne Work-in-progress [Page 18]
RFC nnnn A syntax for describing media feature sets
September 1998
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:
(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.
Klyne Work-in-progress [Page 19]
RFC nnnn A syntax for describing media feature sets
September 1998
5.1.5 Conversion to canonical form
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 )
The result is a "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 7.1.4. 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.1.6 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').
Klyne Work-in-progress [Page 20]
RFC nnnn A syntax for describing media feature sets
September 1998
5.1.7 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
current conjunction is removed from the feature set description.
Otherwise, the resulting description is a minimal form of the
particular conjunction of the feature set definition.
5.1.7.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
Klyne Work-in-progress [Page 21]
RFC nnnn A syntax for describing media feature sets
September 1998
5.1.7.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
(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
[[[TODO: model the above system to confirm that it is complete and
does indeed work properly in all cases.]]]
5.2 Effect of named predicates
The preceding procedures can be extended to deal with named
predicates simply by instantiating (i.e. substituting) the
predicates wherever they are invoked, before performing the
conversion to disjunctive normal form. In the absence of recursive
predicates, this procedure is guaranteed to terminate.
When substituting the body of a precdicate at its point of
invocation, instances of formal parameters within the predicate
body must be replaced by the corresponding actual parameter from
the point of invocation.
5.3 Unit designations
In some exceptional cases, there may be differing conventions for
the units of measurement of a given feature. For example,
resolution is commonly expressed as dots per inch (dpi) or dots per
centimetre (dpcm) in different applications (e.g. printing vs
faxing).
Klyne Work-in-progress [Page 22]
RFC nnnn A syntax for describing media feature sets
September 1998
In such cases, a unit designator may be appended to a feature value
according to the conventions indicated below (see also [3]). These
considerations apply only to features with numeric values.
Every feature tag has a standard unit of measurement. Any
expression of a feature value that uses this unit is given without
a unit designation -- this is the normal case. When the feature
value is expressed in some other unit, a unit designator is
appended to the numeric feature value.
The registration of a feature tag indicates the standard unit of
measurement for a feature, and also any alternate units and
corresponding unit designators that may be used, according to [3].
Thus, if the standard unit of measure for resolution is 'dpcm',
then the feature predicate '(res=200)' would be used to indicate a
resolution of 200 dots-per-centimetre, and '(res=72dpi)' might be
used to indicate 72 dots-per-inch.
Unit designators are accommodated by the following extension to the
feature predicate syntax:
fvalue /= number *WSP token
When performing feature set matching, feature comparisons with and
without unit designators, or feature comparisons with different
unit designators, are treated as if they were different features.
Thus, the feature predicate '(res=200)' would not, in general, fail
to match with the predicate '(res=200dpi)'.
NOTE:
A protocol processor with specific knowledge of the
feature and units concerned might recognize the
relationship between the feature predicates in the above
example, and fail to match these predicates.
This appears to be a natural behaviour in this simple
example, but can cause additional complexity in more
general cases. Accordingly, this is not considered to be
required or normal behaviour. It is presumed that in
general, the application concerned will ensure consistent
feature processing by adopting a consistent unit for any
given feature.
Klyne Work-in-progress [Page 23]
RFC nnnn A syntax for describing media feature sets
September 1998
5.4 Unknown feature value data types
[[Discuss issues of specific features which may have feature-
specific comparison rules, as opposed to generic Booleans,
enumerations, strings and numbers which use comparison rules
independent of the feature concerned.]]
[[[TODO]]]
5.5 Worked example
[[[TODO]]]
5.6 Algorithm source code
[[[TODO]]]
6. Security considerations
Some security considerations for content negotiation are raised in
[1,2,3].
The following are primary security concerns for capability
identification mechanisms:
. Unintentional disclosure of private information through the
announcement of capabilities or user preferences.
. Disruption to system operation caused by accidental or malicious
provision of incorrect capability information.
. Use of a capability identification mechanism might be used to
probe a network (e.g. by identifying specific hosts used, and
exploiting their known weaknesses).
Klyne Work-in-progress [Page 24]
RFC nnnn A syntax for describing media feature sets
September 1998
The most contentious security concerns are raised by mechanisms
which automatically send capability identification data in response
to a query from some unknown system. Use of directory services
(based on LDAP [7], etc.) seem to be less problematic because
proper authentication mechanisms are available.
Mechanisms which provide capability information when sending a
message are less contentious, presumably because some intention can
be inferred that person whose details are disclosed wishes to
communicate with the recipient of those details. This does not,
however, solve problems of spoofed supply of incorrect capability
information.
The use of format converting gateways may prove problematic because
such systems would tend to defeat any message integrity and
authenticity checking mechanisms that are employed.
7. Copyright
Copyright (C) The Internet Society 1998. All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain
it or assist in its implementation may be prepared, copied,
published and distributed, in whole or in part, without restriction
of any kind, provided that the above copyright notice and this
paragraph are included on all such copies and derivative works.
However, this document itself may not be modified in any way, such
as by removing the copyright notice or references to the Internet
Society or other Internet organizations, except as needed for the
purpose of developing Internet standards in which case the
procedures for copyrights defined in the Internet Standards process
must be followed, or as required to translate it into languages
other than English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on
an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET
ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Klyne Work-in-progress [Page 25]
RFC nnnn A syntax for describing media feature sets
September 1998
8. Acknowledgements
My thanks to Larry Masinter for demonstrating to me the breadth of
the media feature issue, and encouraging me to air my early ideas.
Early discussions of ideas on the IETF-HTTP and IETF-FAX discussion
lists led to useful inputs also from Koen Holtman, Ted Hardie and
Dan Wing.
The debate later moved to the IETF conneg WG mailing list, where Al
Gilman was particularly helpful in helping me to refine the feature
set algebra. Ideas for dealing with preferences and specific units
were suggested by Larry Masinter.
This work was supported by Content Technologies Ltd and 5th
Generation Messaging Ltd.
9. References
[1] "Scenarios for the Delivery of Negotiated Content"
T. Hardie, NASA Network Information Center
Internet draft: <draft-ietf-http-negotiate-scenario-02.txt>
Work in progress, November 1997.
[2] "Requirements for protocol-independent content negotiation"
G. Klyne, Integralis Ltd.
Internet draft: <draft-ietf-conneg-requirements-00.txt>
Work in progress, March 1998.
[3] "Media Feature Tag Registration Procedure"
Koen Holtman, TUE
Andrew Mutz, Hewlett-Packard
Ted Hardie, NASA
Internet draft: <draft-ietf-conneg-feature-reg-03.txt>
Work in progress, July 1998.
[4] "Notes on data structuring"
C. A. R. Hoare,
in "Structured Programming"
Academic Press, APIC Studies in Data Processing No. 8
ISBN 0-12-200550-3 / 0-12-200556-2
1972.
[5] "Programming in Prolog" (2nd edition)
W. F. Clocksin and C. S. Mellish,
Springer Verlag
ISBN 3-540-15011-0 / 0-387-15011-0
1984.
Klyne Work-in-progress [Page 26]
RFC nnnn A syntax for describing media feature sets
September 1998
[6] "Media Features for Display, Print, and Fax"
Larry Masinter, Xerox PARC
Koen Holtman, TUE
Andrew Mutz, Hewlett-Packard
Dan Wing, Cisco Systems
Internet draft: <draft-masinter-media-features-02.txt>
Work in progress, January 1998.
[7] RFC 2251, "Lightweight Directory Access Protocol (v3)"
M. Wahl, Critical Angle Inc.
T. Howes, Netscape Communications Corp.
S. Kille, Isode Limited
December 1997.
[8] RFC 2254, "The String Representation of LDAP Search Filters"
T. Howes, Netscape Communications Corp.
December 1997.
[9] RFC 2068, "Hyptertext Transfer Protocol -- HTTP/1.1"
R. Fielding, UC Irvine
J. Gettys,
J. Mogul, DEC
H. Frytyk,
T. Berners-Lee, MIT/LCS
January 1997.
[10] RFC 2234, "Augmented BNF for Syntax Specifications: ABNF"
D. Crocker (editor), Internet Mail Consortium
P. Overell, Demon Internet Ltd.
November 1997.
[11] "Logic, Algebra and Databases"
Peter Gray
Ellis Horwood Series: Computers and their Applications
ISBN 0-85312-709-3/0-85312-803-3 (Ellis Horwood Ltd)
ISBN 0-470-20103-7/0-470-20259-9 (Halstead Press)
1984.
[12] "Elementary Logics: A procedural Perspective
Dov Gabbay
Prentice Hall, Series in computer science
ISBN 0-13-726365-1
1998.
[13] "Logic and its Applications"
Edmund Burk and Eric Foxley
Prentice Hall, Series in computer science
ISBN 0-13-030263-5
1996.
Klyne Work-in-progress [Page 27]
RFC nnnn A syntax for describing media feature sets
September 1998
10. Author's address
Graham Klyne
Content Technologies Ltd. 5th Generation Messaging Ltd.
Forum 1 5 Watlington Street
Station Road Nettlebed
Theale Henley-on-Thames
Reading, RG7 4RA RG9 5AB
United Kingdom United Kingdom.
Telephone: +44 118 930 1300 +44 1491 641 641
Facsimile: +44 118 930 1301 +44 1491 641 611
E-mail: GK@ACM.ORG
Klyne Work-in-progress [Page 28]
| PAFTECH AB 2003-2026 | 2026-04-21 20:37:34 |