Unique key Horn functions
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10452154" target="_blank" >RIV/00216208:11320/22:10452154 - isvavai.cz</a>
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=mxQ8axtXsx" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=mxQ8axtXsx</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.tcs.2022.04.022" target="_blank" >10.1016/j.tcs.2022.04.022</a>
Alternative languages
Result language
angličtina
Original language name
Unique key Horn functions
Original language description
Given a relational database, a key is a set of attributes such that a value assignment to this set uniquely determines the values of all other attributes. The database uniquely defines a pure Horn function h, representing the functional dependencies. If the knowledge of the attribute values in set A determines the value for attribute v, then A -> v is an implicate of h. If K is a key of the database, then K -> v is an implicate of h for all attributes v. Keys of small sizes play a crucial role in various problems. We present structural and complexity results on the set of minimal keys of pure Horn functions. We characterize Sperner hypergraphs for which there is a unique pure Horn function with the given hypergraph as the set of minimal keys. Furthermore, we show that recognizing such hypergraphs is co-NP-complete already when every hyperedge has size two. On the positive side, we identify several classes of graphs for which the recognition problem can be decided in polynomial time. We also present an algorithm that generates the minimal keys of a pure Horn function with polynomial delay, improving on earlier results. By establishing a connection between keys and target sets, our approach can be used to generate all minimal target sets with polynomial delay when the thresholds are bounded by a constant. As a byproduct, our proof shows that the MINIMUM KEY problem is at least as hard as the MINIMUM TARGET SET SELECTION problem with bounded thresholds. (C) 2022 The Author(s). Published by Elsevier B.V.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA19-19463S" target="_blank" >GA19-19463S: Boolean Representation Languages Complete for Unit Propagation</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2022
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Theoretical Computer Science
ISSN
0304-3975
e-ISSN
1879-2294
Volume of the periodical
922
Issue of the periodical within the volume
June
Country of publishing house
NL - THE KINGDOM OF THE NETHERLANDS
Number of pages
9
Pages from-to
170-178
UT code for WoS article
000850360300014
EID of the result in the Scopus database
2-s2.0-85129694970