Hubbry Logo
Transitive dependencyTransitive dependencyMain
Open search
Transitive dependency
Community hub
Transitive dependency
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Transitive dependency
Transitive dependency
Transitive dependency
View on Wikipedia
from Wikipedia
A depends on B, which depends on C. Therefore, A is a transitive dependent of C.
Illustration of a transitive dependency

A transitive dependency is an indirect dependency relationship between software components. This kind of dependency is held by virtue of a transitive relation from a component that the software depends on directly.

Computer programs

[edit]

In a computer program a direct dependency is functionality from a library, or API, or any software component that is referenced directly by the program itself. A transitive dependency is any dependency induced by a different component, that in turn is directly or indirectly referenced by the program. E.g. a call to a log() function may induce a transitive dependency to a library that manages the I/O of writing a message to a log file.

Dependencies and transitive dependencies can be resolved at different times, depending on how the computer program is assembled and/or executed: e.g. a compiler can have a link phase where the dependencies are resolved. Sometimes the build system even allows management of the transitive dependencies.[citation needed]

Similarly, when a computer uses services, a computer program can depend on a service that should be started before to execute the program. A transitive dependency in such case is any other service that the service we depend directly on depends on, e.g. a web browser depends on a Domain Name Resolution service to convert a web URL in an IP address; the DNS will depend on a networking service to access a remote name server. The Linux boot system systemd is based on a set of configurations that declare the dependencies of the modules to be started: at boot time systemd analyzes all the transitive dependencies to decide the execution order of each module to start.

Database management systems

[edit]
See also: Database normalization § Satisfying 3NF, Functional dependency, and Armstrong's axioms § Axiom of transitivity

Suppose entities A, B, and C exist such that the following statements hold:

  1. A → B direct dependency relationship exists.
  2. There is no B → A relationship.
  3. B → C direct dependency relationship exists.

Then the functional dependency A → C is a transitive dependency (which follows the axiom of transitivity).

In database normalization of relational databases, one of the important features of third normal form is that it excludes certain types of transitive dependencies. E.F. Codd, the inventor of the relational model, introduced the concepts of transitive dependence and third normal form in 1971.[1]

Example

[edit]

A transitive dependency occurs in the following relation:

Book Genre Author Author nationality
Twenty Thousand Leagues Under the Seas Science fiction Jules Verne French
Journey to the Center of the Earth Science fiction Jules Verne French
Leaves of Grass Poetry Walt Whitman American
Anna Karenina Literary fiction Leo Tolstoy Russian
A Confession Autobiographical story Leo Tolstoy Russian

The functional dependency {Book} → {Author nationality} emerges; that is, if we know the book, we can know the author's nationality. Furthermore:

  • {Book} → {Author}
  • {Author} does not → {Book}
  • {Author} → {Author nationality}

Therefore {Book} → {Author nationality} is a transitive dependency.

Notes

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Transitive dependency

View on Grokipedia
from Grokipedia
A transitive dependency is a term used in both and . In , a transitive dependency refers to an indirect dependency between software components, where a module depends on another module that in turn depends on a third. For example, if project A depends on library B, and library B depends on library C, then C is a transitive dependency of A. This can lead to complex dependency graphs in package management systems like Maven or npm. In , a transitive dependency occurs when a non-key attribute in a relation functionally depends on another non-key attribute, which itself depends on the , rather than directly on the . This indirect relationship violates the third normal form (3NF) and can introduce data redundancies, insertion anomalies, update anomalies, and deletion anomalies in relational databases. Transitive dependencies arise in unnormalized or partially normalized tables where attributes are not fully dependent on the entire , often during the early stages of . For instance, in an employee table with emp_num, attributes dept_num (department number), and dept_name (department name), if dept_name depends on dept_num rather than directly on emp_num, a transitive dependency exists because multiple employees in the same department would redundantly store the department name. To eliminate such dependencies and achieve 3NF, the relation is decomposed into separate tables: one for employee details (with emp_num as and dept_num as ) and another for department details (with dept_num as ). The concept, rooted in Edgar F. Codd's , ensures by requiring that every non-key attribute depends only on the and not transitively through other attributes. Identifying transitive dependencies involves analyzing functional dependencies in the relation; if a non-prime attribute C depends on a non-prime attribute B (where B depends on the A), then A → B → C forms a transitive dependency that must be resolved through normalization. This process is essential for scalable database systems, reducing storage needs and maintaining consistency across operations like joins and queries.

In software engineering

Definition and occurrence

