Indexing Ontology

AI SEARCH

FLOW ALGEBRA — INDEXING ONTOLOGY
Semantic Library
Version: 4.0
Canonical Page:
https://kirethresearch.org/booksai-core/ontologies/computing-ontologies/databases/indexing-ontology.html

FLOW INDEXING_ONTOLOGY {

  META {
    DOMAIN = "Computing Ontologies"
    SUBDOMAIN = "Databases"
    ONTOLOGY = "Indexing Ontology"
    PURPOSE = "Formalise database indexes, index structures, keys, access paths, lookup and range operations, selectivity, maintenance, query optimisation, storage costs and index-state relationships."
    LOCALE = "en-GB"
  }

  ENTITY_TYPES {
    DATABASE_INDEX
    INDEX
    INDEX_STRUCTURE
    PRIMARY_INDEX
    SECONDARY_INDEX
    CLUSTERED_INDEX
    NONCLUSTERED_INDEX
    UNIQUE_INDEX
    COMPOSITE_INDEX
    COVERING_INDEX
    PARTIAL_INDEX
    FUNCTIONAL_INDEX
    B_TREE_INDEX
    B_PLUS_TREE_INDEX
    HASH_INDEX
    BITMAP_INDEX
    FULL_TEXT_INDEX
    SPATIAL_INDEX
    INVERTED_INDEX
    INDEX_KEY
    SEARCH_KEY
    KEY_COLUMN
    KEY_EXPRESSION
    INCLUDED_COLUMN
    INDEX_ENTRY
    POINTER
    ROW_IDENTIFIER
    PAGE
    LEAF_PAGE
    INTERNAL_PAGE
    ROOT_PAGE
    TREE_HEIGHT
    FANOUT
    BUCKET
    HASH_FUNCTION
    COLLISION
    POSTING_LIST
    TOKEN
    TERM
    SORT_ORDER
    COLLATION
    LOOKUP
    POINT_LOOKUP
    RANGE_LOOKUP
    PREFIX_LOOKUP
    SEARCH_PREDICATE
    SARGABLE_PREDICATE
    NONSARGABLE_PREDICATE
    ACCESS_PATH
    INDEX_SCAN
    INDEX_SEEK
    TABLE_SCAN
    INDEX_ONLY_SCAN
    KEY_LOOKUP
    SELECTIVITY
    CARDINALITY
    DISTINCT_VALUE_COUNT
    DATA_DISTRIBUTION
    HISTOGRAM
    STATISTICS
    QUERY
    QUERY_PLAN
    QUERY_OPTIMISER
    COST_MODEL
    ESTIMATED_COST
    IO_COST
    CPU_COST
    STORAGE_COST
    INDEX_BUILD
    INDEX_CREATE
    INDEX_DROP
    INDEX_REBUILD
    INDEX_REORGANISE
    INDEX_MAINTENANCE
    PAGE_SPLIT
    FRAGMENTATION
    FILL_FACTOR
    CLUSTERING_FACTOR
    INDEX_BLOAT
    DUPLICATE_INDEX
    REDUNDANT_INDEX
    UNUSED_INDEX
    MISSING_INDEX
    INDEX_USAGE
    INDEX_STATISTICS
    INDEX_STATE
    VALID_INDEX
    INVALID_INDEX
    PARTITIONED_INDEX
    LOCAL_INDEX
    GLOBAL_INDEX
    DATABASE_TABLE
    COLUMN
    DATA_TYPE
    CONSTRAINT
    PRIMARY_KEY
    TRANSACTION
    LOCK
    CONFIGURATION
    LATENCY
    THROUGHPUT
    EVIDENCE
    CONFIDENCE_SCORE
    PROVENANCE_RECORD
  }

  RELATIONSHIPS {
    IS_A
    INSTANCE_OF
    BELONGS_TO
    INDEXES
    INDEXED_BY
    HAS_INDEX
    HAS_INDEX_STRUCTURE
    HAS_KEY
    HAS_KEY_COLUMN
    HAS_KEY_EXPRESSION
    INCLUDES_COLUMN
    HAS_ENTRY
    POINTS_TO
    HAS_ROOT
    HAS_INTERNAL_PAGE
    HAS_LEAF_PAGE
    HAS_HEIGHT
    HAS_FANOUT
    HAS_BUCKET
    USES_HASH_FUNCTION
    HAS_COLLISION
    HAS_POSTING_LIST
    HAS_TOKEN
    HAS_SORT_ORDER
    HAS_COLLATION
    SUPPORTS_LOOKUP
    SUPPORTS_RANGE
    SUPPORTS_PREFIX
    MATCHES_PREDICATE
    HAS_ACCESS_PATH
    SCANS
    SEEKS
    LOOKS_UP
    HAS_SELECTIVITY
    HAS_CARDINALITY
    HAS_STATISTICS
    HAS_DISTRIBUTION
    OPTIMISED_BY
    HAS_QUERY_PLAN
    HAS_COST_MODEL
    HAS_ESTIMATED_COST
    HAS_IO_COST
    HAS_CPU_COST
    HAS_STORAGE_COST
    BUILT_FROM
    CREATED_ON
    DROPPED_FROM
    REBUILT_BY
    REORGANISED_BY
    MAINTAINED_BY
    UPDATED_BY
    HAS_FRAGMENTATION
    HAS_FILL_FACTOR
    HAS_CLUSTERING_FACTOR
    HAS_BLOAT
    DUPLICATES
    REDUNDANT_WITH
    USED_BY
    HAS_USAGE
    HAS_STATE
    PARTITIONED_WITH
    CONSTRAINED_BY
    HAS_TRANSACTION
    LOCKED_BY
    HAS_CONFIGURATION
    HAS_LATENCY
    HAS_THROUGHPUT
    DERIVED_FROM
    INFERRED_FROM
    HAS_EVIDENCE
    HAS_CONFIDENCE
    HAS_PROVENANCE
    SEMANTICALLY_EQUIVALENT_TO
  }

  INPUTS {
    DATABASE_SCHEMA
    TABLE_METADATA
    COLUMN_METADATA
    DATA_TYPE_METADATA
    INDEX_DEFINITIONS
    INDEX_STRUCTURE_METADATA
    INDEX_KEY_METADATA
    INCLUDED_COLUMN_METADATA
    SORT_AND_COLLATION_METADATA
    INDEX_PAGE_DATA
    INDEX_STATISTICS
    TABLE_STATISTICS
    HISTOGRAM_DATA
    QUERY_DATA
    QUERY_PLANS
    ACCESS_PATH_DATA
    INDEX_USAGE_DATA
    INDEX_MAINTENANCE_LOGS
    FRAGMENTATION_DATA
    STORAGE_METRICS
    PERFORMANCE_METRICS
    TRANSACTION_AND_LOCK_DATA
    PARTITION_METADATA
    CONFIGURATION_DATA
    ONTOLOGY_TERMS
  }

  NORMALISE {
    STANDARDISE_INDEX_IDENTIFIERS
    NORMALISE_INDEX_TYPE_NAMES
    NORMALISE_INDEX_STRUCTURE_NAMES
    NORMALISE_TABLE_AND_COLUMN_IDENTIFIERS
    NORMALISE_INDEX_KEYS
    NORMALISE_INCLUDED_COLUMNS
    NORMALISE_SORT_ORDER
    NORMALISE_COLLATION
    NORMALISE_PAGE_AND_BUCKET_IDENTIFIERS
    NORMALISE_SELECTIVITY_AND_CARDINALITY_VALUES
    NORMALISE_STATISTICS
    NORMALISE_ACCESS_PATH_NAMES
    NORMALISE_INDEX_USAGE_METRICS
    NORMALISE_FRAGMENTATION_METRICS
    NORMALISE_STORAGE_AND_PERFORMANCE_UNITS
    NORMALISE_PARTITION_IDENTIFIERS
    RESOLVE_INDEX_TABLE_COLUMN_AND_ENTRY_IDENTITIES
    ALIGN_ONTOLOGY_TERMS
    REMOVE_DUPLICATES
    VALIDATE_METADATA
    PRESERVE_PROVENANCE
  }

  PROCESS INDEXING_REASONING_PIPELINE {
    INDEX_REFERENCE -> INDEX_IDENTIFICATION -> INDEX_TYPE_AND_STRUCTURE_RESOLUTION
    INDEX_TYPE_AND_STRUCTURE_RESOLUTION -> TABLE_COLUMN_AND_KEY_MAPPING -> ENTRY_AND_STORAGE_MAPPING
    ENTRY_AND_STORAGE_MAPPING -> ACCESS_PATH_ANALYSIS -> SELECTIVITY_AND_COST_ANALYSIS
    SELECTIVITY_AND_COST_ANALYSIS -> MAINTENANCE_AND_STATE_ANALYSIS -> QUERY_OPTIMISATION_CONTEXT -> VALIDATION -> OUTPUT
  }

  PROCESS B_TREE_REASONING {
    SEARCH_KEY -> ROOT_PAGE
    INTERNAL_PAGE -> KEY_COMPARISON -> CHILD_POINTER_SELECTION
    CHILD_POINTER_SELECTION -> NEXT_PAGE
    LEAF_PAGE -> MATCHING_INDEX_ENTRY
    MATCHING_INDEX_ENTRY -> ROW_IDENTIFIER_OR_STORED_VALUE
  }

  PROCESS HASH_INDEX_REASONING {
    SEARCH_KEY -> HASH_FUNCTION -> BUCKET
    BUCKET -> INDEX_ENTRIES
    COLLISION -> COLLISION_RESOLUTION
    MATCHING_KEY -> ROW_IDENTIFIER_OR_VALUE
  }

  PROCESS INVERTED_INDEX_REASONING {
    TEXT_VALUE -> TOKENISATION -> TERMS
    TERM -> POSTING_LIST
    QUERY_TERM -> POSTING_LIST_LOOKUP
    MULTIPLE_TERMS -> POSTING_LIST_INTERSECTION_UNION_OR_RANKING
  }

  PROCESS ACCESS_PATH_REASONING {
    QUERY_PREDICATE -> INDEXABLE_EXPRESSIONS
    INDEXABLE_EXPRESSIONS -> CANDIDATE_INDEXES
    CANDIDATE_INDEX -> SEEK_SCAN_OR_INDEX_ONLY_ACCESS
    ACCESS_PATH -> ROW_OR_VALUE_RETRIEVAL
  }

  PROCESS SARGABILITY_REASONING {
    SEARCH_PREDICATE -> INDEX_KEY_ALIGNMENT
    DIRECT_SEARCHABLE_FORM -> SARGABLE_PREDICATE
    FUNCTION_TRANSFORMATION_OR_NONSEARCHABLE_FORM -> NONSARGABLE_PREDICATE_CANDIDATE
    SARGABILITY -> ACCESS_PATH_OPTIONS
  }

  PROCESS SELECTIVITY_REASONING {
    PREDICATE -> COLUMN_OR_INDEX_STATISTICS
    STATISTICS -> DATA_DISTRIBUTION + DISTINCT_VALUE_COUNT + HISTOGRAM
    PREDICATE + STATISTICS -> SELECTIVITY_ESTIMATE
    INPUT_CARDINALITY * SELECTIVITY_ESTIMATE -> OUTPUT_CARDINALITY_ESTIMATE
  }

  PROCESS COVERING_INDEX_REASONING {
    QUERY_REQUIRED_COLUMNS -> INDEX_KEY_AND_INCLUDED_COLUMNS
    ALL_REQUIRED_COLUMNS_AVAILABLE_IN_INDEX -> COVERING_INDEX_CANDIDATE
    COVERING_INDEX_CANDIDATE -> INDEX_ONLY_ACCESS_IF_SUPPORTED
  }

  PROCESS COMPOSITE_INDEX_REASONING {
    MULTICOLUMN_INDEX -> ORDERED_KEY_COLUMNS
    QUERY_PREDICATES -> LEADING_KEY_ALIGNMENT
    LEADING_KEY_ALIGNMENT -> SEEK_OR_RANGE_ACCESS_POTENTIAL
    REMAINING_KEYS -> ADDITIONAL_FILTERING_OR_ORDERING_SUPPORT
  }

  PROCESS QUERY_OPTIMISATION_REASONING {
    QUERY -> CANDIDATE_ACCESS_PATHS
    CANDIDATE_ACCESS_PATHS -> TABLE_SCAN + APPLICABLE_INDEX_PATHS
    STATISTICS + COST_MODEL -> ESTIMATED_COSTS
    ESTIMATED_COSTS -> QUERY_OPTIMISER -> SELECTED_QUERY_PLAN
  }

  PROCESS INDEX_MAINTENANCE_REASONING {
    INSERT_OPERATION -> ADD_INDEX_ENTRY
    UPDATE_OPERATION -> UPDATE_OR_RELOCATE_INDEX_ENTRY
    DELETE_OPERATION -> REMOVE_OR_MARK_INDEX_ENTRY
    STRUCTURAL_CHANGE -> PAGE_SPLIT_MERGE_OR_REBALANCING_IF_REQUIRED
  }

  PROCESS FRAGMENTATION_REASONING {
    INDEX_PAGES -> LOGICAL_AND_PHYSICAL_ORDER_ANALYSIS
    PAGE_DENSITY -> SPACE_UTILISATION
    PAGE_SPLITS_AND_DELETIONS -> FRAGMENTATION_OR_BLOAT
    FRAGMENTATION_METRICS -> REBUILD_OR_REORGANISE_CANDIDATE
  }

  PROCESS INDEX_USAGE_REASONING {
    EXECUTION_PLANS -> INDEX_REFERENCES
    INDEX_REFERENCES -> SEEK_SCAN_LOOKUP_COUNTS
    WRITE_OPERATIONS -> MAINTENANCE_COUNTS
    READ_BENEFIT + WRITE_COST + STORAGE_COST -> INDEX_USAGE_PROFILE
  }

  RULES {
    IF INDEX_IS_IDENTIFIED THEN PRESERVE DATABASE_TABLE_INDEX_TYPE_KEY_ORDER_AND_CONFIGURATION_CONTEXT
    IF COMPOSITE_INDEX_IS_ANALYSED THEN PRESERVE ORDERED_KEY_COLUMN_CONTEXT
    IF COVERING_INDEX_IS_ASSERTED THEN REQUIRE QUERY_REQUIRED_COLUMNS_ARE_AVAILABLE_FROM_INDEX_STRUCTURE
    IF INDEX_ACCESS_IS_ASSERTED_OPTIMAL THEN REQUIRE QUERY_STATISTICS_COST_MODEL_AND_ALTERNATIVE_ACCESS_PATH_CONTEXT
    IF UNIQUE_INDEX_IS_ASSERTED THEN DISTINGUISH INDEX_UNIQUENESS_FROM_PRIMARY_KEY_ROLE
    IF INDEX_IS_UNUSED_IN_OBSERVED_WORKLOAD THEN DO_NOT_AUTOMATICALLY_ASSERT_INDEX_IS_UNNECESSARY
    IF SEMANTIC_IDENTIFIERS_DIFFER AND INDEX_REFERENT_IS_SAME THEN APPLY SEMANTIC_EQUIVALENCE
  }

  CONFIDENCE {
    CONFIDENCE_SCORE = WEIGHT(INDEX_IDENTITY_CERTAINTY, INDEX_DEFINITION_COMPLETENESS, KEY_AND_COLUMN_CERTAINTY, STRUCTURE_AND_STORAGE_EVIDENCE, STATISTICS_FRESHNESS, QUERY_PLAN_AND_USAGE_EVIDENCE, MAINTENANCE_AND_FRAGMENTATION_EVIDENCE, PROVENANCE_COMPLETENESS)
    LEVELS { HIGH MODERATE LOW INSUFFICIENT }
    IF INDEX_STATISTICS_ARE_STALE_OR_MISSING THEN REDUCE_SELECTIVITY_AND_COST_CONFIDENCE
    IF WORKLOAD_EVIDENCE_IS_PARTIAL THEN REDUCE_UNUSED_OR_REDUNDANT_INDEX_CONFIDENCE
  }

  SEMANTIC_EQUIVALENCE {
    EQUIVALENCE_KEY = NORMALISE(ENTITY_TYPE, DATABASE_IDENTIFIER, TABLE_IDENTIFIER, INDEX_IDENTIFIER, INDEX_TYPE, ORDERED_KEY_COLUMNS, INCLUDED_COLUMNS, FILTER_OR_PREDICATE)
    IF EQUIVALENCE_KEY(A) == EQUIVALENCE_KEY(B) THEN A SEMANTICALLY_EQUIVALENT_TO B
    ELSE PRESERVE_DISTINCT_ENTITIES
  }

  REASONING_CONSTRAINTS {
    INDEX != TABLE
    INDEX != CONSTRAINT
    INDEX != PRIMARY_KEY
    UNIQUE_INDEX != PRIMARY_KEY_AS_IDENTICAL_CONCEPT
    B_TREE_INDEX != HASH_INDEX
    INDEX_SCAN != INDEX_SEEK
    COMPOSITE_INDEX != MULTIPLE_INDEPENDENT_INDEXES
    KEY_COLUMN != INCLUDED_COLUMN
    INDEX_KEY_ORDER_MAY_AFFECT_ACCESS_PATH_CAPABILITY
    SELECTIVITY != CARDINALITY
    ESTIMATED_COST != ACTUAL_RUNTIME
    FRAGMENTATION != INDEX_BLOAT_AS_IDENTICAL_METRIC
    UNUSED_INDEX != USELESS_INDEX
    INDEX_MAINTENANCE_COST_MUST_BE_CONSIDERED_WITH_READ_BENEFIT
    INDEX_EFFECTIVENESS_DEPENDS_ON_WORKLOAD_DATA_DISTRIBUTION_ENGINE_AND_CONFIGURATION
    PROVENANCE_MUST_BE_PRESERVED
    UNCERTAINTY_MUST_NOT_BE_DISCARDED
  }

  VALIDATION {
    CHECK_ENTITY_TYPES
    CHECK_RELATION_DOMAINS_AND_RANGES
    CHECK_INDEX_IDENTIFIER
    CHECK_DATABASE_AND_TABLE_REFERENCE
    CHECK_INDEX_TYPE
    CHECK_INDEX_STRUCTURE
    CHECK_KEY_COLUMNS
    CHECK_INCLUDED_COLUMNS
    CHECK_SORT_ORDER_AND_COLLATION
    CHECK_INDEX_ENTRIES
    CHECK_PAGE_OR_BUCKET_STRUCTURE
    CHECK_ACCESS_PATHS
    CHECK_SARGABILITY
    CHECK_SELECTIVITY_AND_CARDINALITY
    CHECK_STATISTICS
    CHECK_QUERY_PLAN_USAGE
    CHECK_INDEX_BUILD_STATE
    CHECK_MAINTENANCE_RELATIONS
    CHECK_FRAGMENTATION_AND_BLOAT
    CHECK_REDUNDANCY_CANDIDATES
    CHECK_PARTITIONED_INDEX_CONTEXT
    CHECK_TRANSACTION_AND_LOCK_CONTEXT
    CHECK_CONFIGURATION
    CHECK_PROVENANCE
    CHECK_CONFIDENCE
    CHECK_SEMANTIC_CONSISTENCY
  }

  OUTPUTS {
    NORMALISED_INDEX_ENTITIES
    INDEX_TYPE_RELATIONS
    INDEX_STRUCTURE_RELATIONS
    KEY_AND_INCLUDED_COLUMN_RELATIONS
    PAGE_BUCKET_AND_ENTRY_RELATIONS
    ACCESS_PATH_RELATIONS
    SEEK_SCAN_AND_LOOKUP_RELATIONS
    SARGABILITY_RELATIONS
    SELECTIVITY_AND_CARDINALITY_RELATIONS
    QUERY_PLAN_RELATIONS
    COST_RELATIONS
    COVERING_INDEX_RELATIONS
    COMPOSITE_INDEX_RELATIONS
    INDEX_BUILD_RELATIONS
    INDEX_MAINTENANCE_RELATIONS
    FRAGMENTATION_AND_BLOAT_RELATIONS
    INDEX_USAGE_RELATIONS
    DUPLICATE_AND_REDUNDANT_INDEX_RELATIONS
    PARTITIONED_INDEX_RELATIONS
    PERFORMANCE_RELATIONS
    CONFIDENCE_SCORES
    EVIDENCE_LINKS
    PROVENANCE_RECORDS
    EXPLANATION_PATHS
  }

  UPDATE_MODEL {
    ON INDEX_DEFINITION_SCHEMA_OR_CONFIGURATION_CHANGE {
      NORMALISE
      RESOLVE_INDEX_TABLE_COLUMN_AND_ENTRY_IDENTITIES
      UPDATE_INDEX_STRUCTURE
      UPDATE_KEYS_AND_INCLUDED_COLUMNS
      UPDATE_ACCESS_PATH_CAPABILITIES
      UPDATE_STATISTICS_AND_COST_CONTEXT
      REASSESS_REDUNDANCY_AND_USAGE
      UPDATE_CONFIDENCE
      PRESERVE_VERSION_HISTORY
    }
    ON NEW_QUERY_PLAN_OR_USAGE_EVIDENCE {
      LINK_EVIDENCE
      UPDATE_INDEX_USAGE
      UPDATE_SEEK_SCAN_AND_LOOKUP_RELATIONS
      UPDATE_SELECTIVITY_AND_CARDINALITY_EVIDENCE
      UPDATE_PERFORMANCE_PROFILE
      UPDATE_CONFIDENCE
      RECORD_PROVENANCE
    }
  }

  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_INDEX BY_INDEX_TYPE BY_TABLE BY_KEY_COLUMN BY_ACCESS_PATH BY_QUERY BY_QUERY_PLAN BY_SELECTIVITY BY_CARDINALITY BY_USAGE BY_FRAGMENTATION BY_CONFIDENCE }
    REASON { APPLY_RELATIONSHIPS APPLY_RULES ANALYSE_B_TREE_INDEXES ANALYSE_HASH_INDEXES ANALYSE_INVERTED_INDEXES ANALYSE_ACCESS_PATHS ANALYSE_SARGABILITY ESTIMATE_SELECTIVITY ANALYSE_COVERING_INDEXES ANALYSE_COMPOSITE_INDEXES ANALYSE_QUERY_OPTIMISATION ANALYSE_INDEX_MAINTENANCE ANALYSE_FRAGMENTATION ANALYSE_INDEX_USAGE CHECK_SEMANTIC_EQUIVALENCE PRESERVE_UNCERTAINTY TRACE_EVIDENCE TRACE_PROVENANCE GENERATE_EXPLANATION_PATH }
    RESPONSE_POLICY { DISTINGUISH_INDEX_FROM_TABLE_KEY_AND_CONSTRAINT DISTINGUISH_INDEX_SCAN_SEEK_AND_INDEX_ONLY_ACCESS PRESERVE_DATABASE_TABLE_INDEX_TYPE_KEY_ORDER_STATISTICS_WORKLOAD_AND_CONFIGURATION_CONTEXT DISTINGUISH_ESTIMATED_FROM_ACTUAL_PERFORMANCE PRESERVE_MAINTENANCE_STORAGE_AND_USAGE_COSTS RETURN_CONFIDENCE_WHEN_AVAILABLE RETURN_PROVENANCE_WHEN_AVAILABLE AVOID_UNSUPPORTED_INDEX_INFERENCE }
  }

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

END FLOW