.png){kind=icon}
返回
EFFICIENT MANAGEMENT OF TIME-EVOLVING DATABASES
.png){kind=icon}
PRE
AI
DOI：10.1109/69.404032.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Efficiently managing the history of a time-evolving system is one of the central problems in many database environments, like database systems that incorporate versioning, or object-oriented databases that implicitly or explicitly maintain the history of persistent objects. In this paper we propose algorithms that reconstruct past states of an evolving system for two general cases, i.e., when the system's state is represented by a set or by a hierarchy (a forest of trees). Sets are widely used as a canonical form of representing information in databases or program states. For more complex applications, like schema evolution in object-oriented databases, it becomes necessary to manage the history of data structures that have the form of forests or even graphs. The proposed algorithms use minimal space (proportional to the number of changes occurring in the evolution) and have the advantage of being on-line (in the amortized sense), Any past system state s(t) is reconstructed in time O(Is(t)I + loglogT), where Is(t)I is the size of the answer and T is the maximal evolution time. For all practical cases the loglogT factor is a constant, therefore our algorithms provide almost random access to any past system state. Moreover, we show that the presented algorithms are optimal among all algorithms that use space linear in the number of changes in the system's evolution.
Keyword:
TEMPORAL DATABASES
HISTORICAL QUERIES
ACCESS METHODS
DATA-STRUCTURES
VERSIONING
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
10.4
论文数:
6.8K
被引数:
3.2W
机构
暂无机构信息
引用论文
N‐Methylaspartate‐Evoked Liberation of Taurine and Phosphoethanolamine In Vivo: Site of Release
PREAI
分享收藏
High-Mg carbonatitic microinclusions in some Yakutian diamonds—a new type of diamond-forming fluid.png)
Lithos
LithosIF0
PREAI
分享收藏
查看更多内容