Data take the form of a triple that consists of a summary attribute, a category and a numeric value. The inference problem of summary data consists in deciding whether or not a summary data of interest is evaluable (i.e., can be computed) from a given set of summary data. We address the special case of the inference problem with homogeneous summary data (i.e., summary data with the same summary attribute), where the summary attribute is of additive nature. Owing to additivity, one can model the information content of the given summary data by a linear equation system whose variables are constrained to take their values from the domain of the summary attribute. We state two evaluability criteria, one for a real or integral summary attribute, and the other for a nonnegative-real or nonnegative-integral summary attribute. Using the two evaluability criteria, we show that our inference problem can be solved in strongly polynomial time for a real or integral or nonnegative real summary attribute, and is coNP-complete for a nonnegative-integral summary attribute. Moreover, we prove that, given a summary data of interest that is not evaluable, even in the (simplest) case that the summary attribute is of a real type, finding an evaluable summary data whose category is maximally contained in (or minimally contains) the category of the summary data of interest is an NP-hard problem. (c) 2007 Elsevier B.V. All rights reserved.

An analytical approach to the inference of summary data of additive type / Malvestuto, Francesco Mario; Mezzini, Mauro; Moscarini, Marina. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 385:1-3(2007), pp. 264-285. [10.1016/j.tcs.2007.07.004]

An analytical approach to the inference of summary data of additive type

MALVESTUTO, Francesco Mario;MEZZINI, Mauro;MOSCARINI, Marina
2007

Abstract

Data take the form of a triple that consists of a summary attribute, a category and a numeric value. The inference problem of summary data consists in deciding whether or not a summary data of interest is evaluable (i.e., can be computed) from a given set of summary data. We address the special case of the inference problem with homogeneous summary data (i.e., summary data with the same summary attribute), where the summary attribute is of additive nature. Owing to additivity, one can model the information content of the given summary data by a linear equation system whose variables are constrained to take their values from the domain of the summary attribute. We state two evaluability criteria, one for a real or integral summary attribute, and the other for a nonnegative-real or nonnegative-integral summary attribute. Using the two evaluability criteria, we show that our inference problem can be solved in strongly polynomial time for a real or integral or nonnegative real summary attribute, and is coNP-complete for a nonnegative-integral summary attribute. Moreover, we prove that, given a summary data of interest that is not evaluable, even in the (simplest) case that the summary attribute is of a real type, finding an evaluable summary data whose category is maximally contained in (or minimally contains) the category of the summary data of interest is an NP-hard problem. (c) 2007 Elsevier B.V. All rights reserved.
2007
category hierarchy; evaluability; summary database
01 Pubblicazione su rivista::01a Articolo in rivista
An analytical approach to the inference of summary data of additive type / Malvestuto, Francesco Mario; Mezzini, Mauro; Moscarini, Marina. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 385:1-3(2007), pp. 264-285. [10.1016/j.tcs.2007.07.004]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/358079
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 3
social impact