Source author record

Andrea Cali

Andrea Cali appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Databases Logic in Computer Science Artificial Intelligence Computational Complexity Data Structures and Algorithms

Catalog footprint

What is connected

4works

5topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

Regular resolution for CNFs with almost bounded one-sided treewidth

We introduce a one-sided incidence tree decomposition of a CNF $φ$. This is a tree decomposition of the incidence graph of $φ$ where the underlying tree is rooted and the set of bags containing each clause induces a directed path in the tree. The one-sided treewidth is the smallest width of a one-sided incidence tree decomposition. We consider a class of unsatisfiable CNF $φ$ that can be turned into one of one sided treewidth at most $k$ by removal of at most $p$ clauses. We show that the size of regular resolution for this class of CNFs is FPT parameterized by $k$ and $p$. The results contributes to understanding the complexity of resolution for CNFs of bounded incidence treewidth, an open problem well known in the areas of proof complexity and knowledge compilation. In particular, the result significantly generalizes all the restricted classes of CNFs of bounded incidence treewidth that are known to admit an FPT sized resolution. The proof includes an auxiliary result and several new notions that may be of an independent interest.

preprint2016arXiv

A Hybrid Approach to Query Answering under Expressive Datalog+/-

Datalog+/- is a family of ontology languages that combine good computational properties with high expressive power. Datalog+/- languages are provably able to capture the most relevant Semantic Web languages. In this paper we consider the class of weakly-sticky (WS) Datalog+/- programs, which allow for certain useful forms of joins in rule bodies as well as extending the well-known class of weakly-acyclic TGDs. So far, only non-deterministic algorithms were known for answering queries on WS Datalog+/- programs. We present novel deterministic query answering algorithms under WS Datalog+/-. In particular, we propose: (1) a bottom-up grounding algorithm based on a query-driven chase, and (2) a hybrid approach based on transforming a WS program into a so-called sticky one, for which query rewriting techniques are known. We discuss how our algorithms can be optimized and effectively applied for query answering in real-world scenarios.

preprint2013arXiv

Taming the Infinite Chase: Query Answering under Expressive Integrity Constraints

The chase algorithm is a fundamental tool for query evaluation and query containment under constraints, where the constraints are (sub-classes of) tuple-generating dependencies (TGDs) and equality generating depencies (EGDs). So far, most of the research on this topic has focused on cases where the chase procedure terminates, with some notable exceptions. In this paper we take a general approach, and we propose large classes of TGDs under which the chase does not always terminate. Our languages, in particular, are inspired by guarded logic: we show that by enforcing syntactic properties on the form of the TGDs, we are able to ensure decidability of the problem of answering conjunctive queries despite the non-terminating chase. We provide tight complexity bounds for the problem of conjunctive query evaluation for several classes of TGDs. We then introduce EGDs, and provide a condition under which EGDs do not interact with TGDs, and therefore do not take part in query answering. We show applications of our classes of constraints to the problem of answering conjunctive queries under F-Logic Lite, a recently introduced ontology language, and under prominent tractable Description Logics languages. All the results in this paper immediately extend to the problem of conjunctive query containment.

preprint2010arXiv

Querying Incomplete Data over Extended ER Schemata

Since Chen's Entity-Relationship (ER) model, conceptual modeling has been playing a fundamental role in relational data design. In this paper we consider an extended ER (EER) model enriched with cardinality constraints, disjointness assertions, and is-a relations among both entities and relationships. In this setting, we consider the case of incomplete data, which is likely to occur, for instance, when data from different sources are integrated. In such a context, we address the problem of providing correct answers to conjunctive queries by reasoning on the schema. Based on previous results about decidability of the problem, we provide a query answering algorithm that performs rewriting of the initial query into a recursive Datalog query encoding the information about the schema. We finally show extensions to more general settings. This paper will appear in the special issue of Theory and Practice of Logic Programming (TPLP) titled Logic Programming in Databases: From Datalog to Semantic-Web Rules.