Number of the records: 1
Temporal attribute implications
Title statement Temporal attribute implications [rukopis] / Jan Tříska Additional Variant Titles Temporální závislosti v datech Personal name Tříska, Jan (dissertant) Translated title Temporal data dependencies Issue data 2018 Phys.des. vi s. + 90 s. Note Ved. práce Vilém Vychodil Another responsib. Vychodil, Vilém (thesis advisor) Another responsib. Univerzita Palackého. Katedra informatiky (degree grantor) Keywords attribute implication * axiomatization * minimality * non-redundancy * temporal data * temporal semantics * attribute implication * axiomatization * minimality * non-redundancy * temporal data * temporal semantics Form, Genre disertace dissertations UDC (043.3) Country Česko Language angličtina Document kind PUBLIKAČNÍ ČINNOST Title Ph.D. Degree program Doktorský Degree program Informatika Degreee discipline Informatika book
Kvalifikační práce Downloaded Size datum zpřístupnění 00215614-734416325.zip 57 903.5 KB 07.06.2018 Posudek Typ posudku 00215614-ved-574018387.pdf Posudek vedoucího 00215614-opon-184626242.pdf Posudek oponenta Průběh obhajoby datum zadání datum odevzdání datum obhajoby přidělená hodnocení typ hodnocení 00215614-prubeh-556059268.pdf 10.04.2014 07.06.2018 18.09.2018 S 2
We deal with dependencies in object-attribute data which is recorded at separate points in time. The data is formalized by finitely many tables encoding the relationship between the objects and the attributes and each table can be seen as a single formal context observed at a separate point in time. Given such data, we are interested in concise ways of characterizing all if-then dependencies between the attributes that hold in the data and are preserved in all time points. In order to formalize the dependencies, we introduce if-then formulas called temporal attribute implications which can be seen as particular formulas of linear temporal logic. We introduce a semantic entailment of the formulas, show its fixed-point characterization, investigate closure properties of model classes, present an axiomatization and prove its completeness, and investigate alternative axiomatizations and normalized proofs. We investigate decidability and complexity issues of the logic and prove that the entailment problem is NP-hard and belongs to EXPSPACE. We show that by restricting to predictive formulas, the entailment problem is decidable in pseudo-linear time. We introduce non-redundant bases of dependencies from data as non-redundant sets entailing exactly all the dependencies that hold in the data. In addition, we investigate minimality of bases as a stronger form of non-redundancy. For given data, we present a description of minimal bases using the notion of pseudo-intents generalized in the temporal setting. We further investigate properties of minimal sets of formulas and present sufficient and necessary conditions for their characterization.In addition to the characterization of minimality, we present an algorithm that can be used to minimize any finite set of temporal attribute implications.We deal with dependencies in object-attribute data which is recorded at separate points in time. The data is formalized by finitely many tables encoding the relationship between the objects and the attributes and each table can be seen as a single formal context observed at a separate point in time. Given such data, we are interested in concise ways of characterizing all if-then dependencies between the attributes that hold in the data and are preserved in all time points. In order to formalize the dependencies, we introduce if-then formulas called temporal attribute implications which can be seen as particular formulas of linear temporal logic. We introduce a semantic entailment of the formulas, show its fixed-point characterization, investigate closure properties of model classes, present an axiomatization and prove its completeness, and investigate alternative axiomatizations and normalized proofs. We investigate decidability and complexity issues of the logic and prove that the entailment problem is NP-hard and belongs to EXPSPACE. We show that by restricting to predictive formulas, the entailment problem is decidable in pseudo-linear time. We introduce non-redundant bases of dependencies from data as non-redundant sets entailing exactly all the dependencies that hold in the data. In addition, we investigate minimality of bases as a stronger form of non-redundancy. For given data, we present a description of minimal bases using the notion of pseudo-intents generalized in the temporal setting. We further investigate properties of minimal sets of formulas and present sufficient and necessary conditions for their characterization.In addition to the characterization of minimality, we present an algorithm that can be used to minimize any finite set of temporal attribute implications.
Number of the records: 1