Currency Preserving Query: Selecting the Newest Values from Multiple Tables

Mohan Li, Yanbin SunIEICE Trans. Information and Systems 2018 · DOI

Abstract

In modern distributed data environments, information is frequently scattered across multiple databases that update at different rates. This paper addresses the challenge of ensuring data "currency"—retrieving the most up-to-date values—when querying such overlapping sources. The authors propose the Currency Preserving Query (CPQ) framework, which utilizes a graph-based model to identify the "freshest" data points while respecting referential integrity. By formalizing the problem as finding a "Terminal Tree" within a Schema Currency Graph, the research provides efficient heuristics for automated query generation, ensuring users receive the most current and semantically consistent records available.

Introduction: The Challenge of Data Decay

In the era of big data, a single entity's information rarely resides in one location. For instance, an employee's address might be stored in an HR database, while their salary is in a payroll system and project assignments are in a management tool. Because these systems are updated at different frequencies, data "decays" at different rates across the ecosystem. One database might hold a newer address, while another contains the most recent salary update.

Distributed data sources with temporal orders (red dashed arrows) and join constraints (green lines).

Currently, obtaining a complete, up-to-date record requires manual intervention to identify which table holds the newest version of each attribute and how to join them correctly. This process is both error-prone and inefficient. The authors identify two primary hurdles:

  1. Temporal Ordering: Determining which source holds the "newest" value for a specific attribute.
  2. Referential Integrity: Ensuring that "fresh" values pulled from disparate tables (e.g., salary from Table A and address from Table B) actually belong to the same entity by leveraging foreign keys and join constraints.

Methodology: Freshness as a Graph Problem

The core innovation of this work is treating data currency as a pathfinding problem within a graph. The authors propose several key structures:

  • Schema Currency Graph (SCG): The entire data environment is represented as a graph where nodes are attributes. Edges represent three types of relationships: intra-table associations, temporal orders (indicating which source is newer), and dependency edges for valid joins.
  • Terminal Nodes (TN): These are the "leaf" nodes in the temporal chain—the attributes representing the most current information.
  • Terminal Tree (TerTree): The authors prove that a valid Currency Preserving Query is equivalent to a "Terminal Tree" in the SCG—a structure that connects all required newest attributes using valid join paths.
A Schema Currency Graph (SCG) modeling attributes, temporal orders (dashed), and join dependencies (double lines).

To generate executable SQL-like queries from these trees, the authors address the challenge of query minimization. Finding the smallest query (to minimize database access costs) is proven to be NP-hard, specifically a variation of the Steiner Tree problem. Consequently, two heuristics are proposed: one based on Minimum Spanning Trees (MST) and a faster alternative based on Shortest Paths.

Experimental Evaluation

The approach was evaluated using two primary datasets: the NBA Player Dataset, a real-world dataset spanning 1946–2013, and a Synthetic (SYN) Dataset used to test scalability across up to 1,000 schemas.

Key Results

  • Efficiency vs. Quality: The Shortest Path heuristic proved significantly faster, generating queries in roughly 10ms for a 1,000-schema graph, compared to nearly 1,000ms for the MST-based approach. However, the MST-based method often produced smaller queries with fewer joins, potentially leading to lower execution costs in production environments.
  • Scalability: The overhead for automated query generation is negligible; generating a CPQ from a 200-node Terminal Tree took approximately 5ms.

Conclusion and Future Directions

The CPQ framework demonstrates that data currency can be effectively managed by respecting both temporal updates and join constraints. By formalizing these relationships in a graph, the system ensures that "fresh" records are semantically correct rather than a collection of unrelated newest values. Future work aims to address the current limitation of static temporal rules by exploring conditional temporal orders, where the "freshness" of a source might depend on specific record attributes.

Reference: Li, M., & Sun, Y. (2018). Currency Preserving Query: Selecting the Newest Values from Multiple Tables. IEICE Transactions on Information and Systems, E101-D(12), 3059-3072.

Summary updated

BibTeX
@article{li2018currency,
  author = {Mohan Li and Yanbin Sun},
  title = {{Currency Preserving Query: Selecting the Newest Values from Multiple Tables}},
  journal = {IEICE Trans. Information and Systems},
  year = {2018},
  doi = {10.1587/transinf.2018edp7058},
}
Figure