In software engineering, a transitive dependency refers to an indirect dependency in which a library or module required by a direct dependency of a project is automatically included to fulfill the requirements of the overall software build or runtime environment. These dependencies arise recursively, meaning that dependencies of transitive dependencies are also resolved and incorporated, forming a potentially deep dependency tree. Transitive dependencies occur within dependency graphs managed by package managers and build systems, where projects declare direct dependencies on external libraries, and those libraries in turn rely on others. For instance, in the Java ecosystem using Maven, if a project A depends on library B, and B depends on library C, then C becomes a transitive dependency of A, propagating through the project's POM (Project Object Model) file. Similarly, in with , installing a package like foo triggers the installation of its dependencies in a nested node_modules structure, where sub-dependencies (transitive ones) are hoisted to higher levels to optimize disk space and avoid duplication, unless version conflicts dictate otherwise. In Python's pip ecosystem, transitive dependencies emerge when a direct dependency like tea requires spoon, and spoon requires cup; thus, cup is transitively pulled in during installation. The dependency resolution process in build tools systematically includes transitive dependencies to ensure completeness. First, the tool parses the project's configuration file (e.g., pom.xml in Maven, package.json in , or requirements.txt/pyproject.toml in pip) to identify direct dependencies and their version constraints. Second, it recursively traverses the by querying repositories (such as Maven Central, npm registry, or PyPI) to fetch metadata for each dependency's requirements. Third, the tool applies resolution rules to select compatible versions, such as Maven's "nearest definition" mediation (prioritizing the closest declared version in the graph) or pip's backtracking algorithm to find the latest satisfying set without conflicts. Finally, the resolved transitive dependencies are downloaded, installed, and made available for compilation, testing, or runtime, often generating a lockfile (e.g., package-lock.json in ) to pin exact versions for reproducibility. This automation simplifies development but can lead to large, complex graphs if not managed carefully.

Implications for project management

Transitive dependencies introduce significant risks in , primarily through version conflicts, unnecessary bloat, and vulnerabilities. The diamond dependency problem occurs when multiple direct dependencies rely on different versions of the same transitive library, leading to compatibility issues and potential runtime errors that complicate integration and maintenance. Bloated dependencies, where unused libraries are included via transitive chains, contribute to unnecessary code inclusions that inflate project size and introduce hidden inefficiencies. risks arise from unvetted indirect libraries, as developers may overlook vulnerabilities in transitive components that propagate or exploits across the . These risks manifest in broader impacts on the lifecycle, including prolonged build times, expanded deployment footprints, and challenges in ensuring . Transitive dependencies can extend pipelines by requiring compilation and testing of extraneous code, with studies showing approximately 56% of build time wasted on unused dependencies in projects. Larger deployment sizes result from bundled unused artifacts, increasing storage costs and network transfer times in environments. suffers as varying transitive versions across environments lead to inconsistent builds, hindering collaboration and deployment reliability in distributed teams. A notable historical example is the 2018 event-stream incident in the ecosystem, where a maintainer injected a malicious transitive dependency (flatmap-stream) into the popular event-stream package, affecting numerous projects by attempting to steal credentials from code using bitcoinjs-lib. This supply-chain attack underscored the dangers of indirect dependencies, prompting widespread audits and highlighting the need for vigilant monitoring. Tools and strategies for , such as dependency auditing and lockfiles, are explored in subsequent sections.

Tools and mitigation strategies

Several strategies exist for managing transitive dependencies in software engineering, primarily through explicit control mechanisms in build and package management systems. One common approach is explicit dependency declaration, where developers specify direct dependencies in configuration files to override or enforce specific versions of transitive ones, preventing unintended propagation from upstream libraries. For instance, in Maven, the <dependencyManagement> section allows defining versions that apply to transitive dependencies without adding them as direct ones, ensuring consistency across the project. Similarly, npm's overrides feature, introduced in version 8, enables forcing specific versions or replacements for transitive packages, addressing issues like security vulnerabilities without altering parent dependencies. Dependency locking provides by capturing the exact resolved versions of all dependencies, including transitives, in a lockfile. In , the package-lock.json file locks versions to avoid variations from semantic versioning ranges, mitigating risks like version conflicts that can lead to runtime errors. employs resolution rules, such as forcing versions or substituting modules, to lock transitive dependencies during builds, ensuring deterministic outcomes across environments. Exclusion rules offer a targeted way to remove unwanted transitive dependencies from the resolution graph. Maven supports <exclusions> within dependency declarations to block specific artifacts from propagating, useful for eliminating redundant or conflicting libraries. Gradle provides similar functionality via exclude methods in dependency configurations or resolution strategies, allowing fine-grained control over what enters the classpath. Tools facilitate identification and automation of transitive dependency management. Maven's dependency:tree command visualizes the full , highlighting transitives for analysis and exclusion planning. In npm, npm audit scans for vulnerabilities in both direct and transitive dependencies, generating reports to guide remediation. Dependabot, integrated with , automates security updates by creating pull requests for vulnerable transitive dependencies, supporting ecosystems like npm and Maven while respecting lockfiles. Best practices emphasize proactive oversight to minimize transitive dependency issues. Regular auditing, such as running dependency analyzers weekly, helps detect outdated or vulnerable transitives early, reducing exposure to risks. Adopting monorepos centralizes dependency management across projects, using tools like workspaces or Bazel to share and version-lock common libraries, which simplifies transitive resolution in large-scale developments. Finally, adhering to semantic versioning (SemVer) in dependency specifications—using ranges like ^1.2.3 for minor updates—limits breaking changes in transitives.

