Arrow Research search

Author name cluster

Nina Pardal

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers
2 author rows

Possible papers

6

KR Conference 2025 Conference Paper

A Logic-Based Framework for Database Repairs

  • Nicolas Fröhlich
  • Arne Meier
  • Nina Pardal
  • Jonni Virtema

We introduce a general abstract framework for database repairs, where the repair notions are defined using formal logic. We distinguish between integrity constraints and so-called query constraints. The former are used to model consistency and desirable properties of the data (such as functional dependencies and independencies), while the latter relate two database instances according to their answers to the query constraints. The framework allows for a distinction between hard and soft queries, allowing the answers to a core set of queries to be preserved, as well as defining a distance between instances based on query answers. We illustrate how different repair notions from the literature can be modelled in our framework. The framework generalises both set-based and cardinality based repairs to semiring annotated databases. Finally, we initiate a complexity-theoretic analysis of consistent query answering and checking existence of a repair in our setting.

PDF Details DOI

IJCAI Conference 2024 Conference Paper

On the Complexity of Finding Set Repairs for Data-Graphs (Abstract Reprint)

  • Sergio Abriola
  • Maria Vanina Martinez
  • Nina Pardal
  • Santiago Cifuentes
  • Edwin Pin Baque

In the deeply interconnected world we live in, pieces of information link domains all around us. As graph databases embrace effectively relationships among data and allow processing and querying these connections efficiently, they are rapidly becoming a popular platform for storage that supports a wide range of domains and applications. As in the relational case, it is expected that data preserves a set of integrity constraints that define the semantic structure of the world it represents. When a database does not satisfy its integrity constraints, a possible approach is to search for a ‘similar’ database that does satisfy the constraints, also known as a repair. In this work, we study the problem of computing subset and superset repairs for graph databases with data values using a notion of consistency based on having a set of Reg-GXPath expressions as integrity constraints. We show that for positive fragments of Reg-GXPath these problems admit a polynomialtime algorithm, while the full expressive power of the language renders them intractable.

PDF Details DOI

ECAI Conference 2024 Conference Paper

The Distributional Uncertainty of the SHAP Score in Explainable Machine Learning

  • Santiago Cifuentes
  • Leopoldo E. Bertossi
  • Nina Pardal
  • Sergio Abriola
  • Maria Vanina Martinez
  • Miguel Romero 0001

Attribution scores reflect how important the feature values in an input entity are for the output of a machine learning model. One of the most popular attribution scores is the SHAP score, which is an instantiation of the general Shapley value used in coalition game theory. The definition of this score relies on a probability distribution on the entity population. Since the exact distribution is generally unknown, it needs to be assigned subjectively or be estimated from data, which may lead to misleading feature scores. In this paper, we propose a principled framework for reasoning on SHAP scores under unknown entity population distributions. In our framework, we consider an uncertainty region that contains the potential distributions, and the SHAP score of a feature becomes a function defined over this region. We study the basic problems of finding maxima and minima of this function, which allows us to determine tight ranges for the SHAP scores of all features. In particular, we pinpoint the complexity of these problems, and other related ones, showing them to be intractable. Finally, we present experiments on a real-world dataset, showing that our framework may contribute to a more robust feature scoring.

Details

JAIR Journal 2023 Journal Article

On the Complexity of Finding Set Repairs for Data-Graphs

  • Sergio Abriola
  • María Vanina Martínez
  • Nina Pardal
  • Santiago Cifuentes
  • Edwin Pin Baque

In the deeply interconnected world we live in, pieces of information link domains all around us. As graph databases embrace effectively relationships among data and allow processing and querying these connections efficiently, they are rapidly becoming a popular platform for storage that supports a wide range of domains and applications. As in the relational case, it is expected that data preserves a set of integrity constraints that define the semantic structure of the world it represents. When a database does not satisfy its integrity constraints, a possible approach is to search for a ‘similar’ database that does satisfy the constraints, also known as a repair. In this work, we study the problem of computing subset and superset repairs for graph databases with data values using a notion of consistency based on having a set of Reg-GXPath expressions as integrity constraints. We show that for positive fragments of Reg-GXPath these problems admit a polynomial-time algorithm, while the full expressive power of the language renders them intractable.

PDF Details DOI

KR Conference 2023 Conference Paper

Unified Foundations of Team Semantics via Semirings

  • Timon Barlag
  • Miika Hannula
  • Juha Kontinen
  • Nina Pardal
  • Jonni Virtema

Semiring semantics for first-order logic provides a way to trace how facts represented by a model are used to deduce satisfaction of a formula. Team semantics is a framework for studying logics of dependence and independence in diverse contexts such as databases, quantum mechanics, and statistics by extending first-order logic with atoms that describe dependencies between variables. Combining these two, we propose a unifying approach for analysing the concepts of dependence and independence via a novel semiring team semantics, which subsumes all the previously considered variants for first-order team semantics. In particular, we study the preservation of satisfaction of dependencies and formulae between different semirings. In addition we create links to reasoning tasks such as provenance, counting, and repairs.

PDF Details DOI

Highlights Conference 2023 Conference Abstract

Unified Foundations of Team Semantics via Semirings

  • Nina Pardal

Semiring semantics for first-order logic provides a way to trace how facts represented by a model are used to deduce satisfaction of a formula. Team semantics is a framework for studying logics of dependence and independence in diverse contexts such as databases, quantum mechanics, and statistics by extending first-order logic with atoms that describe dependencies between variables. Combining these two, we propose a unifying approach for analysing the concepts of dependence and independence via a novel semiring team semantics, which subsumes all the previously considered variants for first-order team semantics. In particular, we study the preservation of satisfaction of dependencies and formulae between different semirings. In addition we create links to reasoning tasks such as provenance, counting, and repairs. This is joint work with Timon Barlag, Miika Hannula, Juha Kontinen, and Jonni Virtema. Contributed talk given by Nina Pardal

Details
v2026.09.13