<commit_before>= CIP2016-06-14 - Define Comparability and Equality, as well as Orderability and Equivalence
:numbered:
:toc:
:toc-placement: macro
:source-highlighter: codemirror

*Authors:* <NAME> <<EMAIL>>, <NAME> <<EMAIL>>

[abstract]
.Abstract
--
This CIP redefines and formalizes 4 key language concepts, *comparability* and *equality*, as well as *orderability* and *equivalence*. While these notions already exist in the language today, they have never been defined explicitly.
Furthermore the current definitions are somewhat misaligned with each other.
This leads to inconsistencies and an unnecessarily complicated conceptual model.
In summary, this CIP proposes some changes to how Cypher defines these four concepts in order to get a consistent set of rules and also proposes to align comparability with equality, as well as orderability with equivalence to provide a simpler conceptual model.
It also gives a brief definition of aggregation and standard aggregation functions.
--

toc::[]

== Motivation

There are currently a number of limitations and inconsistencies that this proposal aims to address:

1. Cypher already has good semantics for equality within the primitive types (booleans, strings, integers, and floats) and maps.
Furthermore, Cypher has good semantics for comparability and orderability for integers, floats, and strings, within each of the types.
However working with values of different types can be difficult:

  * Comparability between values of different types is often undefined. This stops query execution instead of allowing graceful recovery. This problem is particularly pronounced when it occurs as part of the evaluation of predicates (in `WHERE`).
  * `ORDER BY` will often fail with an error if the values passed to it have different types.

2. The underlying conceptual model is complex and sometimes inconsistent. This leads to an unclear relationship between comparison operators, equality, grouping, and `ORDER BY`:

  * Comparability and orderability are not aligned with each other consistently, as some types may be ordered but not compared.
  * There are various inconsistencies around equality (and equivalence) semantics as exposed by `IN`, `=`, `DISTINCT`, and grouping.
  The difference between equality and equivalence in Cypher today is small and subtle, and limited to testing two instances of the value `null` to each other.

  ** In equality, `null = null` is `null`.
  ** In equivalence, used by `DISTINCT` and when grouping values, two `null` values are always treated as being the same value.
  ** However, equality treats `null` values differently if they are an element of a list or a map value.
  ** Similar rules apply for `NaN` values.

Furthermore, the key concepts comparability, orderability, equality, and equivalence have never been defined properly.  Therefore another motivation for this CIP is to unambiguously and precisely define these 4 concepts.

== Background

The reader should be mindful of the Cypher type system when reading this CIP. At the time of this proposal, the latest CIP regarding the Cypher type system is: https://github.com/opencypher/openCypher/blob/master/cip/CIP2015-09-16-public-type-system-type-annotation.adoc[`CIP2015-09-16-public-type-system-type-annotation`].

== Proposal

We propose to redefine <<comparability-def>> and <<equality-def>>, as well as <<orderability-def>> and <<equivalence-def>> as detailed in this section, and additionally rephrase <<aggregation,aggregation>> in terms of these new concepts.

[[concepts]]
=== Concepts

Cypher today features four distinct concepts related to equality and ordering:

[horizontal]
[[comparability-con,comparability (concept)]]*Comparability*:: <<comparability-def,Comparability>> is used by the inequality operators (`>`, `<`, `>=`, `\<=`), and defines the underlying semantics of how to compare two values.
[[equality-con,equality (concept)]]*Equality*:: <<equality-def,Equality>> is used by the equality operators (`=`, `<>`), and the list membership operator (`IN`).
It defines the underlying semantics to determine if two values are the same in these contexts.
Equality is also used implicitly by literal maps in node and relationship patterns, since such literal maps are merely a shorthand notation for equality predicates.
[[orderability-con,orderability (concept)]]*Orderability*:: <<orderability-def,Orderability>> is used by the `ORDER BY` clause, and defines the underlying semantics of how to order values.
[[equivalence-con,equivalence (concept)]]*Equivalence*:: <<equivalence-def,Equivalence>> is used by the `DISTINCT` modifier and by grouping in projection clauses (`WITH`, `RETURN`), and defines the underlying semantics to determine if two values are the same in these contexts.

==== The meaning of `null`

