Data Structure Ontology

AI SEARCH

FLOW ALGEBRA — DATA STRUCTURE ONTOLOGY
Semantic Library
Version: 4.0
Canonical Page:
https://kirethresearch.org/booksai-core/ontologies/computing-ontologies/data-structures/data-structure-ontology.html

FLOW DATA_STRUCTURE_ONTOLOGY {

  META {
    DOMAIN = "Computing Ontologies"
    SUBDOMAIN = "Data Structures"
    ONTOLOGY = "Data Structure Ontology"
    PURPOSE = "Formalise data structures as computational entities, including their elements, organisation, operations, invariants, abstract interfaces, concrete representations, complexity and memory relationships."
    LOCALE = "en-GB"
  }

  ENTITY_TYPES {
    DATA_STRUCTURE
    ABSTRACT_DATA_TYPE
    CONCRETE_DATA_STRUCTURE
    LINEAR_DATA_STRUCTURE
    NONLINEAR_DATA_STRUCTURE
    STATIC_DATA_STRUCTURE
    DYNAMIC_DATA_STRUCTURE
    MUTABLE_DATA_STRUCTURE
    IMMUTABLE_DATA_STRUCTURE
    PERSISTENT_DATA_STRUCTURE
    CONCURRENT_DATA_STRUCTURE
    ELEMENT
    VALUE
    KEY
    INDEX
    NODE
    EDGE
    POINTER
    REFERENCE
    COLLECTION
    SEQUENCE
    ARRAY
    DYNAMIC_ARRAY
    MATRIX
    LINKED_LIST
    SINGLY_LINKED_LIST
    DOUBLY_LINKED_LIST
    CIRCULAR_LIST
    STACK
    QUEUE
    DEQUE
    PRIORITY_QUEUE
    SET
    MULTISET
    MAP
    DICTIONARY
    HASH_TABLE
    TREE
    BINARY_TREE
    BINARY_SEARCH_TREE
    BALANCED_TREE
    AVL_TREE
    RED_BLACK_TREE
    B_TREE
    B_PLUS_TREE
    HEAP
    TRIE
    GRAPH
    DIRECTED_GRAPH
    UNDIRECTED_GRAPH
    WEIGHTED_GRAPH
    DAG
    DISJOINT_SET
    UNION_FIND
    BLOOM_FILTER
    SKIP_LIST
    BUFFER
    RING_BUFFER
    RECORD
    TUPLE
    OPERATION
    CREATE
    INSERT
    DELETE
    ACCESS
    LOOKUP
    SEARCH
    UPDATE
    TRAVERSE
    ITERATE
    SORT
    MERGE
    SPLIT
    PUSH
    POP
    ENQUEUE
    DEQUEUE
    PEEK
    RESIZE
    ROTATE
    REBALANCE
    INVARIANT
    ORDERING_INVARIANT
    STRUCTURAL_INVARIANT
    BALANCE_INVARIANT
    CAPACITY
    SIZE
    LOAD_FACTOR
    COMPLEXITY
    TIME_COMPLEXITY
    SPACE_COMPLEXITY
    BEST_CASE
    AVERAGE_CASE
    WORST_CASE
    MEMORY_LAYOUT
    CONTIGUOUS_MEMORY
    LINKED_MEMORY
    STRUCTURAL_SHARING
    IMPLEMENTATION
    CONFIGURATION
    LANGUAGE_CONTEXT
    RUNTIME_CONTEXT
    EVIDENCE
    CONFIDENCE_SCORE
    PROVENANCE_RECORD
  }

  RELATIONSHIPS {
    IS_A
    INSTANCE_OF
    IMPLEMENTS
    REPRESENTS
    PART_OF
    CONTAINS
    HAS_ELEMENT
    HAS_KEY
    HAS_VALUE
    HAS_INDEX
    HAS_NODE
    HAS_EDGE
    POINTS_TO
    REFERENCES
    PRECEDES
    FOLLOWS
    PARENT_OF
    CHILD_OF
    CONNECTED_TO
    ADJACENT_TO
    MAPS_TO
    HASHES_TO
    STORED_IN
    SUPPORTS_OPERATION
    INSERTS
    DELETES
    ACCESSES
    LOOKS_UP
    SEARCHES
    UPDATES
    TRAVERSES
    ITERATES
    SORTS
    MERGES
    SPLITS
    PUSHES
    POPS
    ENQUEUES
    DEQUEUES
    RESIZES
    ROTATES
    REBALANCES
    PRESERVES
    HAS_INVARIANT
    HAS_ORDERING
    HAS_SIZE
    HAS_CAPACITY
    HAS_LOAD_FACTOR
    HAS_TIME_COMPLEXITY
    HAS_SPACE_COMPLEXITY
    HAS_MEMORY_LAYOUT
    HAS_IMPLEMENTATION
    HAS_CONFIGURATION
    DEPENDS_ON
    DERIVED_FROM
    INFERRED_FROM
    HAS_EVIDENCE
    HAS_CONFIDENCE
    HAS_PROVENANCE
    SEMANTICALLY_EQUIVALENT_TO
  }

  INPUTS {
    DATA_STRUCTURE_SPECIFICATIONS
    ABSTRACT_DATA_TYPE_SPECIFICATIONS
    IMPLEMENTATION_DEFINITIONS
    SOURCE_CODE
    ELEMENT_AND_VALUE_DATA
    KEY_AND_INDEX_DATA
    NODE_AND_EDGE_DATA
    OPERATION_TRACES
    INVARIANT_DEFINITIONS
    COMPLEXITY_ANALYSES
    MEMORY_LAYOUT_DATA
    BENCHMARK_DATA
    LANGUAGE_CONTEXT
    RUNTIME_CONTEXT
    CONFIGURATION_DATA
    ONTOLOGY_TERMS
  }

  NORMALISE {
    STANDARDISE_STRUCTURE_IDENTIFIERS
    NORMALISE_STRUCTURE_NAMES
    NORMALISE_ABSTRACT_DATA_TYPE_NAMES
    NORMALISE_IMPLEMENTATION_NAMES
    NORMALISE_ELEMENT_KEY_AND_VALUE_TYPES
    NORMALISE_OPERATION_NAMES
    NORMALISE_NODE_AND_EDGE_IDENTIFIERS
    NORMALISE_ORDERING_TERMS
    NORMALISE_COMPLEXITY_NOTATION
    NORMALISE_MEMORY_UNITS
    NORMALISE_SIZE_CAPACITY_AND_LOAD_FACTOR
    NORMALISE_LANGUAGE_AND_RUNTIME_CONTEXT
    RESOLVE_STRUCTURE_AND_ELEMENT_IDENTITIES
    ALIGN_ONTOLOGY_TERMS
    REMOVE_DUPLICATES
    VALIDATE_METADATA
    PRESERVE_PROVENANCE
  }

  PROCESS DATA_STRUCTURE_PIPELINE {
    STRUCTURE_REFERENCE
      -> STRUCTURE_IDENTIFICATION
      -> ABSTRACT_DATA_TYPE_MAPPING
      -> CONCRETE_IMPLEMENTATION_MAPPING
      -> ELEMENT_AND_RELATION_MAPPING
      -> OPERATION_MAPPING
      -> INVARIANT_ANALYSIS
      -> COMPLEXITY_ANALYSIS
      -> MEMORY_REPRESENTATION_ANALYSIS
      -> VALIDATION
      -> OUTPUT
  }

  PROCESS ABSTRACT_TYPE_REASONING {
    ABSTRACT_DATA_TYPE
      -> REQUIRED_OPERATIONS

    REQUIRED_OPERATIONS
      -> BEHAVIOURAL_CONTRACT

    CONCRETE_DATA_STRUCTURE
      -> PROVIDED_OPERATIONS

    PROVIDED_OPERATIONS + BEHAVIOURAL_CONTRACT
      -> IMPLEMENTATION_CONFORMANCE
  }

  PROCESS ELEMENT_REASONING {
    DATA_STRUCTURE
      -> ELEMENT_SET

    ELEMENT
      -> VALUE_OR_KEY_VALUE_PAIR_OR_NODE

    ELEMENT_RELATIONS
      -> STRUCTURAL_OR_ORDERING_RELATIONS

    STRUCTURAL_RELATIONS
      -> STRUCTURE_STATE
  }

  PROCESS OPERATION_REASONING {
    DATA_STRUCTURE_STATE(T1)
      + OPERATION
      -> PRECONDITION_CHECK

    VALID_OPERATION
      -> STATE_TRANSFORMATION

    STATE_TRANSFORMATION
      -> DATA_STRUCTURE_STATE(T2)

    DATA_STRUCTURE_STATE(T2)
      -> INVARIANT_CHECK
  }

  PROCESS ARRAY_REASONING {
    ARRAY
      -> INDEX_DOMAIN

    INDEX
      -> OFFSET_OR_LOCATION

    LOCATION
      -> ELEMENT

    DYNAMIC_ARRAY_RESIZE
      -> NEW_CAPACITY
      -> ELEMENT_RELOCATION_IF_REQUIRED
  }

  PROCESS LINKED_STRUCTURE_REASONING {
    NODE
      -> VALUE

    NODE
      -> LINK_REFERENCE

    LINK_REFERENCE
      -> NEXT_OR_PREVIOUS_NODE

    INSERT_OR_DELETE
      -> LINK_REWRITING

    LINK_REWRITING
      -> STRUCTURAL_INVARIANT_CHECK
  }

  PROCESS HASH_STRUCTURE_REASONING {
    KEY
      -> HASH_FUNCTION

    HASH_FUNCTION
      -> HASH_VALUE

    HASH_VALUE
      -> BUCKET_OR_SLOT

    COLLISION
      -> COLLISION_RESOLUTION_STRATEGY

    LOOKUP
      -> KEY_COMPARISON
      -> VALUE_OR_NOT_FOUND
  }

  PROCESS TREE_REASONING {
    TREE
      -> ROOT

    ROOT
      -> CHILD_RELATIONS

    CHILD_RELATIONS
      -> SUBTREES

    SEARCH_TREE
      -> ORDERING_INVARIANT

    BALANCED_TREE
      -> BALANCE_INVARIANT

    UPDATE
      -> REBALANCING_IF_REQUIRED
  }

  PROCESS GRAPH_REASONING {
    GRAPH
      -> VERTEX_SET

    GRAPH
      -> EDGE_SET

    EDGE
      -> ENDPOINTS

    DIRECTED_EDGE
      -> SOURCE_AND_TARGET

    GRAPH_REPRESENTATION
      -> ADJACENCY_LIST_OR_MATRIX_OR_OTHER
  }

  PROCESS COMPLEXITY_REASONING {
    DATA_STRUCTURE + OPERATION
      -> INPUT_SIZE_MODEL

    INPUT_SIZE_MODEL
      -> COST_FUNCTION

    COST_FUNCTION
      -> BEST_AVERAGE_OR_WORST_CASE

    COST_FUNCTION
      -> ASYMPTOTIC_TIME_COMPLEXITY

    MEMORY_REQUIREMENTS
      -> SPACE_COMPLEXITY
  }

  PROCESS PERSISTENCE_REASONING {
    PERSISTENT_DATA_STRUCTURE_STATE(T1)
      + UPDATE
      -> NEW_STATE(T2)

    NEW_STATE(T2)
      -> PRESERVE_STATE(T1)

    T1 + T2
      -> STRUCTURAL_SHARING_IF_IMPLEMENTED
  }

  RULES {
    IF CONCRETE_STRUCTURE_IMPLEMENTS_ABSTRACT_DATA_TYPE
    THEN REQUIRE OPERATIONAL_CONTRACT_COMPATIBILITY

    IF OPERATION_CHANGES_STRUCTURE
    THEN CHECK POST_OPERATION_INVARIANTS

    IF COMPLEXITY_IS_ASSERTED
    THEN PRESERVE OPERATION_INPUT_MODEL_CASE_IMPLEMENTATION_AND_CONFIGURATION_CONTEXT

    IF HASH_TABLE_IS_ANALYSED
    THEN PRESERVE HASH_FUNCTION_LOAD_FACTOR_AND_COLLISION_STRATEGY

    IF BALANCED_TREE_IS_ASSERTED
    THEN REQUIRE DEFINED_BALANCE_INVARIANT

    IF GRAPH_IS_DIRECTED
    THEN PRESERVE EDGE_DIRECTION

    IF PERSISTENT_STRUCTURE_IS_UPDATED
    THEN PRESERVE OLD_AND_NEW_STATES

    IF SEMANTIC_IDENTIFIERS_DIFFER
    AND DATA_STRUCTURE_REFERENT_IS_SAME
    THEN APPLY SEMANTIC_EQUIVALENCE
  }

  CONFIDENCE {
    CONFIDENCE_SCORE =
      WEIGHT(
        STRUCTURE_IDENTITY_CERTAINTY,
        ABSTRACT_TYPE_CERTAINTY,
        IMPLEMENTATION_CERTAINTY,
        ELEMENT_AND_RELATION_COMPLETENESS,
        OPERATION_TRACE_COMPLETENESS,
        INVARIANT_EVIDENCE_QUALITY,
        COMPLEXITY_ANALYSIS_QUALITY,
        PROVENANCE_COMPLETENESS
      )

    LEVELS {
      HIGH
      MODERATE
      LOW
      INSUFFICIENT
    }

    IF IMPLEMENTATION_OR_CONFIGURATION_IS_UNKNOWN
    THEN REDUCE_OPERATION_COMPLEXITY_AND_MEMORY_CONFIDENCE

    IF INVARIANT_EVIDENCE_IS_PARTIAL
    THEN REDUCE_STRUCTURE_VALIDITY_CONFIDENCE

    IF COMPLETE_OPERATION_TRACE_CONFIRMS_STATE_AND_INVARIANTS
    THEN INCREASE_CONFIDENCE_SCORE
  }

  SEMANTIC_EQUIVALENCE {
    EQUIVALENCE_KEY =
      NORMALISE(
        ENTITY_TYPE,
        ABSTRACT_DATA_TYPE,
        IMPLEMENTATION,
        ELEMENT_TYPE,
        KEY_TYPE,
        CONFIGURATION,
        LANGUAGE_RUNTIME_CONTEXT
      )

    IF EQUIVALENCE_KEY(A) == EQUIVALENCE_KEY(B)
    THEN A SEMANTICALLY_EQUIVALENT_TO B

    ELSE PRESERVE_DISTINCT_ENTITIES
  }

  REASONING_CONSTRAINTS {
    ABSTRACT_DATA_TYPE != CONCRETE_DATA_STRUCTURE
    DATA_STRUCTURE != ELEMENT
    KEY != VALUE_IN_GENERAL
    INDEX != KEY_IN_ALL_STRUCTURES
    ARRAY != LINKED_LIST
    STACK != QUEUE
    SET != MULTISET
    MAP != HASH_TABLE
    TREE != BINARY_TREE
    BINARY_TREE != BINARY_SEARCH_TREE
    BINARY_SEARCH_TREE != BALANCED_TREE
    HEAP != FULLY_SORTED_STRUCTURE
    GRAPH != TREE
    HASH_COLLISION != DUPLICATE_KEY
    TIME_COMPLEXITY != WALL_CLOCK_TIME
    SPACE_COMPLEXITY != RAW_OBJECT_SIZE_WITHOUT_INPUT_MODEL
    BEST_CASE != AVERAGE_CASE
    AVERAGE_CASE != WORST_CASE
    PERSISTENT != IMMUTABLE_AS_IDENTICAL_CONCEPT
    COMPLEXITY_AND_MEMORY_BEHAVIOUR_DEPEND_ON_IMPLEMENTATION_AND_CONTEXT
    PROVENANCE_MUST_BE_PRESERVED
    UNCERTAINTY_MUST_NOT_BE_DISCARDED
  }

  VALIDATION {
    CHECK_ENTITY_TYPES
    CHECK_RELATION_DOMAINS_AND_RANGES
    CHECK_STRUCTURE_IDENTIFIER
    CHECK_ABSTRACT_DATA_TYPE
    CHECK_CONCRETE_IMPLEMENTATION
    CHECK_ELEMENT_KEY_AND_VALUE_TYPES
    CHECK_INDEX_RELATIONS
    CHECK_NODE_AND_EDGE_RELATIONS
    CHECK_SUPPORTED_OPERATIONS
    CHECK_PRECONDITIONS_AND_POSTCONDITIONS
    CHECK_INVARIANTS
    CHECK_ORDERING
    CHECK_SIZE_CAPACITY_AND_LOAD_FACTOR
    CHECK_COMPLEXITY_CONTEXT
    CHECK_MEMORY_LAYOUT
    CHECK_MUTABILITY_IMMUTABILITY_AND_PERSISTENCE
    CHECK_LANGUAGE_RUNTIME_AND_CONFIGURATION
    CHECK_PROVENANCE
    CHECK_CONFIDENCE
    CHECK_SEMANTIC_CONSISTENCY
  }

  OUTPUTS {
    NORMALISED_DATA_STRUCTURE_ENTITIES
    ABSTRACT_DATA_TYPE_RELATIONS
    IMPLEMENTATION_RELATIONS
    ELEMENT_KEY_VALUE_AND_INDEX_RELATIONS
    NODE_AND_EDGE_RELATIONS
    OPERATION_RELATIONS
    STRUCTURE_STATE_TRANSITIONS
    ARRAY_RELATIONS
    LINKED_STRUCTURE_RELATIONS
    HASH_STRUCTURE_RELATIONS
    TREE_RELATIONS
    GRAPH_RELATIONS
    INVARIANT_RELATIONS
    TIME_COMPLEXITY_RELATIONS
    SPACE_COMPLEXITY_RELATIONS
    MEMORY_LAYOUT_RELATIONS
    PERSISTENCE_AND_STRUCTURAL_SHARING_RELATIONS
    CONFIDENCE_SCORES
    EVIDENCE_LINKS
    PROVENANCE_RECORDS
    EXPLANATION_PATHS
  }

  UPDATE_MODEL {
    ON DATA_STRUCTURE_OPERATION {
      NORMALISE
      RESOLVE_STRUCTURE_AND_ELEMENT_IDENTITIES
      UPDATE_STRUCTURE_STATE
      UPDATE_ELEMENT_AND_RELATION_STATE
      UPDATE_SIZE_CAPACITY_AND_LOAD_FACTOR
      RECHECK_INVARIANTS
      UPDATE_OPERATION_RELATIONS
      UPDATE_CONFIDENCE
    }

    ON IMPLEMENTATION_CONFIGURATION_OR_RUNTIME_CHANGE {
      UPDATE_IMPLEMENTATION_CONTEXT
      REASSESS_COMPLEXITY
      REASSESS_MEMORY_LAYOUT
      RECHECK_SEMANTIC_EQUIVALENCE
      RECOMPUTE_AFFECTED_RELATIONS
      UPDATE_CONFIDENCE
      PRESERVE_VERSION_HISTORY
    }

    ON ONTOLOGY_REVISION {
      REMAP_TERMS
      CHECK_SEMANTIC_EQUIVALENCE
      IDENTIFY_DEPRECATED_TERMS
      MIGRATE_RELATIONSHIPS
      PRESERVE_PRIOR_VERSION_REFERENCES
    }
  }

  FLOW_HASH {
    HASH_INPUT =
      CANONICALISE(
        ENTITY_TYPES,
        RELATIONSHIPS,
        RULES,
        CONFIDENCE,
        SEMANTIC_EQUIVALENCE,
        REASONING_CONSTRAINTS,
        UPDATE_MODEL
      )

    FLOW_HASH = SHA256(HASH_INPUT)
  }

  AI_CONSUMPTION {
    INDEX {
      ONTOLOGY
      ENTITY_TYPES
      RELATIONSHIPS
      RULES
      OUTPUTS
    }

    RETRIEVE {
      BY_DATA_STRUCTURE
      BY_ABSTRACT_DATA_TYPE
      BY_IMPLEMENTATION
      BY_ELEMENT
      BY_KEY
      BY_INDEX
      BY_OPERATION
      BY_INVARIANT
      BY_ARRAY
      BY_LINKED_STRUCTURE
      BY_HASH_STRUCTURE
      BY_TREE
      BY_GRAPH
      BY_COMPLEXITY
      BY_MEMORY_LAYOUT
      BY_CONFIDENCE
    }

    REASON {
      APPLY_RELATIONSHIPS
      APPLY_RULES
      ANALYSE_ABSTRACT_TYPE_CONFORMANCE
      ANALYSE_ELEMENTS_AND_RELATIONS
      TRACE_STRUCTURE_OPERATIONS
      ANALYSE_ARRAYS
      ANALYSE_LINKED_STRUCTURES
      ANALYSE_HASH_STRUCTURES
      ANALYSE_TREES
      ANALYSE_GRAPHS
      ANALYSE_COMPLEXITY
      ANALYSE_PERSISTENCE
      CHECK_INVARIANTS
      CHECK_SEMANTIC_EQUIVALENCE
      PRESERVE_UNCERTAINTY
      TRACE_EVIDENCE
      TRACE_PROVENANCE
      GENERATE_EXPLANATION_PATH
    }

    RESPONSE_POLICY {
      DISTINGUISH_ABSTRACT_DATA_TYPE_FROM_CONCRETE_IMPLEMENTATION
      PRESERVE_STRUCTURE_OPERATION_ELEMENT_IMPLEMENTATION_LANGUAGE_RUNTIME_AND_CONFIGURATION_CONTEXT
      DISTINGUISH_COMPLEXITY_CASES
      DISTINGUISH_HASH_COLLISION_FROM_DUPLICATE_KEY
      PRESERVE_STRUCTURE_INVARIANTS_AND_VERSIONED_STATES
      RETURN_CONFIDENCE_WHEN_AVAILABLE
      RETURN_PROVENANCE_WHEN_AVAILABLE
      AVOID_UNSUPPORTED_DATA_STRUCTURE_INFERENCE
    }
  }

  TERMINAL {
    RESULT =
      VALIDATED(
        SEMANTICALLY_NORMALISED(
          EVIDENCE_LINKED(
            CONFIDENCE_AWARE(
              DATA_STRUCTURE_ONTOLOGY_KNOWLEDGE
            )
          )
        )
      )
  }
}

END FLOW