Lineage, which records the origin of the data and the process by which the data are derived, is critical for many applications. This dissertation addresses several shortcomings of databases for supporting fine-grained lineage. First, frequent updates complicate lineage tracing. Since the data derivation may be expensive, changes in base data are not always propagated to the derived data immediately. This leads to an inconsistent state in the data and to stale lineage. We propose tracing lineage with multiple versions of data. Maintaining multiple versions of the data and their fine-grained lineage ensures that the lineage is always correct. Moreover, current methods trace lineage backward at users' requests and the lineage then, is not stored. To enable ad hoc queries over lineage, we advocate tracing lineage for all data and storing lineage in databases. Unfortunately, the current backward tracing approach is not efficient for tracing lineage for all data. To address this problem, we formally define forward lineage and prove its properties. We propose new query rewriting algorithms for Selection-Projection-Join (SPJ) and Aggregation-Selection-Projection (ASPJ) queries. In addition, our technique handles bag semantics, aggregations and nested sub-queries efficiently. Further, most current techniques focus on tracing internal fine-grained lineage where data is produced by a set of well-defined relational operators. As data is often processed outside databases, tracing lineage of the data produced by a black box function is inherently difficult. We propose a novel approach that instruments the binary code to enable external lineage tracing. This method is superior to prior work in that it is automatic and does not require any domain knowledge. We have implemented our techniques based on PostgreSQL and established the validity of the methods by testing with real data: We support new queries through materialized lineage; the forward method for tracing internal lineage incurs a low overhead for tracing all data lineage; the external lineage tracing technique has been used in a real scientific application and was found to be highly beneficial to our collaborators. Our techniques have broadened the scope of lineage, improved the quality of lineage, and enhanced the efficiency of tracing lineage.