For the following discussion, it is helpful to clarify the meaning of `null`. In Cypher, a `null` value has one of two meanings, depending on the context in which it occurs:

[horizontal]
[[unknown-null,unknown `null`]]*Unknown*:: An "unknown" `null` is taken to be a placeholder for an arbitrary but unknown value. When evaluating predicates, an "unknown" `null` is the `maybe` truth value of ternary logic. For node and relationship properties, an "unknown" `null` is a value that is definite in the real world but has not been stored in the graph. Since in these cases, two "unknown" `null` values stand for arbitrary but definite values in the real world, two "unknown" `null` values should never be treated as certainly being the same value.
[[missing-null,missing `null`]]*Missing*:: A "missing" `null` is taken to be a marker for the absence of a value. In the context of updating node properties from a map, a "missing" `null` is used to mark properties that are to be removed. In the context of `DISTINCT` and grouping, a "missing" `null` value is used as grouping key for all records that miss a more specific value. Since in these cases, two "missing" `null` values represent the same concept, they should always be treated as the same value.

[[regular-map]]
==== Regular maps

Cypher today has one supertype `MAP` for all map values. This includes nodes (of subtype `NODE`), relationships (of subtype `RELATIONSHIP`), and any other map (not captured by a subtype of `MAP`). For the purpose of this document, we define a regular map to be any value of type `MAP` that is neither a `NODE` nor a `RELATIONSHIP`.

[[comparability-equality,comparability and equality]]
=== Comparability and equality

We propose that comparability and equality should be aligned with each other, i.e.

`expr1 = expr2` if and only if `expr1 >= expr2 && expr1 \<= expr2`.

Comparability and equality produce <<unknown-null,"unknown" `null` values>>.

[[incomparable,incomparable]]
==== Incomparability

If and only if every comparison and equality test involving a specific value evaluates to `null`, this value is said to be incomparable.

Furthermore, if every comparison or equality test between two specific values evaluates to `null`, theses values are said to be incomparable with each other.

[[comparability-def,comparability]]
==== Comparability

We propose that <<comparability-con,comparability>> should be defined between any pair of values, as specified below.

- General rules
  * Values are only comparable within their most specific type (except for numbers, see below).
  * Equal values are grouped together.
- Numbers
  * Integers are compared numerically in ascending order.
  * Floats (excluding `NaN` values and the Infinities) are compared numerically in ascending order.
  * Numbers of different types (excluding `NaN` values and the Infinities) are compared to each other as if both numbers would have been coerced to arbitrary precision big decimals (currently outside the Cypher type system) before comparing them with each other numerically in ascending order.
  * Positive infinity is of type `FLOAT`, equal to itself and greater than any other number (excluding `NaN` values).
  * Negative infinity is of type `FLOAT`, equal to itself and less than any other number (excluding `NaN` values).
  * `NaN` values are <<incomparable>>.
  * Numbers are <<incomparable>> to any value that is not also a number.
- Booleans
  * Booleans are compared such that `false` is less than `true`.
  * Booleans are <<incomparable>> to any value that is not also a boolean.
- Strings
  * Strings are compared in dictionary order, i.e. characters are compared pairwise in ascending order from the start of the string to the end.
  Characters missing in a shorter string are considered to be less than any other character.
  For example, `'a' < 'aa'`.
  * Strings are <<incomparable>> to any value that is not also a string.
- Lists
  * Lists are compared in dictionary order, i.e. list elements are compared pairwise in ascending order from the start of the list to the end. Elements missing in a shorter list are considered to be less than any other value (including `null` values).
  For example, `[1] < [1, 0]` but also `[1] < [1, null]`.
  * If comparing two lists requires comparing at least a single `null` value to some other value, these lists are <<incomparable>>.
  For example, `[1, 2] >= [1, null]` evaluates to `null`.
  * Lists are <<incomparable>> to any value that is not also a list.
- Maps
  * [[regular-maps,regular maps]]Regular maps
  ** The comparison order for maps is unspecified and left to implementations.
  ** The comparison order for maps must align with the <<equality-def,equality semantics>> outlined below.
  In consequence, any map that contains an entry that maps its key to a `null` value is <<incomparable>>.
  For exampe, `{a: 1} \<= {a: 1, b: null}` evaluates to `null`.
  ** Regular maps are <<incomparable>> to any value that is not also a regular map.
  * Nodes
  ** The comparison order for nodes is based on an implementation specific internal total order of node identities.
  ** Nodes are <<incomparable>> to any value that is not also a node.
  * Relationships
  ** The comparison order for relationships is based on an implementation specific internal total order of relationship identities.
  ** Relationships are <<incomparable>> to any value that is not also a relationship.
