{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T21:56:31Z","timestamp":1766181391600},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,5,1]],"date-time":"2020-05-01T00:00:00Z","timestamp":1588291200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,5,8]],"date-time":"2020-05-08T00:00:00Z","timestamp":1588896000000},"content-version":"vor","delay-in-days":7,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["SN COMPUT. SCI."],"published-print":{"date-parts":[[2020,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Functional dependencies (s) allow us to represent database constraints, corresponding to requirements as \u201c<jats:italic>patients having the same symptoms undergo the same medical tests<\/jats:italic>.\u201d Some research efforts have focused on extending such dependencies to consider also temporal constraints such as \u201c<jats:italic>patients having the same symptoms undergo in the next period the same medical tests<\/jats:italic>.\u201d Temporal functional dependencies are able to represent such kind of temporal constraints in relational databases. Another extension for s allows one to represent approximate functional dependencies (s), as \u201c<jats:italic>patients with the same symptoms<\/jats:italic><jats:italic>generally<\/jats:italic><jats:italic>undergo the same medical tests<\/jats:italic>.\u201d It enables data to deviate from the defined constraints according to a user-defined percentage. Approximate temporal functional dependencies (s) merge the concepts of temporal functional dependency and of approximate functional dependency. Among the different kinds of , the <jats:italic>Approximate Pure Temporally Evolving Functional Dependencies<\/jats:italic> (<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textit{APE}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>APE<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-FDs for short) allow one to detect patterns on the evolution of data in the database and to discover dependencies as \u201c<jats:italic>For most patients with the same initial diagnosis, the same medical test is prescribed after the occurrence of same symptom<\/jats:italic>.\u201d Mining s from large databases may be computationally expensive. In this paper, we focus on <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textit{APE}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>APE<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-FDs and prove that, unfortunately, verifying a single <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textit{APE}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>APE<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-FD over a given database instance is in general NP-complete. In order to cope with this problem, we propose a framework for mining complex <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textit{APE}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>APE<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-FDs in real-world data collections. In the framework, we designed and applied sound and advanced model-checking techniques. To prove the feasibility of our proposal, we used real-world databases from two medical domains (namely, psychiatry and pharmacovigilance) and tested the running prototype we developed on such databases.<\/jats:p>","DOI":"10.1007\/s42979-020-00160-9","type":"journal-article","created":{"date-parts":[[2020,5,8]],"date-time":"2020-05-08T12:02:45Z","timestamp":1588939365000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Discovering Evolving Temporal Information: Theory and Application to Clinical Databases"],"prefix":"10.1007","volume":"1","author":[{"given":"Pietro","family":"Sala","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carlo","family":"Combi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matteo","family":"Mantovani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Romeo","family":"Rizzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,5,8]]},"reference":[{"issue":"8","key":"160_CR1","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1109\/TC.1986.1676819","volume":"35","author":"RE Bryant","year":"1986","unstructured":"Bryant RE. Graph-based algorithms for Boolean function manipulation. IEEE Trans Comput. 1986;35(8):677\u201391. https:\/\/doi.org\/10.1109\/TC.1986.1676819.","journal-title":"IEEE Trans Comput."},{"key":"160_CR2","doi-asserted-by":"crossref","unstructured":"Codd EF. Normalized data base structure: a brief tutorial. In: Proceedings of the 1971 ACM SIGFIDET (now SIGMOD) workshop on data description, access and control. ACM; 1971, pp. 1\u201317.","DOI":"10.1145\/1734714.1734716"},{"key":"160_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-6543-1","volume-title":"Temporal information systems in medicine","author":"C Combi","year":"2010","unstructured":"Combi C, Keravnou-Papailiou E, Shahar Y. Temporal information systems in medicine. Berlin: Springer; 2010."},{"key":"160_CR4","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1016\/j.compbiomed.2014.08.004","volume":"62","author":"C Combi","year":"2014","unstructured":"Combi C, Mantovani M, Sabaini A, Sala P, Amaddeo F, Moretti U, Pozzi G. Mining approximate temporal functional dependencies with pure temporal grouping in clinical databases. Comput Biol Med. 2014;62:306\u201324.","journal-title":"Comput Biol Med."},{"key":"160_CR5","doi-asserted-by":"publisher","unstructured":"Combi C, Mantovani M, Sala P. Discovering quantitative temporal functional dependencies on clinical data. In: 2017 IEEE international conference on healthcare informatics, ICHI 2017, Park City, UT, USA, Aug 23\u201326, 2017. IEEE Computer Society; 2017. pp. 248\u2013257. https:\/\/doi.org\/10.1109\/ICHI.2017.80.","DOI":"10.1109\/ICHI.2017.80"},{"key":"160_CR6","doi-asserted-by":"crossref","unstructured":"Combi C, Montanari A, Pozzi G. The T4SQL temporal query language. In: Silva MJ, Laender AHF, Baeza-Yates RA, McGuinness DL, Olstad B, Olsen \u00d8H, Falc\u00e3o AO, editors. CIKM. ACM; 2007. pp. 193\u2013202.","DOI":"10.1145\/1321440.1321470"},{"key":"160_CR7","doi-asserted-by":"crossref","unstructured":"Combi C, Montanari A, Sala P. A uniform framework for temporal functional dependencies with multiple granularities. In: Advances in spatial and temporal databases. Springer; 2011. pp. 404\u2013421.","DOI":"10.1007\/978-3-642-22922-0_24"},{"key":"160_CR8","doi-asserted-by":"crossref","unstructured":"Combi C, Oliboni B, Pozzi G. Modeling and querying temporal semistructured data. In: New trends in data warehousing and data analysis. Springer; 2009. pp. 1\u201325.","DOI":"10.1007\/978-0-387-87431-9_14"},{"issue":"2","key":"160_CR9","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/j.jbi.2011.11.005","volume":"45","author":"C Combi","year":"2012","unstructured":"Combi C, Pozzi G, Rossato R. Querying temporal clinical databases on granular trends. J Biomed Inform. 2012;45(2):273\u201391.","journal-title":"J Biomed Inform."},{"key":"160_CR10","doi-asserted-by":"publisher","unstructured":"Combi C, Rizzi R, Sala P. The price of evolution in temporal databases. In: Grandi F, Lange M, Lomuscio A, editors, 22nd international symposium on temporal representation and reasoning, TIME 2015, Kassel, Germany, Sept 23\u201325, 2015. IEEE Computer Society; 2015. pp. 47\u201358. https:\/\/doi.org\/10.1109\/TIME.2015.24.","DOI":"10.1109\/TIME.2015.24"},{"issue":"6\u20138","key":"160_CR11","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1007\/s00236-015-0246-x","volume":"53","author":"C Combi","year":"2016","unstructured":"Combi C, Sala P. Mining approximate interval-based temporal dependencies. Acta Inf. 2016;53(6\u20138):547\u201385. https:\/\/doi.org\/10.1007\/s00236-015-0246-x.","journal-title":"Acta Inf."},{"key":"160_CR12","unstructured":"Dvorsk\u00fd M. Common permutation problem. CoRR; 2008. arXiv:abs\/0803.4261."},{"key":"160_CR13","unstructured":"Huhtala Y, Karkkainen J, Porkka P, Toivonen H. Efficient discovery of functional and approximate dependencies using partitions. In: Proceedings of the 14th international conference on data engineering, 1998. IEEE; 1998. pp. 392\u2013401."},{"issue":"2","key":"160_CR14","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1093\/comjnl\/42.2.100","volume":"42","author":"Y Huhtala","year":"1999","unstructured":"Huhtala Y, K\u00e4rkk\u00e4inen J, Porkka P, Toivonen H. TANE: an efficient algorithm for discovering functional and approximate dependencies. Comput J. 1999;42(2):100\u201311.","journal-title":"Comput J."},{"issue":"4","key":"160_CR15","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1109\/69.536250","volume":"8","author":"CS Jensen","year":"1996","unstructured":"Jensen CS, Snodgrass RT, Soo MD. Extending existing dependency theory to temporal databases. IEEE Trans Knowl Data Eng. 1996;8(4):563\u201382.","journal-title":"IEEE Trans Knowl Data Eng."},{"issue":"1","key":"160_CR16","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0304-3975(95)00028-U","volume":"149","author":"J Kivinen","year":"1995","unstructured":"Kivinen J, Mannila H. Approximate inference of functional dependencies from relations. Theor Comput Sci. 1995;149(1):129\u201349.","journal-title":"Theor Comput Sci."},{"key":"160_CR17","unstructured":"Lind-Nielsen J. BuDDy\u2014a binary decision diagram package. http:\/\/vlsicad.eecs.umich.edu\/BK\/Slots\/cache\/www.itu.dk\/research\/buddy\/.\u00a0Accessed 3 Mar 2020."},{"key":"160_CR18","doi-asserted-by":"crossref","unstructured":"Liu C, Zhang K, Xiong H, Jiang G, Yang Q. Temporal skeletonization on sequential data: patterns, categorization, and visualization. In: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM; 2014. pp. 1336\u20131345.","DOI":"10.1145\/2623330.2623741"},{"issue":"2\u20133","key":"160_CR19","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1080\/09528130210164143","volume":"14","author":"S Lopes","year":"2002","unstructured":"Lopes S, Petit JM, Lakhal L. Functional and approximate dependency mining: database and fca points of view. J. Exp. Theor. Artif. Intell. 2002;14(2\u20133):93\u2013114.","journal-title":"J. Exp. Theor. Artif. Intell."},{"key":"160_CR20","unstructured":"MedDRA. Medical Dictionary for Regulatory Activities. https:\/\/www.meddra.org\/. Accessed 23 Apr 2020."},{"issue":"6","key":"160_CR21","doi-asserted-by":"publisher","first-page":"459","DOI":"10.2165\/00002018-200225060-00011","volume":"25","author":"R Meyboom","year":"2002","unstructured":"Meyboom R, Lindquist M, Egberts A, Edwards I. Signal selection and follow-up in pharmacovigilance. Drug Saf. 2002;25(6):459\u201365.","journal-title":"Drug Saf."},{"key":"160_CR22","unstructured":"Object Management Group: Business Process Model and Notation (BPMN), v2.0.2. http:\/\/www.omg.org\/spec\/BPMN\/2.0.2\/PDF\/. Accessed 3 Mar 2020."},{"key":"160_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-13-7181-3","volume-title":"Descriptive data mining. Computational risk management","author":"DL Olson","year":"2019","unstructured":"Olson DL, Lauhoff G. Descriptive data mining. Computational risk management. 2nd ed. Berlin: Springer; 2019. https:\/\/doi.org\/10.1007\/978-981-13-7181-3.","edition":"2"},{"issue":"8","key":"160_CR24","doi-asserted-by":"publisher","first-page":"1143","DOI":"10.1016\/j.cor.2010.10.025","volume":"38","author":"J Pryor","year":"2011","unstructured":"Pryor J, Chinneck JW. Faster integer-feasibility in mixed-integer linear programs by branching to force change. Comput Oper Res. 2011;38(8):1143\u201352. https:\/\/doi.org\/10.1016\/j.cor.2010.10.025.","journal-title":"Comput Oper Res."},{"issue":"2","key":"160_CR25","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/s10618-007-0077-7","volume":"15","author":"L Sacchi","year":"2007","unstructured":"Sacchi L, Larizza C, Combi C, Bellazzi R. Data mining with temporal abstractions: learning rules from time series. Data Min Knowl Discov. 2007;15(2):217\u201347. https:\/\/doi.org\/10.1007\/s10618-007-0077-7.","journal-title":"Data Min Knowl Discov."},{"key":"160_CR26","doi-asserted-by":"crossref","unstructured":"Sala P. Approximate interval-based temporal dependencies: the complexity landscape. In: 2014 21st international symposium on temporal representation and reasoning (TIME). IEEE; 2014. pp. 69\u201378.","DOI":"10.1109\/TIME.2014.20"},{"key":"160_CR27","doi-asserted-by":"publisher","unstructured":"Sala P, Combi C, Cuccato M, Galvani A, Sabaini A. A framework for mining evolution rules and its application to the clinical domain. In: Balakrishnan P, Srivatsava J, Fu W, Harabagiu SM, Wang F, editors. 2015 International conference on healthcare informatics, ICHI 2015, Dallas, TX, USA, Oct 21\u201323, 2015. IEEE Computer Society; 2015. pp. 293\u2013302. https:\/\/doi.org\/10.1109\/ICHI.2015.42.","DOI":"10.1109\/ICHI.2015.42"},{"key":"160_CR28","doi-asserted-by":"crossref","unstructured":"Sordo M, Ochoa G, Murphy SN. A PSO\/ACO approach to knowledge discovery in a pharmacovigilance context. In: GECCO (Companion); 2009. pp. 2679\u20132684.","DOI":"10.1145\/1570256.1570382"},{"key":"160_CR29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54655-6","volume-title":"Data warehouse systems\u2014design and implementation. Data-centric systems and applications","author":"AA Vaisman","year":"2014","unstructured":"Vaisman AA, Zim\u00e1nyi E. Data warehouse systems\u2014design and implementation. Data-centric systems and applications. Berlin: Springer; 2014. https:\/\/doi.org\/10.1007\/978-3-642-54655-6."},{"issue":"1","key":"160_CR30","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1145\/7531.7918","volume":"34","author":"V Vianu","year":"1987","unstructured":"Vianu V. Dynamic functional dependencies and database aging. J ACM (JACM). 1987;34(1):28\u201359.","journal-title":"J ACM (JACM)"},{"issue":"2","key":"160_CR31","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1145\/249978.249979","volume":"22","author":"XS Wang","year":"1997","unstructured":"Wang XS, Bettini C, Brodsky A, Jajodia S. Logical design for temporal databases with multiple granularities. ACM Trans. Database Syst. (TODS). 1997;22(2):115\u201370.","journal-title":"ACM Trans. Database Syst. (TODS)"},{"issue":"1","key":"160_CR32","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1145\/310701.310715","volume":"24","author":"J Wijsen","year":"1999","unstructured":"Wijsen J. Temporal FDs on complex objects. ACM Trans Database Syst. 1999;24(1):127\u201376.","journal-title":"ACM Trans Database Syst."},{"key":"160_CR33","doi-asserted-by":"publisher","first-page":"2960","DOI":"10.1007\/978-0-387-39940-9_396","volume-title":"Encyclopedia of database systems","author":"J Wijsen","year":"2009","unstructured":"Wijsen J. Temporal dependencies. In: Liu L, \u00d6zsu MT, editors. Encyclopedia of database systems. Berlin: Springer; 2009. p. 2960\u20136. https:\/\/doi.org\/10.1007\/978-0-387-39940-9_396."},{"key":"160_CR34","unstructured":"World Health Organization and WHO Collaborating Centre for International Drug Monitoring: The Importance of Pharmacovigilance. Safety monitoring of medicinal products. World Health Organization; 2002."}],"container-title":["SN Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-020-00160-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42979-020-00160-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-020-00160-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,7]],"date-time":"2021-05-07T23:36:27Z","timestamp":1620430587000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42979-020-00160-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["160"],"URL":"https:\/\/doi.org\/10.1007\/s42979-020-00160-9","relation":{},"ISSN":["2662-995X","2661-8907"],"issn-type":[{"value":"2662-995X","type":"print"},{"value":"2661-8907","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5]]},"assertion":[{"value":"10 March 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 April 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 May 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with Ethical Standards"}},{"value":"On behalf of all authors, the corresponding author states that there are no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"This article does not contain any studies with human participants or animals performed by any of the authors.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical Approval"}}],"article-number":"153"}}