Join Path Discovery

This foundational technique identifies potential join keys by analyzing column properties. Primary key detection scans for columns with high cardinality (approaching 100% unique values) and no nulls. Foreign key detection then searches other tables for columns with a high percentage of their values contained within a candidate primary key, establishing a referential integrity relationship. Algorithms often use inclusion dependency tests and statistical sampling to validate these links efficiently across large datasets.

This technique infers relationships based on the meaning of column names and data, not just values. It uses:

• Natural Language Processing (NLP) on column headers to find synonyms (e.g., cust_id, customer_id, client_identifier).
• Data domain inference to match columns of the same logical type (e.g., email addresses, phone numbers, ISO country codes).
• Embedding similarity where column names and sample values are converted to vectors; high cosine similarity suggests a semantic relationship, enabling joins even with different naming conventions.

This statistical method quantifies how well the values in one column are contained within another. It calculates the inclusion coefficient—the percentage of distinct values in a candidate foreign key column that exist in a candidate primary key column. A high coefficient (e.g., >95%) strongly suggests a joinable relationship. This is crucial for discovering joins in legacy systems without documented foreign keys or where business logic defines relationships.

This technique models the entire database as a graph to discover complex, multi-hop join paths. Nodes represent tables and columns. Edges represent discovered relationships (e.g., foreign key links, semantic similarity). Graph traversal algorithms (like breadth-first search) can then find all possible join paths between two tables of interest, even through intermediary tables. This is essential for understanding the full data lineage and network of connections within a schema.

This advanced technique identifies if the value of one column set uniquely determines another column's value within a table (e.g., order_id determines customer_id). Discovering these dependencies helps:

• Simplify join logic by identifying the minimal key needed for a relationship.
• Validate data quality by exposing violations of expected business rules.
• Infer transitive relationships that can suggest indirect join paths across multiple datasets based on shared deterministic attributes.

Once candidate paths are identified, this technique predicts their performance impact. It uses descriptive statistics from profiling (cardinality, value distribution, data skew) to estimate:

• Join selectivity: The expected number of output rows, crucial for avoiding Cartesian products.
• Execution cost: The computational load of the join operation. This allows the system to rank discovered paths by efficiency, prioritizing high-selectivity joins on indexed columns to recommend optimal queries for analytics engines.

Schema discovery is the automated process of inferring the structural metadata of a dataset, including column names, data types, constraints, and potential relationships, without prior documentation. It is a prerequisite for join path discovery, as understanding table structure is essential for identifying potential join keys.

• Automatically maps column names, data types (e.g., INTEGER, VARCHAR, DATE), and nullability constraints.
• Infers primary keys and unique constraints by analyzing value cardinality.
• Outputs a schema definition (like a CREATE TABLE statement) that serves as the foundational blueprint for further relationship analysis.

Foreign key detection is the automated process of identifying columns in one table that refer to the primary key in another table, revealing explicit referential integrity relationships. It is a core component of join path discovery, focusing on pre-defined relational links.

• Analyzes column names, data types, and value overlap to hypothesize relationships (e.g., customer_id in an orders table likely references id in a customers table).
• Uses statistical profiling on value sets to confirm referential integrity, checking if values in the potential foreign key column are a subset of values in the candidate primary key column.
• Distinguishes from join path discovery by focusing on engineered relationships, whereas join path discovery also uncovers latent, semantic relationships not enforced by database constraints.

Data relationship mapping is the process of discovering and documenting the connections between different data entities, attributes, and tables, often visualized as a graph or network. Join path discovery is a specific application that generates the edges (potential joins) within this larger relationship map.

• Creates a holistic view of how data assets interconnect, beyond just foreign keys.
• Incorporates business logic and semantic relationships (e.g., a product_sku column and a material_id column may be joinable via a separate mapping table).
• Output is often a graph where nodes are tables/columns and edges are the discovered relationships, providing a searchable map for data exploration and impact analysis.

Functional dependency discovery is the automated process of identifying relationships between columns where the value of one set of columns uniquely determines the value of another set within the same table. This informs join path discovery by revealing complex keys and normalized structures.

• Identifies rules like {country_code, phone_number} → {city}, suggesting a composite key.
• Helps in database normalization analysis by spotting transitive dependencies.
• Provides context for join conditions; discovering that department_id determines manager_id can suggest alternative or additional join paths through organizational hierarchy tables.

Cross-dataset analysis is a profiling technique that compares multiple datasets to identify overlaps, differences, and relationships, such as common keys, shared records, or contradictory values. It is the broader analytical umbrella under which join path discovery operates.

• Measures overlap using metrics like Jaccard similarity on column value sets to quantify potential relationship strength.
• Identifies contradictions where the same entity has different attribute values across tables, highlighting data quality issues relevant to join reliability.
• Supports data integration and master data management initiatives by systematically revealing how disparate sources connect.

Entity resolution is the process of identifying, matching, and linking records that refer to the same real-world entity across different data sources, despite inconsistencies or variations in the data. It is a more advanced, semantic counterpart to simple join path discovery based on exact key matches.

• Employs fuzzy matching, probabilistic linking, and machine learning to match records without perfect keys (e.g., matching "Jon Doe Corp" with "John Doe Corporation").
• Crucial when join paths are ambiguous or based on non-unique, dirty data like names and addresses.
• Outputs a persistent identifier that can be used to create a definitive join key across systems, effectively creating a new, clean join path post-resolution.