- Paths
  ** Paths are compared as if they were a list of alternating nodes and relationships of the path from the start node to the end node.
  For example, given nodes `n1`, `n2`, `n3`, and relationships `r1` and `r2`, and given that `n1 < n2 < n3` and `r1 < r2`, then the path `p1` from `n1` to `n3` via `r1` would be less than the path `p2` to `n1` from `n2` via `r2`. Expressed in terms of lists:

      p1 < p2
  <=> [n1-r1->n3] < [n1<-r2-n2]
  <=> n1 < n1 || (n1 = n1 && [r1, n3] < [r2, n2])
  <=> false || (true && [r1, n3] < [r2, n2])
  <=> [r1, n3] < [r2, n2]
  <=> r1 < r2 || (r1 = r2 && n3 < n2)
  <=> true || (false && false)
  <=> true

  ** Additionally, paths track the direction in which a relationship is traversed.
  Two paths that traverse the same nodes and relationships in the same order but differ in the direction in which they traverse a single relationship are not equal (this can happen in paths containing loops).
  The comparison order for paths is expected to align with this.
  ** Paths are <<incomparable>> to any value that is not also a path.
- Implementation-specific types
  * Implementations may choose to define suitable comparability rules for values of additional, non-canonical types.
  * Values of an additional, non-canonical type are expected to be <<incomparable>> to values of a canonical type.
- `null` is <<incomparable>> with any other value (including other `null` values).

[[equality-def,equality]]
==== Equality ====

In order to align equality with <<comparability-def>>, we change equality of lists and maps that contain `null` values to treat those values in the same way as if they would have been compared outside of those lists and maps, as individual, simple values.
<commit_msg>Change definition of path comparability<commit_after>= CIP2016-06-14 - Define Comparability and Equality, as well as Orderability and Equivalence
:numbered:
:toc:
:toc-placement: macro
:source-highlighter: codemirror

*Authors:* <NAME> <<EMAIL>>, <NAME> <<EMAIL>>

[abstract]
.Abstract
--
This CIP redefines and formalizes 4 key language concepts, *comparability* and *equality*, as well as *orderability* and *equivalence*. While these notions already exist in the language today, they have never been defined explicitly.
Furthermore the current definitions are somewhat misaligned with each other.
This leads to inconsistencies and an unnecessarily complicated conceptual model.
In summary, this CIP proposes some changes to how Cypher defines these four concepts in order to get a consistent set of rules and also proposes to align comparability with equality, as well as orderability with equivalence to provide a simpler conceptual model.
It also gives a brief definition of aggregation and standard aggregation functions.
--

toc::[]

== Motivation

There are currently a number of limitations and inconsistencies that this proposal aims to address:

1. Cypher already has good semantics for equality within the primitive types (booleans, strings, integers, and floats) and maps.
Furthermore, Cypher has good semantics for comparability and orderability for integers, floats, and strings, within each of the types.
However working with values of different types can be difficult:

  * Comparability between values of different types is often undefined. This stops query execution instead of allowing graceful recovery. This problem is particularly pronounced when it occurs as part of the evaluation of predicates (in `WHERE`).
  * `ORDER BY` will often fail with an error if the values passed to it have different types.

2. The underlying conceptual model is complex and sometimes inconsistent. This leads to an unclear relationship between comparison operators, equality, grouping, and `ORDER BY`:

  * Comparability and orderability are not aligned with each other consistently, as some types may be ordered but not compared.
  * There are various inconsistencies around equality (and equivalence) semantics as exposed by `IN`, `=`, `DISTINCT`, and grouping.
  The difference between equality and equivalence in Cypher today is small and subtle, and limited to testing two instances of the value `null` to each other.

  ** In equality, `null = null` is `null`.
  ** In equivalence, used by `DISTINCT` and when grouping values, two `null` values are always treated as being the same value.
  ** However, equality treats `null` values differently if they are an element of a list or a map value.
  ** Similar rules apply for `NaN` values.

