...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Fuzzy sets and systems >Possibilistic keys
【24h】

Possibilistic keys

机译：可能键

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Possibility theory is applied to introduce and reason about the fundamental notion of a key for uncertain data. Uncertainty is modeled qualitatively by assigning to tuples of data a degree of possibility with which they occur in a relation, and assigning to keys a degree of certainty which says to which tuples the key applies. The associated implication problem is characterized axiomatically and algorithmically. Using extremal combinatorics, we then characterize the families of non-redundant possibilistic keys that attain maximum cardinality. In addition, we show how to compute for any given set of possibilistic keys a possibilistic Armstrong relation, that is, a possibilistic relation that satisfies every key in the given set and violates every possibilistic key not implied by the given set. We also establish an algorithm for the discovery of all possibilistic keys that are satisfied by a given possibilistic relation. It is shown that the computational complexity of computing possibilistic Armstrong relations is precisely exponential in the input, and the decision variant of the discovery problem is NP-complete as well as W[2]-complete in the size of the possibilistic key. Further applications of possibilistic keys in constraint maintenance, data cleaning, and query processing are illustrated by examples. The computation of possibilistic Armstrong relations and discovery of possibilistic keys from possibilistic relations have been implemented as prototypes. Extensive experiments with these prototypes provide insight into the size of possibilistic Armstrong relations and the time to compute them, as well as the time it takes to compute a cover of the possibilistic keys that hold on a possibilistic relation, and the time it takes to remove any redundant possibilistic keys from this cover. (C) 2019 Elsevier B.V. All rights reserved.
机译：应用可能性理论对不确定数据密钥的基本概念进行介绍和推理。通过向数据元组分配它们在关系中出现的可能性程度，并向键分配一个确定程度，该确定程度说明密钥适用于哪些元组，从而对质量进行定性建模。公理化和算法化地表征了相关的隐含问题。然后，使用极值组合运算法则来描述获得最大基数的非冗余可能性密钥族。另外，我们展示了如何为任意给定的可能键集计算可能的Armstrong关系，即满足给定集中的每个键并且违反给定集未隐含的每个可能键的可能关系。我们还建立了一种算法，用于发现给定可能性关系满足的所有可能密钥。结果表明，可能的阿姆斯特朗关系的计算复杂度在输入中正好是指数级的，发现问题的决策变量在可能性密钥的大小上为NP-complete和W [2] -complete。通过示例说明了可能键在约束维护，数据清理和查询处理中的其他应用。可能性阿姆斯特朗关系的计算和从可能性关系中发现可能性密钥已作为原型实现。使用这些原型进行的大量实验可洞悉可能的阿姆斯特朗关系的大小以及计算它们的时间，以及计算保持这种可能性关系的可能性键所需的时间，以及将其删除所需的时间。此封面中的所有冗余可能键。 （C）2019 Elsevier B.V.保留所有权利。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号