Attività di ricerca di Moscarini, Marina

Using graphs and hypergraphs as formal tools, she approached various problems in database theory related to designing acyclic schemes, query answering in logical independence interfaces and protecting data in statistical databases. Acyclic database schemes enjoy several desirable properties concerning consistency checking, dependency equivalence and query optimisation; therefore it is important to develop polynomial algorithms to recognise and to design them. Logical independence interfaces allow the user to ask for a set of attributes without specifying how to compute the answer; if more than one answer is admissible then the query is ambiguous and the system needs to remove the ambiguity; if only one answer is admissible but there are different ways of computing it then the system must be able to choose the more efficient one. Statistical databases are composed of tables of containing statistics about classes of individuals; they are used mainly when individual data cannot be made public. Therefore, data security is a central topic in the study of statistical databases; if the data enjoy the additivity property, security problems can arise from the possibility of computing, starting from data in the tables and from marginals, data that are in no table.

Problems concerning query answering in logical independence interfaces, can be solved by finding minimal connections in chordal graphs or in acyclic hypergraphs. This led to study two classical optimization problems (the Steiner tree problem and the connected domination problem) that are NP-hard in the general case and to characterise particular classes of graphs in which they can be solved in polynomial time.