Furthermore, the key concepts comparability, orderability, equality, and equivalence have never been defined properly.  Therefore another motivation for this CIP is to unambiguously and precisely define these 4 concepts.

== Background

The reader should be mindful of the Cypher type system when reading this CIP. At the time of this proposal, the latest CIP regarding the Cypher type system is: https://github.com/opencypher/openCypher/blob/master/cip/CIP2015-09-16-public-type-system-type-annotation.adoc[`CIP2015-09-16-public-type-system-type-annotation`].

== Proposal

We propose to redefine <<comparability-def>> and <<equality-def>>, as well as <<orderability-def>> and <<equivalence-def>> as detailed in this section, and additionally rephrase <<aggregation,aggregation>> in terms of these new concepts.

[[concepts]]
=== Concepts

Cypher today features four distinct concepts related to equality and ordering:

[horizontal]
[[comparability-con,comparability (concept)]]*Comparability*:: <<comparability-def,Comparability>> is used by the inequality operators (`>`, `<`, `>=`, `\<=`), and defines the underlying semantics of how to compare two values.
[[equality-con,equality (concept)]]*Equality*:: <<equality-def,Equality>> is used by the equality operators (`=`, `<>`), and the list membership operator (`IN`).
It defines the underlying semantics to determine if two values are the same in these contexts.
Equality is also used implicitly by literal maps in node and relationship patterns, since such literal maps are merely a shorthand notation for equality predicates.
[[orderability-con,orderability (concept)]]*Orderability*:: <<orderability-def,Orderability>> is used by the `ORDER BY` clause, and defines the underlying semantics of how to order values.
[[equivalence-con,equivalence (concept)]]*Equivalence*:: <<equivalence-def,Equivalence>> is used by the `DISTINCT` modifier and by grouping in projection clauses (`WITH`, `RETURN`), and defines the underlying semantics to determine if two values are the same in these contexts.

==== The meaning of `null`

For the following discussion, it is helpful to clarify the meaning of `null`. In Cypher, a `null` value has one of two meanings, depending on the context in which it occurs:

[horizontal]
[[unknown-null,unknown `null`]]*Unknown*:: An "unknown" `null` is taken to be a placeholder for an arbitrary but unknown value. When evaluating predicates, an "unknown" `null` is the `maybe` truth value of ternary logic. For node and relationship properties, an "unknown" `null` is a value that is definite in the real world but has not been stored in the graph. Since in these cases, two "unknown" `null` values stand for arbitrary but definite values in the real world, two "unknown" `null` values should never be treated as certainly being the same value.
[[missing-null,missing `null`]]*Missing*:: A "missing" `null` is taken to be a marker for the absence of a value. In the context of updating node properties from a map, a "missing" `null` is used to mark properties that are to be removed. In the context of `DISTINCT` and grouping, a "missing" `null` value is used as grouping key for all records that miss a more specific value. Since in these cases, two "missing" `null` values represent the same concept, they should always be treated as the same value.

[[regular-map]]
==== Regular maps

Cypher today has one supertype `MAP` for all map values. This includes nodes (of subtype `NODE`), relationships (of subtype `RELATIONSHIP`), and any other map (not captured by a subtype of `MAP`). For the purpose of this document, we define a regular map to be any value of type `MAP` that is neither a `NODE` nor a `RELATIONSHIP`.

[[comparability-equality,comparability and equality]]
=== Comparability and equality

We propose that comparability and equality should be aligned with each other, i.e.

`expr1 = expr2` if and only if `expr1 >= expr2 && expr1 \<= expr2`.

Comparability and equality produce <<unknown-null,"unknown" `null` values>>.

[[incomparable,incomparable]]
==== Incomparability

If and only if every comparison and equality test involving a specific value evaluates to `null`, this value is said to be incomparable.

Furthermore, if every comparison or equality test between two specific values evaluates to `null`, theses values are said to be incomparable with each other.

[[comparability-def,comparability]]
==== Comparability

We propose that <<comparability-con,comparability>> should be defined between any pair of values, as specified below.

- General rules
  * Values are only comparable within their most specific type (except for numbers, see below).
  * Equal values are grouped together.
