Logical representation of sets in Orchestra

[kleihan]

This thread is intended to discuss one of the proposals mentioned in #197 with the headline "Multiple Values". The FIX Protocol uses a repeating group with a single field to express a set where one or more values can be provided. FIX Latest still has two datatypes (MultipleCharValue and MultipleStringValue) that support space delimited single / multiple character values. These datatypes are no longer used for new fields and single field repeating groups are used instead, e.g. ExecInstRules.

Semantically, these are all sets but there is more than one way of encoding a set. It could be a string with or without delimiters to separate the values. It could also be a bitmap with one bit per value, requiring one or more bytes depending on the possible values. A programming language may choose to use an array as datatype to store this information and make it more easily accessible. The Orchestra element ' mappedDatatype' should be enhanced to support the description of the actual encoding.

FIX Latest currently only has one mapping of these datatypes for FIXML, using a pattern for validation:

MultipleCharValue uses pattern="[A-Za-z0-9](\s[A-Za-z0-9])*"
MultipleStringValue uses pattern=".+(\s.+)*"

Should Orchestra be able to express such sets explicitly? If so, what are the options to do so?

Here are some options to start the discussion:

1. Add an attribute to a datatype to express that it is a set and mappedDatatype details the encoding
2. Add an attribute to a code set to express that its values are not mutually exclusive
3. Add an attribute to a field definition to express an unbounded cardinality (this can not only apply to fields with code sets but also to any datatype, e.g. a list of numerical values.
4. Add an attribute to a group definition to express the fact that the group is actually a set (would only be allowed for groups with a single field as element).
5. Add a new element type "set" alongside code sets, fields, components, groups
6. ...

Note that ISO 20022 has a from-to cardinality (0,1,) attached to every element (field, component or group) that implicitly gives presence information (e.g. 0:1 is optional, 1:1 is required, 0: is unbounded and 1:* is at least one and unbounded). FIX Protocol may not use sets as they do not easily map to tag=value.

[donmendelson]

@kleihan, I agree that Orchestra could benefit from having richer and more extensible definitions of datatypes and the mapping to lexical spaces in the mappedDatatype element. The representations in different encodings could be entirely different for the same semantics. As you said, MultipleCharValue is represented in tag-value encoding as a specially encoded string. But multiple choices from a set of valid values can be represented in SBE as a bitset, which is much smaller on the wire and easier to decode.

A bit of background: "set" is one of several aggregate datatypes defined by ISO 11404 General Purpose Datatypes. A set is an unordered collection of unique values.

The other aggregate types are record, class, sequence, bag, array, and table. Each has its own characteristics. The Orchestra equivalent of "record" is Component. I leave it to the group to decide which of the others might be useful in Orchestra.

I will add that the current schema has some rudimentary characteristics for expressing aggregate types. Attributes of mappedDatatype :

<xs:attribute name="element" type="xs:string">
	<xs:annotation>
		<xs:documentation>Element type of an aggregate type such as an array or sequence</xs:documentation>
	</xs:annotation>
</xs:attribute>
<xs:attribute name="size" type="xs:nonNegativeInteger">
	<xs:annotation>
		<xs:documentation>Size of an aggregate type such as an array. That is, the number of elements.</xs:documentation>
	</xs:annotation>
</xs:attribute>

Some aggregations, such as array, have a fixed size while others are variable length. We need to make that distinction clear.

[martinswanson]

Adding a concrete example for a "bitmap" from LSEG's Group Ticker Plant spec

Data type: Bit Field
Description: A single byte used to hold up to eight 1-bit flags. Each bit will represent a Boolean flag. The 0 bit is the lowest significant bit and the 7 bit is the highest significant bit.

I guess this does not fit with Don's description of a Set, but rather an array type.

FWIW I originally modelled this as a component with codesets for each field, as follows:

Component AllowedBookTypes (1)

Synopsis

Defines the order-book types that are allowed for the instrument. Each designated bit represents a book type. ‘0’ means not allowed and ‘1’ means allowed.

Name	Tag	Presence	Synopsis
FirmQuoteBook	1001	optional	Firm Quote Book
OffBook	1002	optional	Off-book
ElectronicOrderBook	1003	optional	Electronic Order Book
PrivateRFQ	1003	optional	Private RFQ

Codeset FirmQuoteBookCodeSet type Boolean (1001)

Name	Value	Id	Sort	Synopsis
NotAllowed	0	1001001	1	Not allowed
Allowed	1	1001002	2	Allowed

[donmendelson]

@martinswanson, although the term "bitset" is commonly used, I agree that it is really an array of Boolean, where each Boolean is encoded as a bit (0/1). In an array, each element is addressable by an index, e.g. the third bit is off (0=false).

[mkudukin]

I'd like to add an overview and a proposal we drafted a few months ago. While it still needs some refinement, it can help us progress the discussion. It addresses options 1 and 2 from @kleihan's original post.

Multi-Value Code Sets Support Requirements

This problem is about fields where their value is not a single one, but it can be multiple values. For example, instead of being Attribute="A", it could be Attribute="A;B;C", where in the latter case the Attribute has 3 values. Specifically, this is about Fields of CodeSet type, where the value space is defined as the list of codes of the CodeSet. In the case above, for example, we can have a CodeSet called Letters, with these 6 code values: A, B, C, D, E, F. And field Attribute is of type Letters, and has multiple values assigned: A, B, and C.

These are our requirements:

• Indicate in Orchestra definition of a Field or CodeSet whether they allow the selection of multiple values. We should decide whether this applies to the Field or CodeSet.
• Define in Orchestra how they are encoded when serialized (using datatype mappings).

The following sections cover cases that we may encounter.

Code sets of values

CodeSet values have variable length

In this case, a CodeSet has values with variable length, e.g. String. This means that a code can have a single character value, and the other one can be two or more characters. This option requires special encoding, e.g. using a separator.

Example

<codeSet name="ExecInstCodeSet" id="18" type="MultipleValueString">
	<code name="NoCross" id="18011" value="A"/>
	<code name="Suspend" id="18012" value="S"/>
	...
	<code name="NoCrossCustom" id="18111" value="Ax"/>
</codeSet>

Encoded field value when codes S and Ax are selected:

S Ax

CodeSet values have fixed length

In this case, a CodeSet has values of a fixed length. This case ensures efficient packing and is applicable when all codes are of the same length, e.g. a single character. This allows the selected codes to be packed sequentially without separators.

Example

<codeSet name="ExecInstCodeSet" id="18" type="MultipleValueString">
	<code name="NoCross" id="18011" value="A"/>
	<code name="Suspend" id="18012" value="S"/>
</codeSet>

Encoded field value when codes A and S are selected:

AS

Code sets of flags (bits)

CodeSet values indicate a bit in a bitmap

In this case, the CodeSet values are selected (i.e., enabled or disabled) based on a bit corresponding to each value. This allows the most efficient packing of the set into binary format, which is especially useful for binary protocols. In this case, a code value represents the bit associated with the code.

Example

<codeSet name="ExecInstCodeSet" id="18" type="BitSet8">
	<code name="NoCross" id="18011" value="1"/>
	<code name="Suspend" id="18012" value="2"/>
	<code name="Hold" id="18013" value="3"/>
</codeSet>

Encoded field value when NoCross and Hold are selected:

Decimal 5, binary 101

Value and lexical space of codes (encoding)

To encode a CodeSet, the datatype of its codes must be defined (i.e., their lexical space). This information is provided through the MappedDataType for each encoding. For example:

• For a CodeSet with “string” codes (i.e., a String value space) the lexical space of their encoded value will be a string, once the individual encoded values are bundled together.
• For a CodeSet with “char” codes (i.e., a Char value space) the lexical space of their encoded value will also be a string, once the individual encoded values are bundled together.
• For a CodeSet with “flag” codes (i.e., a Positive Integer value space) the lexical space of their encoded value will be an Unsigned Integer, once the individual encoded values are bundled together.

The datatype of codes is used to:

• Encode individual code values before composing them into the multi-value result.
• Perform design-time validation by checking that the code value conforms to its datatype.

Value Separator

A separator is necessary when encoding CodeSets with a variable length codes values, e.g. string values. This allows to identify each code values in the composite value. The separator must obviously belong to the composite lexical space.

Possible Solution Ideas

We recommend introducing a new attribute, compositeType, which should be used if a CodeSet supports multiple values. This attribute should reference a datatype with a value space suitable to represent the composite value of all the selected codes together.

Example

Define a CodeSet with two codes: P and N. The CodeSet should support selection of up to two codes simultaneously, i.e., valid values of a Field of this CodeSet would be: <none>, P, N, and PN.

<codeSet name="ExecInstCodeSet" id="18" type="char” compositeType="string">
	<code id="1" name="NoPriceCheck" value="P"/>
	<code id="2" name="NoNotionalCheck" value="N"/>
</codeSet>

The type attribute refers to the datatype char, which indicates the value space for individual codes. The new compositeType attribute refers to the datatype string, which indicates the value space required by the result of combining multiple codes. In the XML standard, these datatypes are mapped to the xs:string type, with their respective value space restrictions as it follows:

<datatype name="char">
	<mappedDatatype standard="XML" base="xs:string" size="1" pattern="[A-Za-z0-9]"/>
</datatype>

<datatype name="string">
	<mappedDatatype standard="XML" base="xs:string"/>
</datatype>

Using the information above, an encoder understands the correct way to represent the selected codes within a composite type. In the above example, the decoder understands that individual codes’ characters are concatenated to form a string.

As described earlier, a protocol may require a separator between encoded values. We recommend indicating this to the encoder with a new elementSeparator attribute of the mappedDatatype element. Its value can be a string or a single character to be used as a separator while concatenating individual values. In the following example, we indicate that a comma is used as a separator. Therefore, when both codes of the above sample CodeSet are selected, the encoded value of the field will be P,N.

<<datatype name="string">
	<mappedDatatype standard="XML" base="xs:string" elementSeparator=","/>
</datatype>

For bit sets, mappedDatatype of a composite type should tell the encoder that the datatype should be treated as a bitmap. An easy way to do this is to map to the bitstring datatype from ISO 11404. In such a case, the encoder should expect each code’s value to be a bit’s ordinal number. The value space of a code’s value should be set accordingly. The following example is a rewritten version of ExecInstCodeSet, backed by a bit set this time:

<codeSet name="ExecInstCodeSet" id="18" type="BitNum8” compositeType="BitSet8">
	<code id="1" name="NoPriceCheck" value="1"/>
	<code id="2" name="NoNotionalCheck" value="2"/>
</codeSet>

<datatype name="BitSet8">
	<mappedDatatype standard="ISO11404" base="bitstring" element="bit" size="8"/>
	<!-- An octet representing up to 256 states -->
</datatype>

<datatype name="BitNum8">
	<mappedDatatype standard="ISO11404" base="integer" minInclusive="1" maxInclusive="8"/>
	<!-- A number of a bit in an octet -->
</datatype>

In this example, the composite type of the CodeSet is a set of eight bits, even though the CodeSet may use only two of them. Most binary protocols align such datatypes by octets, so it can be represented internally as an unsigned byte. The BitNum8 type instead is mapped to an integer with a valid value range of 1 to 8, representing 1-based ordinal number of a bit. This requires the values of CodeSet’s codes to conform to this datatype, mapping each code to a particular bit.