In database theory

Definition and functional dependencies

In theory, a is a constraint between two sets of attributes in a relation, where one set (the ) uniquely determines the values of the other set. Formally, if XX and YY are sets of attributes in a relation RR, then X→YX \to Y holds if, for every pair of tuples in RR that agree on XX, they also agree on YY. This concept ensures by capturing how attribute values are interrelated, with determinants acting as unique identifiers for dependent attributes. Functional dependencies can be partial, where a non-prime attribute depends on only part of a composite , or transitive, involving indirect chains of determination. These dependencies form the foundation for analyzing and structuring relations to prevent redundancies and anomalies. A transitive dependency arises when a non-prime attribute in a relation functionally depends on another non-prime attribute, which itself depends on a , creating an indirect path of determination. For instance, if attributes satisfy A→BA \to B and B→CB \to C, where AA is a , BB and CC are non-prime attributes, then CC is transitively dependent on AA via BB. This type of dependency violates direct reliance on keys, leading to potential data inconsistencies if not addressed, as changes to the intermediate attribute BB may not propagate correctly to CC. Transitive dependencies highlight the need to distinguish between direct and indirect functional relationships in relation design. The concepts of functional and transitive dependencies originated in E.F. Codd's development of the relational model during the 1970s, building on his foundational 1970 paper that introduced relations as the core structure for data representation. In his 1972 work, Codd formalized transitive dependencies as part of efforts to refine the model, emphasizing their role in eliminating update anomalies and ensuring relation simplicity. These ideas were pivotal in establishing normalization principles, which aim to preserve data integrity without excessive redundancy in large shared databases.

Role in normalization

Transitive dependencies are central to the concept of (3NF) in , as they represent a key violation that introduces redundancy and anomalies. Specifically, a transitive dependency arises when a non-prime attribute functionally depends on another non-prime attribute via an intermediate non-key attribute, rather than directly on a ; this contravenes 3NF, which mandates that no non-prime attribute transitively depends on a , ensuring all dependencies are direct or involve superkeys or prime attributes. As outlined by E.F. Codd, such dependencies propagate inconsistencies during updates, insertions, or deletions, compromising relational integrity. Within the broader normalization hierarchy, databases advance from (1NF), which enforces atomic attribute values, to (2NF), which eliminates partial dependencies on composite keys, culminating in 3NF to eradicate transitive dependencies. This progression ensures progressive refinement of the relational schema; while 3NF fully addresses transitive dependencies, higher forms like Boyce-Codd normal form (BCNF) impose stricter criteria—requiring every in a to be a —which may necessitate further to resolve non-transitive issues not covered by 3NF. Eliminating transitive dependencies through 3NF normalization delivers core benefits, including minimized , prevention of update anomalies that could lead to inconsistent information, bolstered , and streamlined database maintenance by isolating related attributes into separate relations. However, these gains come with trade-offs, such as an increase in the number of tables and greater dependence on join operations, which can elevate query complexity and potentially impact performance in large-scale systems.

Detection and resolution example

Consider a sample relation schema for an employee database, denoted as R(EmployeeID,DepartmentID,DepartmentName,[Location](/page/Location))R(\text{EmployeeID}, \text{DepartmentID}, \text{DepartmentName}, \text{[Location](/page/Location)}), where EmployeeID is the . The functional dependencies include EmployeeID → DepartmentID, DepartmentID → DepartmentName, and DepartmentID → Location. To detect transitive dependencies, one approach is to construct a dependency diagram, which visually represents the functional dependencies as directed arrows between attributes. In this diagram, an arrow from EmployeeID to DepartmentID indicates direct dependence, while arrows from DepartmentID to DepartmentName and from DepartmentID to reveal intermediate dependencies. The resulting chain—EmployeeID → DepartmentID → DepartmentName and EmployeeID → DepartmentID → —identifies DepartmentName and as transitively dependent on the primary key EmployeeID through the non-key attribute DepartmentID. An alternative detection method uses attribute closure, which computes the set of all attributes functionally determined by a given attribute set under the provided dependencies. The closure of {EmployeeID}, denoted EmployeeID+^+, starts with EmployeeID and applies the dependencies iteratively: it includes DepartmentID (from EmployeeID → DepartmentID), then adds DepartmentName and (from DepartmentID → DepartmentName and DepartmentID → Location). Since DepartmentName and appear in the closure but depend indirectly via DepartmentID, this confirms the transitive dependencies. To resolve these transitive dependencies and achieve , decompose the relation into two projections that eliminate the indirect paths while preserving all dependencies and lossless join. The resulting schemas are:
  • R1(EmployeeID,DepartmentID)R_1(\text{EmployeeID}, \text{DepartmentID}), with EmployeeID as and the direct dependency EmployeeID → DepartmentID.
  • R2(DepartmentID,DepartmentName,Location)R_2(\text{DepartmentID}, \text{DepartmentName}, \text{Location}), with DepartmentID as and dependencies DepartmentID → DepartmentName, DepartmentID → Location.
