Annotation uses

• Numeric annotations serve to place limits on the number of isomorphic structures that can occur in matching portions of the database.

• Numeric annotations also serve to group isomorphic structures that would otherwise produce multiple matches into a single subgraph.

• QGraph does not provide any mechanism for limiting the number of matching substructures without grouping the results.

• A numeric annotation can be specified on a vertex or edge in a QGraph query.

Annotation format

• An unbounded range [i..] on a vertex or edge means that at least i instances of the corresponding database element must be present to match the query. An unbounded range will match any number greater than or equal to i of database elements.

• A bounded range [i..j] means that at least i and no more than j instances are required for a match. The query will not match database structures that have fewer than i or more than j of the annotated element.

• An exact annotation [i] means that exactly the specified number of database elements must be present to match the query. The query will not match database structures that have fewer than or more than the specified number of elements.

• To group substructures without limit, we use the annotation [1..].

Adjacency requirements

• Edges adjacent to annotated vertices must themselves be annotated.

• Annotated edges can stand alone; they do not require that any adjacent vertices be annotated.

• The [1..] annotation is often the appropriate choice for annotating an edge adjacent to an annotated vertex.

• The vertex annotation takes precedence over the edge annotation.

• At most, only one of two adjacent vertices can be annotated.

Negated and optional elements

• A negated element is annotated with [0], indicating that the corresponding database element must not be present in the matching subgraph.

• An optional element is annotated with [0..] or [0..j], indicating that the corresponding database element may be present but is not required in the matching subgraph.

• To be well formed, a query must remain a connected graph after removing any negated or optional elements.

• The annotation [1..] is usually appropriate for annotating edges adjacent to a negated or optional vertex.

• Negated query elements do not appear in the query’s results.

• Negated elements cannot substitute for conditions that express inequalities.

Implementation restrictions

• Proximity cannot process queries in which an annotated vertex is connected to more than one unannotated vertex.

• Proximity prohibits edge annotations with a lower bound of 0.