On the complexity of sampling query feedback restricted database repair of functional dependency violations

DOI10.1016/J.TCS.2015.02.010zbMATH1332.68042OpenAlexW2081489756MaRDI QIDQ896157FDOQ896157

Authors Dongjing Miao, Xianmin Liu, Jianzhong Li

Publication date 11 December 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.02.010

zbMATH Keywords

complexitydatabaserepair sampling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Database theory (68P15)

Recommendations

• Sampling query feedback restricted repairs of functional dependency violations: complexity and algorithm
• Complexity of repair checking and consistent query answering
• Counting subset repairs with functional dependencies
• On the data complexity of consistent query answering
• Advances in Databases and Information Systems

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1953144 (Why is no real title available?)
• scientific article; zbMATH DE number 839556 (Why is no real title available?)
• Calculating constraints on relational expression
• Determining View dependencies using tableaux
• First-order query rewriting for inconsistent databases
• Minimal-change integrity maintenance using tuple deletions
• On the correct translation of update operations on relational views
• Prioritized repairing and consistent query answering in relational databases
• Update semantics of relational views
• Updates of Relational Views

Cited in

(13)

• On the complexity of bounded deletion propagation
• New results on the complexity of deletion propagation
• On the complexity and approximability of repair position selection problem
• SEF view deletion under bounded condition
• Functional dependency restricted insertion propagation
• On the Complexity of Insertion Propagation with Functional Dependency Constraints
• Triangle edge deletion on planar glasses-free RGB-digraphs
• Parameterized complexity of completeness reasoning for conjunctive queries
• Counting subset repairs with functional dependencies
• On sampling representatives of relational schemas with a functional dependency
• Sampling query feedback restricted repairs of functional dependency violations: complexity and algorithm
• Sampling-based approximate skyline calculation on big data
• The parameterized complexity and kernelization of resilience for database queries

This page was built for publication: On the complexity of sampling query feedback restricted database repair of functional dependency violations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896157)