zbMATH — the first resource for mathematics

Logic of temporal attribute implications. (English) Zbl 1409.68283
Summary: We study logic for reasoning with if-then formulas describing dependencies between attributes of objects which are observed in consecutive points in time. We introduce 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.

68T27 Logic in artificial intelligence
68Q25 Analysis of algorithms and problem complexity
68T30 Knowledge representation
Full Text: DOI
[1] Agrawal, R., Imieliński, T., Swami, A.: Mining association rules between sets of items in large databases. In: Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data (New York, NY, USA), SIGMOD ’93, ACM, pp. 207-216 (1993)
[2] Ale, J.M., Rossi, G.H.: An approach to discovering temporal association rules. In: Proceedings of the 2000 ACM Symposium on Applied Computing (New York, NY, USA), SAC ’00, vol. 1, pp. 294-300. ACM (2000) · Zbl 1434.68144
[3] Armstrong, W.W.: Dependency structures of data base relationships. In: Rosenfeld, J. L., Freeman, H. (eds.) Information Processing 74: Proceedings of IFIP Congress (Amsterdam), pp.580-583, North Holland (1974) · Zbl 0296.68038
[4] Artale, A., Kontchakov, R., Ryzhikov, V., Zakharyaschev, M.: The complexity of clausal fragments of LTL. arXiv:1306.5088 (2013) · Zbl 1433.03046
[5] Baixeries, J; Kaytoue, M; Napoli, A, Characterizing functional dependencies in formal concept analysis with pattern structures, Ann. Math. Artif. Intell., 72, 129-149, (2014) · Zbl 1320.68064
[6] Beeri, C; Bernstein, PA, Computational problems related to the design of normal form relational schemas, ACM Trans. Database Syst., 4, 30-59, (1979)
[7] Bettini, C., Jajodia, S., Wang, X.S.: Time Granularities in Databases, Data Mining, and Temporal Reasoning. Springer (2000) · Zbl 0976.68049
[8] Biedermann, K.: A Foundation of the Theory of Trilattices. Dissertation, TU Darmstadt, Aachen (1998) · Zbl 0920.06001
[9] Birkhoff, G.: Lattice theory. American Mathematical Society (1940) · Zbl 0063.00402
[10] Blackburn, P., de Rijke, M., Venema, Y.: Modal logic. Cambridge University Press, Secaucus, NJ, USA (2002) · Zbl 0988.03006
[11] Chomicki, J., Imieliński, T.: Temporal deductive databases and infinite objects. In: Proceedings of the 7Th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (New York, NY, USA), PODS ’88, ACM, pp. 61-73 (1988)
[12] Chomicki, J., Imieliński, T.: Relational specifications of infinite query answers. In: Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data (New York, NY, USA), SIGMOD ’89, ACM, pp. 174-183 (1989)
[13] Chomicki, J; Imieliński, T, Finite representation of infinite query answers, ACM Trans. Database Syst., 18, 181-223, (1993)
[14] Codd, EF, A relational model of data for large shared data banks, Commun. ACM, 13, 377-387, (1970) · Zbl 0207.18003
[15] Combi, C; Sala, P, Interval-based temporal functional dependencies: specification and verification, Ann. Math. Artif. Intell., 71, 85-130, (2014) · Zbl 1311.68051
[16] Cordero, P; Mora, Á; Pérez de Guzmán, I; Enciso, M, Non-deterministic ideal operators: an adequate tool for formalization in data bases, Discret. Appl. Math., 156, 911-923, (2008) · Zbl 1142.68023
[17] Cresswell, S., Coddington, A.M.: Compilation of LTL goal formulas into PDDL. In: López de Mántaras, R., Saitta, L. (eds.) Proceedings of the 16Th Eureopean Conference on Artificial Intelligence, ECAI’2004, including Prestigious Applicants of Intelligent Systems, PAIS 2004, Valencia, Spain, August 22-27, 2004, pp. 985-986. IOS Press (2004) · Zbl 1277.68067
[18] Date, C.J., Darwen, H.: Relational Database Writings 1989-1991. Ch. The Role of Functional Dependence in Query Decomposition, pp. 133-154. Addison-Wesley Publishing Co. Inc. (1992)
[19] Date, C.J., Darwen, H., Lorentzos, N.A.: Time and Relational Theory: Temporal Databases in the Relational Model and SQL. Morgan Kaufmann (2014)
[20] Davey, B.A., Priestley, H.A.: Introduction to Lattices and Order. Cambridge University Press, Cambridge (1990) · Zbl 0701.06001
[21] De Cat, B; Bruynooghe, M, Detection and exploitation of functional dependencies for model generation, Theory Pract. Logic Program., 13, 471-485, (2013) · Zbl 1286.68042
[22] Dieng, CT; Jen, T-Y; Laurent, D; Spyratos, N, Mining frequent conjunctive queries using functional and inclusion dependencies, VLDB J., 22, 125-150, (2013)
[23] Fagin, R, Functional dependencies in a relational database and propositional logic, IBM J. Res. Dev., 21, 534-544, (1977) · Zbl 0366.68022
[24] Fan, W; Li, J; Tang, N; Yu, W, Incremental detection of inconsistencies in distributed data, IEEE Trans. Knowl. Data Eng., 26, 1367-1383, (2014)
[25] Feng, L; Dillon, T; Liu, J, Inter-transactional association rules for multi-dimensional contexts for prediction and their application to studying meterological data, Data Knowl. Eng., 37, 85-115, (2001) · Zbl 0974.68043
[26] Feng, L; Yu, JX; Lu, H; Han, J, A template model for multidimensional inter-transactional association rules, VLDB J., 11, 153-175, (2002)
[27] Ferrarotti, F; Hartmann, S; Link, S, Reasoning about functional and full hierarchical dependencies over partial relations, Inform. Sci., 235, 150-173, (2013) · Zbl 1284.68231
[28] Gaintzarain J., Lucio, P.: Logical foundations for more expressive declarative temporal logic programming languages. ACM Trans. Comput. Logic 14(4), 28:1-28:41 (2013) · Zbl 1353.68035
[29] Ganter, B.: Two basic algorithms in concept analysis. In: Proceedings of the 8Th International Conference on Formal Concept Analysis (Berlin, Heidelberg), ICFCA’10, pp. 312-340. Springer (2010) · Zbl 1274.68484
[30] Ganter B., Obiedkov, S.: Implications in triadic formal contexts. In: Wolff, K.E., Pfeiffer, H.D., Delugach, H.S. (eds.) Conceptual Structures at Work, Lecture Notes in Computer Science, vol. 3127, pp. 186-195. Springer, Berlin Heidelberg (2004) · Zbl 1104.68735
[31] Ganter, B., Wille, R.: Formal Concept Analysis: Mathematical Foundations, 1st edn. Springer, New York (1997) · Zbl 0861.06001
[32] Garey, M.R., Johnson, D.S.: Computers and Intractability: a Guide to the Theory of np-Completeness. W. H. Freeman & Co., New York (1979) · Zbl 0411.68039
[33] Ghallab, M., Howe, A., Knoblock, C., McDermott, D., Ram, A., Veloso, M., Weld, D., Wilkins, D.: Pddl—the planning domain definition language, version 1.2. technical report cvc tr-98-003/dcs tr-1165 (oct.). Tech. report, Yale Center for Computational Vision and Control, Yale University (1998) · Zbl 0366.68022
[34] Guigues, J-L; Duquenne, V, Familles minimales d’implications informatives resultant d’un tableau de données binaires, Math. Sci. Humaines, 95, 5-18, (1986)
[35] Hájek, P.: Metamathematics of Fuzzy Logic. Kluwer Academic Publishers, Dordrecht, The Netherlands (1998) · Zbl 0937.03030
[36] Huang, Y-P; Kao, L-J; Sandnes, F-E, Efficient mining of salinity and temperature association rules from argo data, Expert Syst. Appl., 35, 59-68, (2008)
[37] Ibaraki, T; Kogan, A; Makino, K, On functional dependencies in q-Horn theories, Artif. Intell., 131, 171-187, (2001) · Zbl 0996.68197
[38] Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Berlin, Heidelberg (2004) · Zbl 1103.90003
[39] Lee, AJT; Wang, C-S; Weng, W-Y; Chen, Y-A; Wu, H-W, An efficient algorithm for mining closed inter-transaction itemsets, Data Knowl. Eng., 66, 68-91, (2008)
[40] Lehmann, F., Wille, R.: A triadic approach to formal concept analysis. In: Ellis, G., Levinson, R., Rich, W., Sowa, J.F. (eds.) Conceptual Structures: Applications, Implementation and Theory, Lecture Notes in Computer Science, vol. 954, pp. 32-43. Springer, Berlin, Heidelberg (1995) · Zbl 1142.68023
[41] Li, J; Liu, J; Toivonen, H; Yong, J, Effective pruning for the discovery of conditional functional dependencies, Comput. J., 56, 378-392, (2013)
[42] Li, Y; Ning, P; Wang, XS; Jajodia, S, Discovering calendar-based temporal association rules, Data Knowl. Eng., 44, 193-218, (2003)
[43] Lindström, P, First order predicate logic with generalized quantifiers, Theoria, 32, 186-195, (1966) · Zbl 1230.03072
[44] Liu, J; Ye, F; Li, J; Wang, J, On discovery of functional dependencies from data, Data Knowl. Eng., 86, 146-159, (2013)
[45] Lloyd, J.W.: Foundations of Logic Programming. Springer New York, Inc., New York (1984) · Zbl 0547.68005
[46] Lu, H; Feng, L; Han, J, Beyond intratransaction association analysis: mining multidimensional intertransaction association rules, ACM Trans. Inf. Syst., 18, 423-454, (2000)
[47] Ma, S; Fan, W; Bravo, L, Extending inclusion dependencies with conditions, Theor. Comput. Sci., 515, 64-95, (2014) · Zbl 1277.68067
[48] Maier, D.: Theory of Relational Databases. Computer Science Pr, Rockville (1983) · Zbl 0519.68082
[49] McCarthy, J., Hayes, P.J.: Readings in Nonmonotonic Reasoning, pp. 26-45. Morgan Kaufmann Publishers Inc., San Francisco (1987)
[50] Mostowski, A, On a generalization of quantifiers, Fundam. Math., 44, 12-36, (1957) · Zbl 0078.24401
[51] Oliveira, JN, A relation-algebraic approach to the “hoare logic” of functional dependencies, Journal of Logical and Algebraic Methods in Programming, 83, 249-262, (2014) · Zbl 1434.68144
[52] Papadimitriou, C.H.: Computational Complexity. Addison-Wesley Publishing Co. Inc. (1994) · Zbl 0833.68049
[53] Pinto, J; Reiter, R, Reasoning about time in the situation calculus, Ann. Math. Artif. Intell., 14, 251-268, (1995) · Zbl 0855.68102
[54] Rainsford, C.P., Roddick, J.F.: Adding temporal semantics to association rules. In: żytkow, J.M., Rauch, J. (eds.) Principles of Data Mining and Knowledge Discovery, Lecture Notes in Computer Science, vol. 1704, pp. 504-509. Springer, Berlin, Heidelberg (1999)
[55] R. Reiter: Artificial intelligence and mathematical theory of computation, pp 359-380. Academic Press Professional, Inc., San Diego (1991)
[56] Reynolds, M, The complexity of decision problems for linear temporal logics, Journal of Studies in Logic, 3, 19-50, (2010)
[57] Robinson, JA, A machine-oriented logic based on the resolution principle, J. ACM, 12, 23-41, (1965) · Zbl 0139.12303
[58] Song, S; Chen, L; Cheng, H, Efficient determination of distance thresholds for differential dependencies, IEEE Trans. Knowl. Data Eng., 26, 2179-2192, (2014) · Zbl 1324.93011
[59] Szabo, G.I., Benczur, A.: Functional dependencies on symbol strings generated by extended context free languages. In: Morzy, T., Harder, T., Wrembel, R. (eds.) Advances in Databases and Information Systems, Advances in Intelligent Systems and Computing, vol. 186, pp. 253-264 (2013)
[60] Tarski, A, A lattice-theoretical fixpoint theorem and its applications, Pac. J. Math., 5, 285-309, (1955) · Zbl 0064.26004
[61] Triska, J., Vychodil, V.: Towards Armstrong-style inference system for attribute implications with temporal semantics. In: Torra, V., Narukawa, Y., Endo, Y. (eds.) Modeling Decisions for Artificial Intelligence - 11Th International Conference, MDAI 2014, Tokyo, Japan, October 29-31, 2014. Proceedings, Lecture Notes in Computer Science, vol. 8825, pp. 84-95. Springer (2014)
[62] Triska, J., Vychodil, V.: Minimal bases of temporal attribute implications. in preparation (2016) · Zbl 1409.68283
[63] Tung, A.K.H., Lu, H., Han, J., Feng, L.: Breaking the barrier of transactions: mining inter-transaction association rules. In: Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (New York, NY, USA), KDD ’99, ACM, pp. 297-301 (1999)
[64] Vincent, MW; Liu, J; Mohania, MK, The implication problem for ‘closest node’ functional dependencies in complete XML documents, J. Comput. Syst. Sci., 78, 1045-1098, (2012) · Zbl 1245.68076
[65] Wellman, M.P.: Exploiting functional dependencies in qualitative probabilistic reasoning. arXiv:1304.1081 (2013) · Zbl 0139.12303
[66] Zaki, MJ, Mining non-redundant association rules, Data Min. Knowl. Disc., 9, 223-248, (2004)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.