- Numbers
  * Integers are compared numerically in ascending order.
  * Floats (excluding `NaN` values and the Infinities) are compared numerically in ascending order.
  * Numbers of different types (excluding `NaN` values and the Infinities) are compared to each other as if both numbers would have been coerced to arbitrary precision big decimals (currently outside the Cypher type system) before comparing them with each other numerically in ascending order.
  * Positive infinity is of type `FLOAT`, equal to itself and greater than any other number (excluding `NaN` values).
  * Negative infinity is of type `FLOAT`, equal to itself and less than any other number (excluding `NaN` values).
  * `NaN` values are <<incomparable>>.
  * Numbers are <<incomparable>> to any value that is not also a number.
- Booleans
  * Booleans are compared such that `false` is less than `true`.
  * Booleans are <<incomparable>> to any value that is not also a boolean.
- Strings
  * Strings are compared in dictionary order, i.e. characters are compared pairwise in ascending order from the start of the string to the end.
  Characters missing in a shorter string are considered to be less than any other character.
  For example, `'a' < 'aa'`.
  * Strings are <<incomparable>> to any value that is not also a string.
- Lists
  * Lists are compared in dictionary order, i.e. list elements are compared pairwise in ascending order from the start of the list to the end. Elements missing in a shorter list are considered to be less than any other value (including `null` values).
  For example, `[1] < [1, 0]` but also `[1] < [1, null]`.
  * If comparing two lists requires comparing at least a single `null` value to some other value, these lists are <<incomparable>>.
  For example, `[1, 2] >= [1, null]` evaluates to `null`.
  * Lists are <<incomparable>> to any value that is not also a list.
- Maps
  * [[regular-maps,regular maps]]Regular maps
  ** The comparison order for maps is unspecified and left to implementations.
  ** The comparison order for maps must align with the <<equality-def,equality semantics>> outlined below.
  In consequence, any map that contains an entry that maps its key to a `null` value is <<incomparable>>.
  For exampe, `{a: 1} \<= {a: 1, b: null}` evaluates to `null`.
  ** Regular maps are <<incomparable>> to any value that is not also a regular map.
  * Nodes
  ** The comparison order for nodes is based on an implementation specific internal total order of node identities.
  ** Nodes are <<incomparable>> to any value that is not also a node.
  * Relationships
  ** The comparison order for relationships is based on an implementation specific internal total order of relationship identities.
  ** Relationships are <<incomparable>> to any value that is not also a relationship.
- Paths
  ** Paths are compared as if they were a list of alternating nodes and relationships of the path from the start node to the end node.
  For example, given nodes `n1`, `n2`, `n3`, and relationships `r1` and `r2`, and given that `n1 < n2 < n3` and `r1 < r2`, then the path `p1` from `n1` to `n3` via `r1` would be less than the path `p2` to `n1` from `n2` via `r2`. Expressed in terms of lists:

      p1 < p2
  <=> [n1, r1, n3] < [n1, r2, n2]
  <=> n1 < n1 || (n1 = n1 && [r1, n3] < [r2, n2])
  <=> false || (true && [r1, n3] < [r2, n2])
  <=> [r1, n3] < [r2, n2]
  <=> r1 < r2 || (r1 = r2 && n3 < n2)
  <=> true || (false && false)
  <=> true

  ** Paths are <<incomparable>> to any value that is not also a path.
- Implementation-specific types
  * Implementations may choose to define suitable comparability rules for values of additional, non-canonical types.
  * Values of an additional, non-canonical type are expected to be <<incomparable>> to values of a canonical type.
- `null` is <<incomparable>> with any other value (including other `null` values).

[[equality-def,equality]]
==== Equality ====

In order to align equality with <<comparability-def>>, we change equality of lists and maps that contain `null` values to treat those values in the same way as if they would have been compared outside of those lists and maps, as individual, simple values.

{'fraction_non_alphanumeric': 0.08278552949658595, 'fraction_numerical': 0.007803554009924085, 'mean_word_length': 4.614285714285714, 'pattern_counts': {'":': 0, '<': 172, '<?xml version=': 0, '>': 144, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1700704', 'n_tokens_mistral': 6373, 'n_tokens_neox': 6015, 'n_words': 3343}