Uncertain Rule Based Method for Determining Data Currency

Mohan Li, Jianzhong Li, Siyao Cheng, Yanbin Sun

Abstract

This paper presents a novel framework for identifying outdated information in databases by integrating temporal rules with uncertainty scores. Traditional rule-based methods often fail when timestamps are missing or when rules are not universally applicable. By employing uncertain currency rules and a polynomial-time inference algorithm based on currency graphs, the proposed method significantly enhances the accuracy and coverage of data currency detection. Evaluation on real-world datasets demonstrates substantial improvements over certain-rule-only approaches, particularly in datasets with weak regularity.

Introduction

In data management, "currency" refers to whether a data item is up-to-date. Outdated data is a significant issue for system performance and safety; statistics suggest that approximately 2% of customer records become obsolete every month, and poor medical data has been linked to thousands of annual fatalities. Existing solutions typically rely on timestamps or rigid logical rules (e.g., "an employee's salary does not decrease"). However, timestamps are often missing or imprecise, and traditional "certain" rules cannot identify cases where all available records for an entity are obsolete. For instance, if a database contains two outdated salary records, a certain rule might identify which is newer but fail to recognize that both are currently incorrect.

Methodology

The authors propose Uncertain Currency Rules, which attach a certainty score ($\xi$) to logical predicates. This allows the system to handle "soft" knowledge, such as "90% of the time, a person's rank increases with their tenure."

Examples of uncertain currency rules with associated certainty scores.

The framework operates through three main technical components:

  • Uncertain Rule Syntax: Rules incorporate timestamps and certainty degrees to model imprecise temporal knowledge.
  • Domination Graphs (DG): These graphs determine the optimal order for evaluating attributes (e.g., determining 'City' currency before 'Zip Code') to prevent infinite reasoning loops.
  • Currency Graphs (GA): This core data structure represents data items or time points as nodes and temporal orders as edges. Edge weights represent the certainty of the generating rule.
  • Longest Path Inference: A modified Dijkstra’s algorithm finds the "longest path" in terms of certainty to determine the most likely valid time for a record.

Experimental Evaluation

The method was evaluated on two real-life datasets: the NBA Dataset (~19,000 tuples), which is highly regular, and the Camera Dataset (~1,000 tuples), which exhibits "weak regularity" with harder-to-define rules.

Performance was measured using Absolute Error (AbsE) and F-measure. On the NBA dataset, the combination of certain and uncertain rules achieved an F-measure of 0.94. On the more challenging Camera dataset, the F-measure reached 0.85, a significant jump from the 0.18 achieved using only certain rules. This "uncertainty boost" proves that imperfect knowledge is significantly better than no knowledge.

Absolute error across varying certainty thresholds for NBA and Camera datasets.

The algorithm also proved computationally efficient, processing 9,000 data items across 9 attributes in just 12.8 seconds, making it viable for large-scale production databases.

Discussion and Future Work

A primary finding is the Coverage-Certainty Trade-off. In the Camera dataset, certain rules (100% confidence) covered only 5% of tuples. Incorporating uncertain rules allowed for nearly full coverage with high accuracy. Furthermore, the authors demonstrated that adding timestamps to a small subset of rules can propagate through the database to identify thousands of obsolete records. In cases of conflicting rules, the system defaults to the conclusion with the highest certainty, mimicking human reasoning.

While effective at detection, the current framework does not address data repair (fixing the outdated values). Future work includes developing automated repair methods, adapting the algorithm for real-time dynamic databases, and improving automated rule learning to reduce reliance on manual domain expertise.

Summary updated

Abstract

Currency is one of the important measurements of data quality. The main purpose of the study on data currency is to determine whether a given data item is up-to-date. Though there are already several works on determining data currency, all the proposed methods have limitations. Some works require timestamps of data items that are not always available, and others are based on certain currency rules that can only decide relevant currency and cannot express uncertain semantics. To overcome the limitations of the previous methods, this paper introduces a new approach for determining data currency based on uncertain currency rules. First, a class of uncertain currency rules is provided to infer the possible valid time for a given data item, and then based on the rules, data currency is formally defined. After that, a polynomial time algorithm for evaluating data currency is given based on the uncertain currency rules. Using real-life data sets, the effectiveness and efficiency of the proposed method are experimentally verified.
BibTeX
@article{li2018uncertain,
  author = {Mohan Li and Jianzhong Li and Siyao Cheng and Yanbin Sun},
  title = {{Uncertain Rule Based Method for Determining Data Currency}},
  journal = {IEICE Trans. Information and Systems},
  year = {2018},
  doi = {10.1587/transinf.2017edp7378},
}
Figure