In SQL-like notation, the original unnormalized schema might appear as:

sql

CREATE TABLE Employee ( EmployeeID INT [PRIMARY KEY](/page/Primary_key), DepartmentID INT, DepartmentName VARCHAR(50), Location VARCHAR(50) );

CREATE TABLE Employee ( EmployeeID INT [PRIMARY KEY](/page/Primary_key), DepartmentID INT, DepartmentName VARCHAR(50), Location VARCHAR(50) );

After decomposition:

sql

CREATE TABLE Employee ( EmployeeID INT [PRIMARY KEY](/page/Primary_key), DepartmentID INT, [FOREIGN KEY](/page/Foreign_key) (DepartmentID) REFERENCES Department(DepartmentID) ); CREATE TABLE Department ( DepartmentID INT [PRIMARY KEY](/page/Primary_key), DepartmentName VARCHAR(50), Location VARCHAR(50) );

CREATE TABLE Employee ( EmployeeID INT [PRIMARY KEY](/page/Primary_key), DepartmentID INT, [FOREIGN KEY](/page/Foreign_key) (DepartmentID) REFERENCES Department(DepartmentID) ); CREATE TABLE Department ( DepartmentID INT [PRIMARY KEY](/page/Primary_key), DepartmentName VARCHAR(50), Location VARCHAR(50) );

This process follows the projection method for , replacing the original relation with its lossless . To verify elimination, reconstruct dependency diagrams or recompute attribute closures for the new relations. For R1R_1, EmployeeID+^+ = {EmployeeID, DepartmentID}, showing only direct dependence with no transitive paths. For R2R_2, DepartmentID+^+ = {DepartmentID, DepartmentName, Location}, where DepartmentName and Location depend directly on the key without intermediates. No transitive dependencies remain, confirming the schema is in .

References

  1. https://maven.apache.org/guides/introduction/introduction-to-dependency-mechanism.html
  2. https://www.ibm.com/think/topics/database-normalization
  3. https://www.sciencedirect.com/topics/computer-science/transitive-dependency
  4. https://docs.gradle.org/current/userguide/declaring_dependencies.html
  5. https://docs.npmjs.com/cli/v10/configuring-npm/folders
  6. https://pip.pypa.io/en/stable/topics/dependency-resolution/
  7. https://bazel.build/basics/dependencies
  8. https://link.springer.com/article/10.1007/s10664-020-09914-8
  9. https://www.endorlabs.com/learn/demystifying-transitive-dependency-vulnerabilities-sca
  10. https://rebels.cs.uwaterloo.ca/papers/fse2024_weeraddana.pdf
  11. https://apiiro.com/glossary/transitive-dependencies/
  12. https://arxiv.org/html/2402.00424v1
  13. https://blog.npmjs.org/post/180565383195/details-about-the-event-stream-incident
  14. https://dl.acm.org/doi/pdf/10.1145/3517208.3523753
  15. https://maven.apache.org/guides/introduction/introduction-to-optional-and-excludes-dependencies.html
  16. https://docs.gradle.org/current/userguide/resolution_rules.html
  17. https://docs.gradle.org/current/userguide/dependency_resolution.html
  18. https://docs.github.com/en/code-security/dependabot/dependabot-security-updates/about-dependabot-security-updates
  19. https://www.thoughtworks.com/en-us/insights/blog/agile-engineering-practices/monorepo-vs-multirepo
  20. https://www.sciencedirect.com/science/article/abs/pii/S0164121216300243
  21. https://forum.thethirdmanifesto.com/wp-content/uploads/asgarosforum/987737/00-efc-further-normalization.pdf
  22. https://zimmer.fresnostate.edu/~sasanr/Teaching-Material/MIS/DBMS/Guide-To-5NF.pdf
  23. https://dl.acm.org/doi/10.1145/362384.362685
  24. https://www.semanticscholar.org/paper/Further-Normalization-of-the-Data-Base-Relational-Codd/7be40103ca2c4114e07bb327bf5f902d5b081808
  25. https://opentextbc.ca/dbdesign01/chapter/chapter-12-normalization/
  26. https://dl.acm.org/doi/pdf/10.1145/320107.320115
Add your contribution
Related Hubs
User Avatar
No comments yet.