IETF media feature registration WG Graham Klyne
Internet draft Content Technologies/5GM
7 August 1998
Expires: February 1999
An algebra for describing media feature sets
<draft-ietf-conneg-feature-algebra-03.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).
Copyright (C) 1998, The Internet Society
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].
This document describes an algebra and 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.
Klyne [Page 1]
Internet draft 5 August 1998
An algebra for describing media feature sets
Table of contents
1. Introduction.............................................3
1.1 Structure of this document ...........................4
1.2 Discussion of this document ..........................4
1.3 Amendment history ....................................5
1.4 Unfinished business ..................................5
2. Terminology and definitions..............................6
3. Media feature values.....................................6
3.1 Complexity of feature algebra ........................7
3.2 Sufficiency of simple types ..........................7
3.2.1 Unstructured data types..........................8
3.2.2 Cartesian product................................8
3.2.3 Discriminated union..............................8
3.2.4 Array............................................9
3.2.5 Powerset.........................................9
3.2.6 Sequence.........................................9
4. Feature set predicates...................................10
4.1 An algebra for data file format selection ............11
4.1.1 Describing feature sets..........................12
4.1.1.1 Feature value ranges 12
4.1.1.2 Feature value combinations 13
4.1.1.3 Using meta-features to group features 14
4.1.2 Content, sender and recipient capabilities.......15
4.2 Conclusion and proposal ..............................15
5. Indicating preferences...................................16
5.1 Combining preferences ................................16
5.2 Representing preferences .............................17
6. Feature set representation...............................18
6.1 Textual representation of predicates .................19
6.2 Named and auxiliary predicates .......................21
6.2.1 Defining a named predicate.......................21
6.2.2 Invoking named predicates........................22
6.2.3 Auxiliary predicates in a filter.................22
6.3 Feature set definition examples ......................22
6.3.1 Single predicate.................................22
6.3.2 Predicate with auxiliary predicate...............23
6.4 ASN.1 representation .................................24
7. Content negotiation protocol processing..................24
7.1 Matching feature sets ................................24
7.1.1 Feature set matching strategy....................26
7.1.2 Formulating the problem..........................27
7.1.3 Replace set expressions..........................27
7.1.4 Replace comparisons and logical negations........27
7.1.5 Conversion to canonical form.....................29
7.1.6 Grouping of feature predicates...................30
7.1.7 Merge single-feature constraints.................30
7.1.7.1 Rules for simplifying ordered values 30
7.1.7.2 Rules for simplifying unordered values 31
7.2 Effect of named predicates ...........................32
Klyne [Page 2]
Internet draft 5 August 1998
An algebra for describing media feature sets
7.3 Unit designations ....................................32
7.4 Unknown feature value data types .....................33
7.5 Worked example .......................................33
7.6 Algorithm source code ................................33
8. Security considerations..................................33
9. Copyright................................................35
10. Acknowledgements........................................35
11. References..............................................36
12. Author's address........................................38
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
are presented in [3].
This document defines an algebra which 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 a syntax for describing feature sets,
and an algorithm for feature set matching.
The feature set algebra is built around the principle of using
feature set predicates as "mathematical relations" which define
constraints on feature handling capabilities. The idea is 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 the Prolog programming language uses Horn
Clauses to describe a set of result values.
In developing the algebra, examples are given using notation drawn
from the Prolog programming language. Later, a syntax for
expressing feature predicates is suggested, based on LDAP search
filters. Finally, an algorithm for feature set matching is
described.
Klyne [Page 3]
Internet draft 5 August 1998
An algebra for describing media feature sets
1.1 Structure of this document
The main part of this draft addresses the following main areas:
Section 2 introduces and references some terms which are used with
special meaning.
Section 3 discusses constraints on the data types allowed for
individual media feature values.
Section 4 introduces and describes the algebra used to construct
feature set descriptions with expressions containing media
features. The first part of this section contains a development of
the ideas, and the second part contains the conclusions and
proposed algebra.
Section 5 introduces and describes extensions to the algebra for
indicating preferences between different feature sets.
Section 6 contains a description of recommended representations for
describing feature sets based on the previously-described algebra.
Section 7 discusses some feature-related protocol processing
issues, including a description of an algorithm for feature set
matching.
1.2 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/
1.3 Amendment history
00a 11-Mar-1998
Document initially created.
Klyne [Page 4]
Internet draft 5 August 1998
An algebra for describing media feature sets
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.
1.4 Unfinished business
. Array values: are they needed? (section 3.2.4)
. Discuss determination of qvalues in the feature set matching
algorithm.
. Use of unknown data types for feature values (section 7.3)
. Add source code for feature matching implementation.
. Should ASN.1 representation be pursued? If so, should it be
aligned with LDAP filter representation? (section 6.5)
Klyne [Page 5]
Internet draft 5 August 1998
An algebra for describing media feature sets
2. 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 values
This document 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
More complex media feature values might be accommodated, but they
would (a) be undesirable because they would complicate the algebra,
and (b) are not necessary.
These statements are justified in the following sub-sections.
NOTE
The following sub-sections are not part of the algebraic
framework description, and may be skipped by readers not
concerned with design rationale.
Klyne [Page 6]
Internet draft 5 August 1998
An algebra for describing media feature sets
3.1 Complexity of feature algebra
Statement (a) above is justified as follows: predicates constructed
as expressions containing media feature values must ultimately
resolve to a logical combination of feature value tests.
A full range of simple tests for all of the data types listed above
can be performed based on just two fundamental operations: equality
and less-than. All other meaningful tests can be constructed as
predicates incorporating these two basic tests.
For example:
( a != b ) iff !( a == b )
( a <= b ) iff !( b < a )
( a > b ) iff ( b < a )
( a >= b ) iff !( a < b )
If additional (composite) data types are introduced, then
additional operators must be introduced to test their component
parts: the addition of just one further comparison operator
increases the number of such operators by 50%.
3.2 Sufficiency of simple types
To justify statement (b), let us first review the range of
composite data types that might reasonably be considered.
In 1972, a paper "Notes on data structuring" by C. A. R. Hoare was
published in the book "Structured Programming" [4]. This was an
early formalization of data types used in programming languages,
and its content has formed a sufficient basis for describing the
data types in almost every programming language which has been
developed. This gives good grounds to believe that the type
framework is also sufficient for media features.
The data types covered by Hoare's paper are:
. Unstructured data types: (integer, real, enumeration, ordered
enumeration, sub-ranges).
. Cartesian product (e.g. C 'struct').
. Discriminated union (e.g. C 'union').
. Array.
. Powerset (e.g. Pascal 'SET OF').
. Sequence (e.g. C string, Pascal 'FILE OF').
Klyne [Page 7]
Internet draft 5 August 1998
An algebra for describing media feature sets
To demonstrate sufficiency of simple types for media features we
must show that the feature-set defining properties of these
composite types can be captured using predicates on the simple
types described previously.
3.2.1 Unstructured data types
The unstructured data types noted correspond closely to, and can be
represented by the proposed simple value types for media features.
3.2.2 Cartesian product
A Cartesian product value (e.g. resolution=[x,y]) is easily
captured as a collection of two or more separately named media
features (e.g. x-resolution=x, y-resolution=y).
3.2.3 Discriminated union
A discriminated union value is an either/or type of choice. For
example, a given workstation might be able to display 16K colours
at 1024x768 resolution, OR 256 colours at 1280x1024 resolution.
These possibilities are captured by a logical-OR of predicates:
( ( x-resolution <= 1024 ) &&
( y-resolution <= 768 ) &&
( colours <= 16384 ) ) ||
( ( x-resolution <= 1280 ) &&
( y-resolution <= 1024 ) &&
( colours <= 256 ) )
3.2.4 Array
An array represents a mapping from one data type to another. For
example, the availability of pens in a pen plotter might be
represented by an array which maps a pen number to a colour.
If the array index which forms the basis for defining a feature set
is assumed to be a constant, then each member can be designated by
a feature name which incorporates the index value. For example:
Pen-1=black, pen-2=red, etc.
Another example where an array might describe a media feature is a
colour palette: an array is used to associate a colour value (in
terms of RGB or some other colour model) with a colour index value.
In this case is possible to envisage a requirement for a particular
colour to be loaded in the palette without any knowledge of the
index which maps to it.
Klyne [Page 8]
Internet draft 5 August 1998
An algebra for describing media feature sets
In this case, the colour might be treated as a named Boolean
attribute: if TRUE then that colour is deemed to be available in
the palette
Feature selection based on a variable array index is more
difficult, but it is believed that this is not required for media
selection.
[[I cannot think of any example of feature selection which involves
a variable index into an array. If such a feature is presented, an
array type could be added to the set of allowable media feature
types, and an array selection operator added to the algebra.]]
3.2.5 Powerset
A powerset is a collection of zero, one or more values from some
base set of values. A colour palette may be viewed as a powerset
of colour values, or the fonts available in a printer as a powerset
of all available fonts.
A powerset is very easily represented by a separate Boolean-valued
feature for each member of the base set. The value TRUE indicates
that the corresponding value is a member of the powerset value.
3.2.6 Sequence
A sequence is a list of values from some base set of values, which
are accessed sequentially.
A sequence can be modelled by an array if one assumes integer index
values starting at (say) 1 and incrementing by 1 for each
successive element of the sequence.
Thus, the considerations described above relating to array values
can be considered as also applying (in part) to sequence values.
That is, if arrays are deemed to be adequately handled, then
sequence values too can be handled.
4. Feature set predicates
A model for data file selection is proposed, based on relational
set definition and subset selection, using elements of the Prolog
programming language [5] as a descriptive notation for this
purpose.
NOTE
The use of Prolog as a syntax for feature description is
NOT being proposed; rather, the Prolog-like notation is
Klyne [Page 9]
Internet draft 5 August 1998
An algebra for describing media feature sets
used to develop the semantics of an algebra. These
semantics could be mapped to any convenient syntax.
For the purposes of developing this algebra, examples are drawn
from the media features described in "Media Features for Display,
Print, and Fax" [6], which in summary are:
pix-x=n (Image size, in pixels)
pix-y=m
res-x=n (Image resolution, pixels per inch)
res-y=m
media= screen/screen-paged/stationary/transparency/
envelope/envelope-plain/envelope-window/
continuous-long/continuous-short
tab-stock/multi-part-form/labels/multi-layer
papersize= na-letter|iso-A4|iso-B4|iso-A3|na-legal
color=n (Colour depth in bits)
grey=n (Grey scale depth in bits)
tiff=S/F/J/C/L/M
4.1 An algebra for data file format selection
The basic idea proposed here is that a feature capability of the
original content, sender, data file format or recipient is
represented as a predicate applied to a collection of feature
values. Under universal quantification (i.e. selecting all
possible values that satisfy it), a predicate indicates a range of
possible combinations of feature values).
This idea is inherent in Prolog clause notation, which is used in
the example below to describe a predicate
'acceptable_file_format(File)', which yields a set of possible file
transfer formats, using other predicates which indicate the file
formats available to the sender and feature capabilities of the
file format, original content:
acceptable_file_format(File) :-
sender_available_file_format(File),
match_format(File).
(Read this statement as: 'File' is an acceptable file format IF it
is a format available to the sender AND it matches the requirements
defined by 'match_format'.)
match_format(File) :-
pix_x(File,Px), content_pix_x(Px), recipient_pix_x(Px),
Klyne [Page 10]
Internet draft 5 August 1998
An algebra for describing media feature sets
pix_y(File,Py), content_pix_x(Py), recipient_pix_y(Py),
res_x(File,Rx), content_res_x(Rx), recipient_res_x(Rx),
res_y(File,Ry), content_res_y(Ry), recipient_res_y(Ry),
colour(File,C), content_colour(C), recipient_colour(C),
grey(File,G), content_grey(G), recipient_grey(G),
ua_media(File,M),
content_ua_media(M),
recipient_ua_media(M),
papersize(File,P),
content_papersize(P),
recipient_papersize(P).
(Read this as: 'File' satisfies the constraints of 'match_format'
IF there is some 'pix_x' feature value 'Px' that is supported by
the file format AND is suitable for representing the message
content to be sent AND can be displayed by the message recipient,
AND there is some 'pix_y' feature ...)
Essentially, 'acceptable_file_format' selects a set of file
transfer formats from those available (as defined by
'sender_available_file_format'), choosing any whose feature
capabilities have a non-empty intersection with the feature
capabilities of the original content and the recipient.
4.1.1 Describing feature sets
The above framework suggests file format capabilities are described
as enumerated feature sets. As an abstract theory, this works fine
but for practical use it has a couple of problems:
(a) description of features with a large number of possibilities
(b) describing features which are supported in specific
combinations
A typical case of (a) would be where a feature (e.g. size of image
in pixels) can take any value from a range. To present and test
each value separately is not a practical proposition, even if it
were possible. (A guide here as to what constitutes a practical
approach is to make a judgement about the feasibility of writing
the corresponding Prolog program.)
A typical case of (b) would be where different values for certain
features can occur only in combinations (e.g. allowable
combinations of resolution and colour depth on a given video
display). If the features are treated independently as suggested
by the framework above, all possible combinations would be allowed,
rather than the specifically allowable combinations.
Klyne [Page 11]
Internet draft 5 August 1998
An algebra for describing media feature sets
4.1.1.1 Feature value ranges
The first issue can be addressed by considering the type of value
which can represent the allowed features of a data file format.
The features of a specific data file are represented as values from
an enumeration (e.g. ua_media, papersize), or a numeric values
(integer or rational). The description of allowable file format
feature needs to represent all the allowable values.
The Prolog clauses used above to describe file format features
already allow for multiple enumerated values. Each acts as a
mathematical relation to select a subset of the set of file values
allowed by the preceding predicates.
Section 3 of this document describes proposed media feature value
types.
For numeric feature values, a sequence of two numbers to represent
a closed interval is suggested, where either value may be replaced
by an empty list to indicate no limiting value. Thus:
[m,n] => { x : m <= x <= n }
[m,[]] => { x : m <= x }
[[],n] => { x : x <= n }
The following Prolog could be used to describe such range matching:
feature_match(X,[[],[]]).
feature_match(X,[L,[]]) :- L <= X.
feature_match(X,[[],H]) :- X <= H.
feature_match(X,[L,H]) :- L <= X, X <= H.
feature_match(X,X).
(This example stretches standard Prolog, which does not support
non-integer numbers. The final clause allows 'feature_match' to
deal with equality matching for the normal enumerated and text
string value case.)
Similar constructs might be used with enumeration-valued and
string-values features for which an ordering relationship is
defined.
4.1.1.2 Feature value combinations
The approach to representing allowed combinations of feature values
presented here is to use additional predicates to describe
relationship constraints between them.
Klyne [Page 12]
Internet draft 5 August 1998
An algebra for describing media feature sets
For example, consider a display capable of handling any x- and y-
resolution between 72dpi and 600dpi. This might be represented by
the constraint clauses:
feature_match(Rx,[75,600]),
feature_match(Ry,[75,600])
If x- and y- resolutions are to be further constrained to specific
related values, the following additional predicate clause might be
added to the feature set description:
feature_match(Rx,75), feature_match(Ry,75) ;
feature_match(Rx,75), feature_match(Ry,150) ;
feature_match(Rx,150), feature_match(Ry,150) ;
feature_match(Rx,150), feature_match(Ry,300) ;
feature_match(Rx,300), feature_match(Ry,300) ;
feature_match(Rx,300), feature_match(Ry,600) ;
feature_match(Rx,600), feature_match(Ry,600)
(Here, 'a;b' denotes 'a' OR 'b'.)
Another example might be a display which supports 640x480, 800x600
and 1024x768 image pixel sizes:
( ( feature_match(Px,640), feature_match(Py,480) ) ;
( feature_match(Px,600), feature_match(Py,800) ) ;
( feature_match(Px,1024), feature_match(Py,768) ) )
This is based on the predicates 'pix_x(File,Px)', 'pix_y(File,Py)',
'res_x(File,Rx)' and 'res_y(File,Ry)' from the initial framework
above.)
4.1.1.3 Using meta-features to group features
The expression of feature combinations can sometimes be simplified
by introducing "meta-features", or auxiliary predicates, to
describe relationship constraints between feature values.
Developing the previous examples, given:
pix_x(File,Px),
pix_y(File,Py),
res_x(File,Rx),
res_y(File,Ry),
We can define meta-features 'pix' and 'res':
pix(File,[Px,Py]) :- pix_x(File,Px), pix_y(File,Py).
res(File,[Rx,Ry]) :- res_x(File,Rx), res_y(File,Ry).
Klyne [Page 13]
Internet draft 5 August 1998
An algebra for describing media feature sets
Then the additional constraints:
pix(File,[640, 480]).
pix(File,[800, 600]).
pix(File,[1024,768]).
serve to define three allowable pixel image sizes, and:
res(File,[Rx,Ry]) :-
feature_match(Rx,75), feature_match(Ry,75) ;
feature_match(Rx,75), feature_match(Ry,150) ;
feature_match(Rx,150), feature_match(Ry,150) ;
feature_match(Rx,150), feature_match(Ry,300) ;
feature_match(Rx,300), feature_match(Ry,300) ;
feature_match(Rx,300), feature_match(Ry,600) ;
feature_match(Rx,600), feature_match(Ry,600)
serves to represent the allowable resolutions described in the
previous section.
4.1.2 Content, sender and recipient capabilities
It has been shown that feature set predicates can be used to
describe the capabilities of a particular content file format, and
also to represent constraints of feature value combinations.
This use of feature predicates is equally applicable to describing
the feature handling capabilities of senders, recipients and other
entities involved in message transmission.
4.2 Conclusion and proposal
The previous sections show that file format capabilities can be
described by feature set predicates: arbitrary logical expressions
using AND, OR, NOT logical combining operators, and media feature
value matching. Data file features, original content features,
sender features and recipient features (and user features) can all
be represented in this way.
A key insight, which points to this conclusion, is that a
collection of feature values can be viewed as describing a specific
representation of the content of a specific document (for example,
when rendered by a given recipient). The capabilities that we wish
to describe, be they sender, file format, recipient or other
capabilities, are sets of such feature collections, with the
potential to be displayed using any of the feature value
collections in the set.
This raises a terminology problem, because the term "feature set"
can be used to mean a collection of specific feature values and a
Klyne [Page 14]
Internet draft 5 August 1998
An algebra for describing media feature sets
range of possible feature values. Thus the more restricted
definitions of "feature collection" and "feature set" which appear
in the terminology section of this document.
Original content, data files and recipients (and users) all embody
the potential capability to deal with a "feature set". One of the
aims of content negotiation is to select an available data file
format (availability being circumscribed by the original content
and sender capabilities) whose feature set intersection with the
recipient feature set is non-empty. (The further issue of
preference being deferred for later consideration.)
The concept of a mathematical relation as a subset defined by a
predicate can be used to define feature sets, using universal
quantification (i.e. using the predicate to select from some
notional universe of all possible feature collections).
Thus, a common framework of predicates can be used to represent the
feature capabilities of original content, data file formats,
recipients and any other participating entity which may impose
constraints on the usable feature sets.
Within this framework, it is sufficient to represent individual
feature values as Booleans, enumerated values, text strings or
numeric ranges. The thesis in section 3 of his document, combined
with a study of "Media Features for Display, Print, and Fax" [6],
indicate that more complex media feature values can be handled by
predicates.
5. Indicating preferences
5.1 Combining preferences
The general problem of describing and combining preferences among
feature sets is very much more complex than simply describing
allowable feature sets. For example, given two feature sets:
{A1,B1}
{A2,B2}
where:
A1 is preferred over A2
B2 is preferred over B1
Which of the feature sets is preferred? In the absence of
additional information or assumptions, there is no generally
satisfactory answer to this.
Klyne [Page 15]
Internet draft 5 August 1998
An algebra for describing media feature sets
The proposed resolution of this issue is simply to assert that
preference information cannot be combined. Applied to the above
example, any preference information about A1 in relation to A2, or
B1 in relation to B2 is not presumed to convey information about
preference of {A1,B1} in relation to {A2,B2}.
In practical terms, this restricts the application of preference
information to top-level predicate clauses. A top-level clause
completely defines an allowable feature set; clauses combined by
logical-AND operators cannot be top-level clauses.
5.2 Representing preferences
A convenient way to represent preferences is by numeric "quality
values", as used in HTTP "Accept" headers, etc. (see RFC 2068 [9],
section 3.9).
It has been suggested that numeric quality values are potentially
misleading if used as more than just a way of ranking options.
Attempts to perform arithmetic on quality values do seem to
degenerate into meaningless juggling of numbers.
Numeric quality values in the range 0 to 1 (as defined by RFC 2068
[9], section 3.9) are used to rank feature sets according to
preference. Higher values are preferred over lower values, and
equal values are presumed to be equally preferred. Beyond this,
the actual number used has no significance, and should not be used
as a basis for any arithmetic operation.
In the absence of any explicitly applied quality value, a value of
"1" is assumed, suggesting an "ideal" option that is equally or
more preferred than any other.
This approach can be represented by extending the Prolog-based
framework of an earlier example as follows:
match_format(File,Qvalue) :-
match_format(File),
Qvalue=1.
match_format(File) :-
pix(File,[1024,768],
res(File,[Rx,Ry]).
match_format(File,Qvalue) :-
pix(File,[800, 600]),
res(File,[Rx,Ry]),
Qvalue=0.9.
match_format(File,Qvalue) :-
Klyne [Page 16]
Internet draft 5 August 1998
An algebra for describing media feature sets
pix(File,[640, 480]).
res(File,[Rx,Ry]),
Qvalue=0.8.
res(File,[Rx,Ry]) :-
feature_match(Rx,75), feature_match(Ry,75) ;
feature_match(Rx,75), feature_match(Ry,150) ;
feature_match(Rx,150), feature_match(Ry,150) ;
feature_match(Rx,150), feature_match(Ry,300) ;
feature_match(Rx,300), feature_match(Ry,300) ;
feature_match(Rx,300), feature_match(Ry,600) ;
feature_match(Rx,600), feature_match(Ry,600)
This example applies image preference ranking based solely on the
size of the image, provided that the resolution constraints are
satisfied.
6. Feature set representation
The foregoing sections have described a framework and semantics for
defining feature sets with predicates applied to feature
collections. This section proposes some concrete representations
for these feature set predicates.
Rather than invent an all-new notation, this proposal adapts a
notation already defined for directory access [7,8]. 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.
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 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.
. Feature selection contains provisions for defining relationships
between feature values.
Klyne [Page 17]
Internet draft 5 August 1998
An algebra for describing media feature sets
The idea of substring matching does not seem to be relevant to
feature set selection, and is excluded from these proposals.
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.
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.
6.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
Klyne [Page 18]
Internet draft 5 August 1998
An algebra for describing media feature sets
simple = attr filtertype value
filtertype = equal / greater / less
equal = "="
approx = "~="
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.)
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 example, to incorporate
a conceivable requirement to explicitly specify a
matching rule).
6.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.
Klyne [Page 19]
Internet draft 5 August 1998
An algebra for describing media feature sets
6.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.
'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 discussion 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.
6.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.
Klyne [Page 20]
Internet draft 5 August 1998
An algebra for describing media feature sets
6.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.)
NOTE
Recursive predicates are not permitted. The scoping
rules should ensure this.
6.3 Feature set definition examples
This section re-casts the Prolog example given in section 5.2 using
the textual form syntax described in sections 6.1 and 6.2.
6.3.1 Single predicate
(| (& (Pix_x=1024)
(Pix_y=768)
(| (& (Res_x=75) (Res_y=75) )
(& (Res_x=75) (Res_y=150) )
(& (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=75) (Res_y=75) )
(& (Res_x=75) (Res_y=150) )
(& (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=75) (Res_y=75) )
Klyne [Page 21]
Internet draft 5 August 1998
An algebra for describing media feature sets
(& (Res_x=75) (Res_y=150) )
(& (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
6.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=75) (Res_y=75) )
(& (Res_x=75) (Res_y=150) )
(& (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
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.
6.4 ASN.1 representation
Should it be required, the LDAP search filter model provides the
basis for an ASN.1 representation of a feature predicate.
The following ASN.1 is adapted from RFC 2251 "Lightweight Directory
Access Protocol (v3)" [7] (also contained in RFC 2254 "The String
Representation of LDAP Search Filters" [8]) to mirror the
adaptation of the string representation presented above
[[The following ASN.1 fragment does not include provision for
quality value (and possibly other parameter values). Also, if
using an ASN.1-derived representation it would seem appropriate to
use an ISO object identifier for the feature tag, and an ASN.1 type
for the feature value. Such changes would remove any semblance of
compatibility with LDAP, but that may not matter.]]
Klyne [Page 22]
Internet draft 5 August 1998
An algebra for describing media feature sets
Filter ::= CHOICE {
and [0] SET OF Filter,
or [1] SET OF Filter,
not [2] Filter,
equalityMatch [3] AttributeValueAssertion,
greaterOrEqual [5] AttributeValueAssertion,
lessOrEqual [6] AttributeValueAssertion
}
AttributeValueAssertion ::= SEQUENCE {
featureTag OCTET STRING,
featureValue OCTET STRING
}
7. Content negotiation protocol processing
This section addresses some issues that may arise when using
feature set predicates as part of some content negotiation or file
selection protocol.
7.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
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), [13] (chapter
4) and [14] (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
Klyne [Page 23]
Internet draft 5 August 1998
An algebra for describing media feature sets
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.
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
the 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 [Page 24]
Internet draft 5 August 1998
An algebra for describing media feature sets
7.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.
7.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 that satisfies both
predicates, 'P' and 'Q'?
Klyne [Page 25]
Internet draft 5 August 1998
An algebra for describing media feature sets
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.
7.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)
7.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 forumulating 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.)
These four cases can be captured by a pair of primitive predicates:
Klyne [Page 26]
Internet draft 5 August 1998
An algebra for describing media feature sets
(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.
7.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 )
Klyne [Page 27]
Internet draft 5 August 1998
An algebra for describing media feature sets
--> (| 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".)
7.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').
7.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.
Klyne [Page 28]
Internet draft 5 August 1998
An algebra for describing media feature sets
7.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
7.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
Klyne [Page 29]
Internet draft 5 August 1998
An algebra for describing media feature sets
[[[TODO: model the above system to confirm that it is complete and
does indeed work properly in all cases.]]]
7.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.
7.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).
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)'.
Klyne [Page 30]
Internet draft 5 August 1998
An algebra for describing media feature sets
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.
7.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]]]
7.5 Worked example
[[[TODO]]]
7.6 Algorithm source code
[[[TODO]]]
8. Security considerations
Some security considerations for content negotiation are raised in
[1,2,3].
Klyne [Page 31]
Internet draft 5 August 1998
An algebra for describing media feature sets
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).
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.
9. 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.
Klyne [Page 32]
Internet draft 5 August 1998
An algebra for describing media feature sets
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.
10. 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.
I would also like to thank Content Technologies Ltd and 5th
Generation Messaging Ltd for supporting this work.
11. 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] "Content feature tag registration procedures"
Koen Holtman, TUE
Andrew Mutz, Hewlett-Packard
Ted Hardie, NASA
Internet draft: <draft-ietf-http-feature-reg-03.txt>
Work in progress, November 1997.
Klyne [Page 33]
Internet draft 5 August 1998
An algebra for describing media feature sets
[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.
[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.
Klyne [Page 34]
Internet draft 5 August 1998
An algebra for describing media feature sets
[12] "Introduction to Expert Systems"
Peter Jackson
Addison Wesley, International computer science series
ISBN 0-201-14223-6
1986.
[13] "Elementary Logics: A procedural Perspective
Dov Gabbay
Prentice Hall, Series in computer science
ISBN 0-13-726365-1
1998.
[14] "Logic and its Applications"
Edmund Burk and Eric Foxley
Prentice Hall, Series in computer science
ISBN 0-13-030263-5
1996.
[15] "Metalogic:
An Introduction to the Metatheory of Standard First Order Logic"
Geoffrey Hunter
University of California Press
ISBN 0-520-02356-0
1971.
[16] "Elementary Linear Algebra"
Paul C Shields
Worth Publishers Inc.
ISBN 0-87901-121-1
1968, 1973, 1980.
[17] "Linear Programming"
Saul I Gass,
McGraw-Hill Inc.
Library of Congress Catalog Card no 68-55267 (no ISBN)
1958, 1964, 1969.
Klyne [Page 35]
Internet draft 5 August 1998
An algebra for describing media feature sets
12. 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 [Page 36]
