Recently, there has been an increasing interest in extending Dung's framework with probability theory, leading to the Probabilistic Argumentation Framework (PAF), and with supports in addition to attacks, leading to the Bipolar Argumentation Framework (BAF). In this paper, we introduce the Conditional Probabilistic Bipolar Argumentation Framework (CPBAF), which extends Probabilistic and Bipolar AF by allowing conditional probabilities on arguments, attacks, and on (possibly cyclic) supports. In this setting, we address the problem of computing the probability that a given argument is accepted. This is carried out by introducing the concept of probabilistic explanation for a given (probabilistic) extension. We show that the complexity of the problem is FP^#P-hard and propose polynomial approximation algorithms with bounded additive error for CPBAF where cycles with an odd number of attacks are forbidden.

We present ARGUS, an end-to-end Argument Mining (AM) tool that exploits Large Language Models (LLMs) to automatically perform all core AM tasks, i.e., Argument Component Segmentation, Classification, Relation Identification, and Relation Classification. Furthermore, ARGUS builds the corresponding argumentation framework (AF) and seamlessly integrates symbolic solvers to compute extensions and perform formal reasoning. ARGUS is designed to ensure broad flexibility and usability, supporting any open-source or commercial LLMs and symbolic solvers, providing a ready-to-use platform for exploring neuro-symbolic approaches to argumentation in both research and practical applications.

Explainable AI has received significant attention in recent years. Machine learning models often operate as black boxes, lacking explainability and transparency while supporting decision-making processes. Local post-hoc explainability queries attempt to answer why individual inputs are classified in a certain way by a given model. While there has been important work on counterfactual explanations, less attention has been devoted to semifactual ones. In this paper, we focus on local post-hoc explainability queries within the semifactual `even-if' thinking and their computational complexity among different classes of models, and show that both linear and tree-based models are strictly more interpretable than neural networks. After this, we introduce a preference-based framework enabling users to personalize explanations based on their preferences, both in the case of semifactuals and counterfactuals, enhancing interpretability and user-centricity. Finally, we explore the complexity of several interpretability problems in the proposed preference-based framework and provide algorithms for polynomial cases.

Argumentation is an important research area in the field of AI. There is a substantial amount of work on different aspects of Dung's abstract Argumentation Framework (AF). Two relevant aspects considered separately so far are: i) extending the framework to account for recursive attacks and supports, and ii) considering dynamics, i.e., AFs evolving over time. In this paper, we jointly deal with these two aspects. We focus on High-Order Argumentation Frameworks with Necessities (HOAFNs) which allow for attack and support relations (interpreted as necessity) not only between arguments but also targeting attacks and supports at any level. We propose an approach for the incremental evaluation of the credulous acceptance problem in HOAFNs, by “incrementally” computing an extension (a set of accepted arguments, attacks and supports), if it exists, containing a given goal element in an updated HOAFN. In particular, we are interested in monitoring the credulous acceptance of a given argument, attack or support (goal) in an evolving HOAFN. Thus, our approach assumes to have a HOAFN Δ, a goal ϱ occurring in Δ, an extension E for Δ containing ϱ, and an update u establishing some changes in the original HOAFN, and uses the extension for first checking whether the update is relevant; for relevant updates, an extension of the updated HOAFN containing the goal is computed by translating the problem to the AF domain and leveraging on AF solvers. We provide formal results for our incremental approach and empirically show that it outperforms the evaluation from scratch of the credulous acceptance problem for an updated HOAFN.

Dung's Argumentation Framework (AF) has been extended in several directions to make knowledge representation and reasoning tasks more intuitive and/or expressive. We present a novel extension of AF called Featured AF (FAF), where each argument has associated a set of features expressed by means of unary and binary facts. In such a context, a query is expressed by means of a conjunctive relational calculus formula which is evaluated over the extensions of the FAF. Then, this framework is further expanded into the so-called Extended FAF (EFAF), where a first-order logic formula (FOL) is used for reasoning over `feasible' subframeworks that satisfy the FOL formula and minimally differ from the original framework. We investigate the computational complexity of verification and acceptance problems under several semantics and show that incomplete AF (iAF) frameworks, including correlated iAF and constrained iAF, are special cases of EFAF.

Dung's abstract Argumentation Framework (AF) has been extended in several directions to make knowledge representation and reasoning more intuitive and expressive. In this paper, we present the Knowledge-based Argumentation Framework (KAF), an extension of AF with a Knowledge Base (KB) expressed in DL-Lite, which includes concept and role instances describing the topology of an AF, besides additional knowledge on the domain. The KAF semantics is given by a set of KAF extensions, each consisting of an extension of the underlying AF together with a ``pertinent'' subset of the original KB, which is obtained by discarding assertions referring to arguments that have been ruled out in the AF extension. Then, the framework is further expanded into the Constrained KAF (CKAF), where a set of restricted relational calculus formulae is used for reasoning over `feasible' subframeworks that satisfy the formulae and minimally differ from the original framework. We thoroughly investigate the computational complexity of classical reasoning problems under popular argumentation semantics, and show that well-known AF-based frameworks are special cases of CKAF.

Dung’s Argumentation Framework (AF) has been extended in several directions. Among the numerous proposed extensions, three of them seem to be of particular interest and have correlations between them. These extensions are: constrained AF (CAF), where AF is augmented with (strong) constraints; epistemic AF (EAF), where AF is augmented with epistemic constraints; and incomplete AF (iAF), where arguments and attacks can be uncertain. While the complexity and expressiveness of CAF and iAF have been studied, that of EAF has not been explored so far. In this paper we investigate the complexity and expressivity of EAF. To this end, we first introduce the Labeled CAF (LCAF), a variation of CAF where constraints are defined over the alphabet of labeled arguments. Then, we investigate the complexity of credulous and skeptical reasoning and show that: i) EAF is more expressive than iAF (under preferred semantics), ii) although LCAF is a restriction of EAF where modal operators are not allowed, these frameworks have the same complexity, iii) the results for LCAF close a gap in the characterization of the complexity of CAF. Interestingly, even though EAF has the same complexity as LCAF, it allows modeling domain knowledge in a more natural and easy-to-understand way.

Explainable Artificial Intelligence and Formal Argumentation have received significant attention in recent years. Argumentation frameworks are useful for representing knowledge and reasoning on it. Counterfactual and semifactual explanations are interpretability techniques that provide insights into the outcome of a model by generating alternative hypothetical instances. While there has been important work on counterfactual and semifactual explanations for Machine Learning (ML) models, less attention has been devoted to these kinds of problems in argumentation. In this paper, we explore counterfactual and semifactual reasoning in abstract Argumentation Framework. We investigate the computational complexity of counterfactual- and semifactual-based reasoning problems, showing that they are generally harder than classical argumentation problems such as credulous and skeptical acceptance. Finally, we show that counterfactual and semifactual queries can be encoded in weak-constrained Argumentation Framework, and provide a computational strategy through ASP solvers.

Dealing with controversial information is an important issue in several application contexts. Formal argumentation enables reasoning on arguments for and against a claim to decide on an outcome. Dung's abstract Argumentation Framework (AF) has emerged as a central formalism in argument-based reasoning. Key aspects of the success and popularity of Dung's framework include its simplicity and expressiveness. Integrity constraints help to express domain knowledge in a compact and natural way, thus keeping easy the modeling task even for problems that otherwise would be hard to encode within an AF. In this paper, we first explore two intuitive semantics based on Kleene and Lukasiewicz logics, respectively, for AF augmented with (strong) constraints—the resulting argumentation framework is called Constrained AF (CAF). Then, we propose a new argumentation framework called Weak constrained AF (WAF) that enhances CAF with weak constraints. Intuitively, these constraints can be used to find “optimal” solutions to problems defined through CAF. We provide a detailed complexity analysis of CAF and WAF, showing that strong constraints do not increase the expressive power of AF in most cases, while weak constraints systematically increase the expressive power of CAF (and AF) under several well-known argumentation semantics.

Early suicidal ideation detection has long been regarded as an important task that can benefit both society and individuals. In this regard, it has been shown that, very frequently, the first symptoms of this problem can be identified by analyzing the contents shared on social media. Machine learning classification models have proven promising in capturing behavioral and textual features from posts shared on social media. This study proposes a novel machine-learning model to detect the risk of suicide from social media posts, employing both natural language processing and state-of-the-art deep learning techniques. We propose an ensemble LSTM-TCN model that benefits from a self-attention mechanism to detect suicidal ideation among users of two well-known social networks, Twitter (X) and Reddit. Furthermore, we present a comprehensive analysis of the data, examining the suicidal posts both statistically and semantically, which can provide rich knowledge about suicidal ideation. Our proposed model (AL-BTCN) outperforms the compared state-of-the-art models, resulting in over 94% accuracy, recall, and F1-score. Researchers, mental health specialists, and social media service providers can all benefit from the findings of this study.

Abstract Dung’s abstract Argumentation Framework (AF) has emerged as a key formalism for argumentation in artificial intelligence. It has been extended in several directions, including the possibility to express supports, leading to the development of the Bipolar Argumentation Framework (BAF), and recursive attacks and supports, resulting in the Recursive BAF (Rec-BAF). Different interpretations of supports have been proposed, whereas for Rec-BAF (where the target of attacks and supports may also be attacks and supports) even different semantics for attacks have been defined. However, the semantics of these frameworks have either not been defined in the presence of support cycles or are often quite intricate in terms of the involved definitions. We encompass this limitation and present classical semantics for general BAF and Rec-BAF and show that the semantics for specific BAF and Rec-BAF frameworks can be defined by very simple and intuitive modifications of that defined for the case of AF. This is achieved by providing a modular definition of the sets of defeated and acceptable elements for each AF-based framework. We also characterize, in an elegant and uniform way, the semantics of general BAF and Rec-BAF in terms of logic programming and partial stable model semantics.

Abstract Data exchange, the problem of transferring data from a source schema to a target schema, has been studied for several years. The semantics of answering positive queries over the target schema has been defined in early work, but little attention has been paid to more general queries. A few proposals of semantics for more general queries exist but they either do not properly extend the standard semantics under positive queries, giving rise to counterintuitive answers, or they make query answering undecidable even for the most important data exchange settings, for example, with weakly-acyclic dependencies. The goal of this paper is to provide a new semantics for data exchange that is able to deal with general queries. At the same time, we want our semantics to coincide with the classical one when focusing on positive queries, and to not trade-off too much in terms of complexity of query answering. We show that query answering is undecidable in general under the new semantics, but it is $\text{co}\text{NP}\text{-complete}$ when the dependencies are weakly-acyclic. Moreover, in the latter case, we show that exact answers under our semantics can be computed by means of logic programs with choice, thus exploiting existing efficient systems. For more efficient computations, we also show that our semantics allows for the construction of a representative target instance, similar in spirit to a universal solution, that can be exploited for computing approximate answers in polynomial time.

Dung's abstract Argumentation Framework (AF) has emerged as a central formalism in the area of knowledge representation and reasoning. Preferences in AF allow to represent the comparative strength of arguments in a simple yet expressive way. Preference-based AF (PAF) has been proposed to extend AF with preferences of the form a > b, whose intuitive meaning is that argument a is better than b. In this paper we generalize PAF by introducing conditional preferences of the form a > b \leftarrow body that informally state that a is better than b whenever the condition expressed by body is true. The resulting framework, namely Conditional Preference-based AF (CPAF), extends the PAF semantics under three well-known preference criteria, i.e. democratic, elitist, and KTV. After introducing CPAF, we study the complexity of the verification problem (deciding whether a set of arguments is a ``best'' extension) as well as of the credulous and skeptical acceptance problems (deciding whether a given argument belongs to any or all ``best'' extensions, respectively) under multiple-status semantics (that is, complete, preferred, stable, and semi-stable semantics) for the above-mentioned preference criteria.

Dung’s Argumentation Framework (AF) has been extended in several directions. An interesting extension, among others, is the Epistemic AF (EAF) which allows representing the agent’s belief by means of epistemic constraints. In particular, an epistemic constraint is a propositional formula over labeled arguments (e.g. in(a), out(c)) extended with the modal operators K and M that intuitively state that the agent believes that a given formula is certainly or possibly true, respectively. In this paper, focusing on EAF, we investigate the complexity of the possible and necessary variants of three canonical problems in abstract argumentation: verification, existence, and non-empty existence. Moreover, we explore the relationship between EAF and incomplete AF (iAF), an extension of AF where arguments and attacks may be uncertain. Our complexity analysis shows that the verification problem in iAF can be naturally reduced to the verification in EAF, while it turns out that a similar result cannot hold for the necessary (non-empty) existence problem.

In recent years there has been an increasing interest in extending Dung's framework to facilitate the knowledge representation and reasoning process. In this paper, we present an extension of Abstract Argumentation Framework (AF) that allows for the representation of preferences over arguments' truth values (3-valued preferences). For instance, we can express a preference stating that extensions where argument a is false (i.e. defeated) are preferred to extensions where argument b is false. Interestingly, such a framework generalizes the well-known Preference-based AF with no additional cost in terms of computational complexity for most of the classical argumentation semantics. Then, we further extend AF by considering both (3-valued) preferences and 3-valued constraints, that is constraints of the form \varphi \Rightarrow v or v \Rightarrow \varphi, where \varphi is a logical formula and v is a 3-valued truth value. After investigating the complexity of the resulting framework,as both constraints and preferences may represent subjective knowledge of agents, we extend our framework by considering multiple agents and study the complexity of deciding acceptance of arguments in this context.

Dung's Argumentation Framework (AF) has been extended in several directions, including the possibility of representing uncertainty about the existence of arguments and attacks. In this regard, two main proposals have been introduced in the literature: Probabilistic Argumentation Framework (PrAF) and Incomplete Argumentation Framework (iAF). PrAF is an extension of AF with probability theory, thus representing quantified uncertainty. In contrast, iAF represents unquantified uncertainty, that is it can be seen as a special case where we only know that some elements (arguments or attacks) are uncertain. In this paper, we first address the problem of computing the probability that a given argument is accepted in PrAF. This is carried out by introducing the concept of probabilistic explanation for any given (probabilistic) extension. We show that the complexity of the problem is FP#P-hard and propose polynomial approximation algorithms with bounded additive error for PrAFs where odd-length cycles are forbidden. We investigate the approximate complexity of the related FP#P-hard problems of credulous and skeptical acceptance in PrAF, showing that they are generally harder than the problem of computing the probability that a given argument is accepted. Next we consider iAF and, after showing some equivalence properties among classes of iAFs, we study iAF as a special case of PrAF where uncertain elements have associated a probability equal to 1/2. Finally, given this result, we investigate the relationships between iAF acceptance problems and probabilistic acceptance in PrAF.

Abstract Nowadays, cloud computing provides easy access to a set of variable and configurable computing resources based on user demand through the network. Cloud computing services are available through common internet protocols and network standards. In addition to the unique benefits of cloud computing, insecure communication and attacks on cloud networks cannot be ignored. There are several techniques for dealing with network attacks. To this end, network anomaly detection systems are widely used as an effective countermeasure against network anomalies. The anomaly-based approach generally learns normal traffic patterns in various ways and identifies patterns of anomalies. Network anomaly detection systems have gained much attention in intelligently monitoring network traffic using machine learning methods. This paper presents an efficient model based on autoencoders for anomaly detection in cloud computing networks. The autoencoder learns a basic representation of the normal data and its reconstruction with minimum error. Therefore, the reconstruction error is used as an anomaly or classification metric. In addition, to detecting anomaly data from normal data, the classification of anomaly types has also been investigated. We have proposed a new approach by examining an autoencoder’s anomaly detection method based on data reconstruction error. Unlike the existing autoencoder-based anomaly detection techniques that consider the reconstruction error of all input features as a single value, we assume that the reconstruction error is a vector. This enables our model to use the reconstruction error of every input feature as an anomaly or classification metric. We further propose a multi-class classification structure to classify the anomalies. We use the CIDDS-001 dataset as a commonly accepted dataset in the literature. Our evaluations show that the performance of the proposed method has improved considerably compared to the existing ones in terms of accuracy, recall, false-positive rate, and F1-score metrics.

Dung’s Argumentation Framework (AF) has been extended in several directions, including the possibility of representing unquantified uncertainty about the existence of arguments and attacks. The framework resulting from such an extension is called incomplete AF (iAF). In this paper, we first introduce three new satisfaction problems named totality, determinism and functionality, and investigate their computational complexity for both AF and iAF under several semantics. We also investigate the complexity of credulous and skeptical acceptance in iAF under semi-stable semantics—a problem left open in the literature. We then show that any iAF can be rewritten into an equivalent one where either only (unattacked) arguments or only attacks are uncertain. Finally, we relate iAF to probabilistic argumentation framework, where uncertainty is quantified.

Dung's abstract Argumentation Framework (AF) has emerged as a central formalism for argumentation in AI. Preferences in AF allow to represent the comparative strength of arguments in a simple yet expressive way. In this paper we first investigate the complexity of the verification as well as credulous and skeptical acceptance problems in Preference-based AF (PAF) that extends AF with preferences over arguments. Next, after introducing new semantics for AF where extensions are selected using cardinality (instead of set inclusion) criteria and investigating their complexity, we introduce a framework called AF with Priority rules (AFP) that extends AF with sequences of priority rules. AFP generalizes AF with classical set-inclusion and cardinality based semantics, suggesting that argumentation semantics can be viewed as ways to express priorities among extensions. Finally, we extend AFP by proposing AF with Priority rules and Preferences (AFP^2), where also preferences over arguments can be used to define priority rules, and study the complexity of the above-mentioned problems.

Dung's abstract Argumentation Framework (AF) has emerged as a central formalism in formal argumentation. Key aspects of the success and popularity of Dung's framework include its simplicity and expressiveness. Integrity constraints help to express domain knowledge in a compact and natural way, thus keeping easy the modeling task even for problems that otherwise would be hard to encode within an AF. In this paper, after providing an intuitive semantics based on Lukasiewicz's logic for AFs with (strong) constraints, called Constrained AFs (CAFs), we propose Weak constrained AFs (WAFs) that enhance CAFs with weak constraints. Intuitively, these constraints can be used to find ``optimal'' solutions to problems defined through CAFs. We provide a detailed complexity analysis of CAFs and WAFs, showing that strong constraints do not increase the expressive power of AFs in most cases, while weak constraints systematically increase the expressive power of CAFs under several well-known argumentation semantics.

Extensions of Dung’s Argumentation Framework (AF) include the class of Recursive Bipolar AFs (Rec-BAFs), i.e. AFs with recursive attacks and supports. We show that a Rec-BAF \Delta can be translated into a logic program P_\Delta so that the extensions of \Delta under different semantics coincide with subsets of the partial stable models of P_\Delta.

Attack-Support Argumentation Framework (ASAF) is an extension of the Bipolar Argumentation Framework that allows for attacks and supports not only between arguments but also targeting attacks and supports at any level. In this paper we propose an incremental approach for computing the skeptical preferred acceptance in dynamic ASAFs. Specifically, we investigate how the skeptical acceptance of a goal element (an argument, an attack, or a support) evolves when a given ASAF is updated by adding or retracting an argument, an attack, or a support, and propose an incremental algorithm for solving this problem. Our approach relies on identifying a portion of the given ASAF which is sufficient to determine the status of the goal w.r.t. the updated ASAF. We experimentally evaluate our approach showing that it outperforms the computation from scratch on average.

Argumentation is an important topic in the field of AI. There is a substantial amount of work about different aspects of Dung's abstract Argumentation Framework (AF). Two relevant aspects considered separately so far are extending the framework to account for recursive attacks and supports, and considering dynamics, i.e., AFs evolving over time. In this paper, we jointly deal with these two aspects. We focus on Attack-Support Argumentation Frameworks (ASAFs) which allow for attack and support relations not only between arguments but also targeting attacks and supports at any level, and propose an approach for the incremental computation of extensions (sets of accepted arguments, attacks and supports) of updated ASAFs. Our approach assumes that an initial ASAF extension is given and uses it for first checking whether updates are irrelevant; for relevant updates, an extension of an updated ASAF is computed by translating the problem to the AF domain and leveraging on AF solvers. We experimentally show our incremental approach outperforms the direct computation of extensions for updated ASAFs.

Consistent query answering is a principled approach for querying inconsistent databases. It relies on two basic notions: the notion of a repair, that is, a consistent database that "minimally" differs from the original one, and the notion of a consistent query answer, that is, a query answer that can be derived from every repair. In general, an inconsistent database can admit multiple repairs, each corresponding to a different way of restoring consistency, and the consistent query answering framework does not make any discrimination among them. However, in many applications it is natural and desired to express preferences among the different choices that can be made to resolve inconsistency.

Recently there has been an increasing interest in probabilistic abstract argumentation, an extension of Dung's abstract argumentation framework with probability theory. In this setting, we address the problem of computing the probability that a given argument is accepted. This is carried out by introducing the concept of probabilistic explanation for a given (probabilistic) extension. We show that the complexity of the problem is FP^#P-hard and propose polynomial approximation algorithms with bounded additive error for probabilistic argumentation frameworks where odd-length cycles are forbidden. This is quite surprising since, as we show, such kind of approximation algorithm does not exist for the related FP^#P-hard problem of computing the probability of the credulous acceptance of an argument, even for the special class of argumentation frameworks considered in the paper.

Query answering over inconsistent knowledge bases is a problem that has attracted a great deal of interest over the years. Different inconsistency-tolerant semantics have been proposed, and most of them are based on the notion of repair, that is, a "maximal" consistent subset of the database. In general, there can be several repairs, so it is often natural and desirable to express preferences among them. In this paper, we propose a framework for querying inconsistent knowledge bases under user preferences for existential rule languages. We provide generalizations of popular inconsistency-tolerant semantics taking preferences into account and study the data and combined complexity of different relevant problems.

Abstract Recently there has been an increasing interest in frameworks extending Dung’s abstract Argumentation Framework (AF). Popular extensions include bipolar AFs and AFs with recursive attacks and necessary supports. Although the relationships between AF semantics and Partial Stable Models (PSMs) of logic programs has been deeply investigated, this is not the case for more general frameworks extending AF. In this paper we explore the relationships between AF-based frameworks and PSMs. We show that every AF-based framework Δ can be translated into a logic program PΔ so that the extensions prescribed by different semantics of Δ coincide with subsets of the PSMs of PΔ. We provide a logic programming approach that characterizes, in an elegant and uniform way, the semantics of several AF-based frameworks. This result allows also to define the semantics for new AF-based frameworks, such as AFs with recursive attacks and recursive deductive supports.

Though there has been an extensive body of work on efficiently solving computational problems for static Dung's argumentation frameworks (AFs), little work has been done for handling dynamic AFs and in particular for deciding the skeptical acceptance of a given argument. In this paper we devise an efficient algorithm for computing the skeptical preferred acceptance in dynamic AFs. More specifically, we investigate how the skeptical acceptance of an argument (goal) evolves when the given AF is updated and propose an efficient algorithm for solving this problem. Our algorithm, called SPA, relies on two main ideas: i) computing a small portion of the input AF, called "context-based" AF, which is sufficient to determine the status of the goal in the updated AF, and ii) incrementally computing the ideal extension to further restrict the context-based AF. We experimentally show that SPA significantly outperforms the computation from scratch, and that the overhead of incrementally maintaining the ideal extension pays off as it speeds up the computation.

Extended argumentation frameworks (EAFs) extend Dung's argumentation frameworks (AFs) to represent a kind of defeasible attack (by relying on the concept of second-order attack), in addition to the Dung's classical notion of attack between arguments. EAFs can be profitably used to model disputes between agents, with the aim of deciding the sets of arguments (called extensions) that should be accepted to support a point of view in a discussion. However, since new arguments and attacks are often introduced to take into account new available knowledge, EAFs as well as their extensions change over the time.

Incomplete information arises in many database applications, such as data integration, data exchange, inconsistency management, data cleaning, ontological reasoning, and many others. A principled way of answering queries over incomplete databases is to compute certain answers, which are query answers that can be obtained from every complete database represented by an incomplete one.

Consistent query answering is a principled approach for querying inconsistent knowledge bases. It relies on the notion of a "repair", that is, a maximal consistent subset of the facts in the knowledge base. One drawback of this approach is that entire facts are deleted to resolve inconsistency, even if they may still contain useful "reliable" information. To overcome this limitation, we propose a new notion of repair allowing values within facts to be updated for restoring consistency. This more fine-grained repair primitive allows us to preserve more information in the knowledge base. We also introduce the notion of a "universal repair", which is a compact representation of all repairs. Then, we show that consistent query answering in our framework is intractable (coNP-complete). In light of this result, we develop a polynomial time approximation algorithm for computing a sound (but possibly incomplete) set of consistent query answers.

Incomplete information arises in many current database applications. Certain answers are a widely accepted semantics of query answering over incomplete databases. Since their computation is a coNP-hard problem, recent research has focused on developing polynomial time approximation algorithms computing a sound (but possibly incomplete) set of certain answers. In this demo we showcase ACID, a system to compute sound sets of certain answers. The central tools of its underlying algorithms are conditional tables and the conditional evaluation of relation algebra. Different evaluation strategies can be applied, with more accurate ones having higher complexity, but returning more certain answers. We show how to query incomplete databases using the ACID system, which offers a suite of approximation algorithms enabling users to choose the technique that best meets their needs in terms of balance between efficiency and quality of the result's approximation.

Computing shortest distances is a central task in many domains. The growing number of applications dealing with dynamic graphs calls for incremental algorithms, as it is impractical to recompute shortest distances from scratch every time updates occur. In this paper, we address the problem of maintaining all-pairs shortest distances in dynamic graphs. We propose efficient incremental algorithms to process sequences of edge deletions/insertions/updates and vertex deletions/insertions. The proposed approach relies on some general operators that can be easily “instantiated” both in main memory and on top of different underlying DBMSs. We provide complexity analyses of the proposed algorithms. Experimental results on several real-world datasets show that current main-memory algorithms become soon impractical, disk-based ones are needed for larger graphs, and our approach significantly outperforms state-of-the-art algorithms.

Abstract argumentation frameworks (AFs) are a well-known formalism for modelling and deciding many argumentation problems. Computational issues and evaluation algorithms have been deeply investigated for static AFs, whose structure does not change over the time. However, AFs are often dynamic as a consequence of the fact that argumentation is inherently dynamic. In this paper, we tackle the problem of incrementally computing extensions for dynamic AFs: given an initial extension and an update (or a set of updates), we devise a technique for computing an extension of the updated AF under four well-known semantics (i.e., complete, preferred, stable, and grounded). The idea is to identify a reduced (updated) AF sufficient to compute an extension of the whole AF and use state-of-the-art algorithms to recompute an extension of the reduced AF only. The experiments reveal that, for all semantics considered and using different solvers, the incremental technique is on average two orders of magnitude faster than computing the semantics from scratch.

In this article, we propose a new technique for checking whether the bottom-up evaluation of logic programs with function symbols terminates. The technique is based on the definition of mappings from arguments to strings of function symbols, representing possible values which could be taken by arguments during the bottom-up evaluation. Starting from mappings, we identify mapping-restricted arguments, a subset of limited arguments, namely arguments that take values from finite domains. Mapping-restricted programs, consisting of rules whose arguments are all mapping restricted, are terminating under the bottom-up computation, as all of its arguments take values from finite domains. We show that mappings can be computed by transforming the original program into a unary logic program: this allows us to establish decidability of checking if a program is mapping restricted. We study the complexity of the presented approach and compare it to other techniques known in the literature. We also introduce an extension of the proposed approach that is able to recognize a wider class of logic programs. The presented technique provides a significant improvement, as it can detect terminating programs not identified by other criteria proposed so far. Furthermore, it can be combined with other techniques to further enlarge the class of programs recognized as terminating under the bottom-up evaluation.

Computing shortest distances is a central task in many graph applications. Although many algorithms to solve this problem have been proposed, they are designed to work in the main memory and/or with static graphs, which limits their applicability to many current applications where graphs are subject to frequent updates. In this paper, we propose novel efficient incremental algorithms for maintaining all-pairs shortest distances in dynamic graphs. We experimentally evaluate our approach on real-world datasets, showing that it outperforms current algorithms designed for the same problem.

We address the problem of efficiently computing the extensions of abstract argumentation frameworks (AFs) which are updated by adding/deleting arguments or attacks. We focus on the two most popular ‘deterministic’ semantics (namely, grounded and ideal) and present two approaches for their incremental computation, well-suited to dynamic applications where updates to an initial AF are frequently performed to take into account new available knowledge.

Computing shortest distances is a central task in many graph applications. Since it is impractical to recompute shortest distances from scratch every time the graph changes, many algorithms have been proposed to incrementally maintain shortest distances after edge deletions or insertions.

The chase is a well-known algorithm with a wide range of applications in data exchange, data cleaning, data integration, query optimization, and ontological reasoning. Since the chase evaluation might not terminate and it is undecidable whether it terminates, the problem of defining (decidable) sufficient conditions ensuring termination has received a great deal of interest in recent years. In this regard, several termination criteria have been proposed. One of the main weaknesses of current approaches is the limited analysis they perform on equality generating dependencies (EGDs). In this paper, we propose sufficient conditions ensuring that a set of dependencies has at least one terminating chase sequence. We propose novel criteria which are able to perform a more accurate analysis of EGDs. Specifically, we propose a new stratification criterion and an adornment algorithm. The latter can both be used as a termination criterion and be combined with current techniques to make them more effective, in that strictly more sets of dependencies are identified. Our techniques identify sets of dependencies that are not recognized by any of the current criteria.

Abstract It is widely acknowledged that function symbols are an important feature in answer set programming, as they make modelling easier, increase the expressive power, and allow us to deal with infinite domains. The main issue with their introduction is that the evaluation of a program might not terminate and checking whether it terminates or not is undecidable. To cope with this problem, several classes of logic programs have been proposed where the use of function symbols is restricted but the program evaluation termination is guaranteed. Despite the significant body of work in this area, current approaches do not include many simple practical programs whose evaluation terminates. In this paper, we present the novel classes ofrule-boundedandcycle-bounded programs, which overcome different limitations of current approaches by performing a more global analysis of how terms are propagated from the body to the head of rules. Results on the correctness, the complexity, and the expressivity of the proposed approach are provided.

The aim of this paper is to present more general criteria and techniques for chase termination. We first present extensions of the well-known stratification criterion and introduce a new criterion, called local stratification, which generalizes both super-weak acyclicity and stratification-based criteria (including the class of constraints which are inductively restricted). Next, the paper presents a rewriting algorithm transforming the original set of constraints Σ into an “equivalent” set Σαand verifying the structural properties for chase termination on Σα. The rewriting of constraints allows us to recognize larger classes of constraints for which chase termination is guaranteed. In particular, we show that if Σ satisfies chase termination conditions T, then the rewritten set Σαsatisfies T as well, but the vice versa is not true, that is there are significant classes of constraints for which Σαsatisfies T and Σ does not. A more general rewriting algorithm producing as output an equivalent set of dependencies and a Boolean value stating whether a sort of cyclicity has been detected is also proposed. The new rewriting technique and the checking of acyclicity allow us to introduce the class of acyclic constraints, which generalizes local stratification and guarantees that all chase sequences are finite with a length polynomial in the size of the input database.

Abstract Recently, there has been an increasing interest in the bottom-up evaluation of the semantics of logic programs with complex terms. The presence of function symbols in the program may render the ground instantiation infinite, and finiteness of models and termination of the evaluation procedure, in the general case, are not guaranteed anymore. Since the program termination problem is undecidable in the general case, several decidable criteria (called program termination criteria) have been recently proposed. However, current conditions are not able to identify even simple programs, whose bottom-up execution always terminates. The paper introduces new decidable criteria for checking termination of logic programs with function symbols under bottom-up evaluation, by deeply analyzing the program structure. First, we analyze the propagation of complex terms among arguments by means of the extended version of the argument graph calledpropagation graph. The resulting criterion, calledacyclicity, generalizes most of the decidable criteria proposed so far. Next, we study how rules may activate each other and define a more powerful criterion, calledsafety. This criterion uses the so-calledsafety functionable to analyze how rules may activate each other and how the presence of some arguments in a rule limits its activation. We also study the application of the proposed criteria to bound queries and show that the safety criterion is well-suited to identify relevant classes of programs and bound queries. Finally, we propose a hierarchy of classes of terminating programs, calledk-safety, where thek-safe class strictly includes the (k-1)-safe class.

A database is called uncertain if two or more tuples of the same relation are allowed to agree on their primary key. Intuitively, such tuples act as alternatives for each other. A repair (or possible world) of such uncertain database is obtained by selecting a maximal number of tuples without ever selecting two tuples of the same relation that agree on their primary key. For a Boolean query q , the problem CERTAINTY( q ) takes as input an uncertain database db and asks whether q evaluates to true on every repair of db. In recent years, the complexity of CERTAINTY( q ) has been studied under different restrictions on q . These complexity studies have assumed no restrictions on the uncertain databases that are input to CERTAINTY( q ). In practice, however, it may be known that these input databases are partially consistent, in the sense that they satisfy some dependencies (e.g., functional dependencies). In this article, we introduce the problem CERTAINTY( q ) in the presence of a set Σ of dependencies. The problem CERTAINTY( q , Σ) takes as input an uncertain database db that satisfies Σ, and asks whether every repair of db satisfies q . We focus on the complexity of CERTAINTY( q , Σ) when q is an acyclic conjunctive query without self-join, and Σ is a set of functional dependencies and join dependencies, the latter of a particular form. We provide an algorithm that, given q and Σ, decides whether CERTAINTY( q , Σ) is first-order expressible. Moreover, we show how to effectively construct a first-order definition of CERTAINTY( q , Σ) if it exists.

In this paper we propose a new technique for checking whether the bottom-up evaluation of logic programs with function symbols terminates. The technique is based on the definition of mappings from arguments to strings of function symbols, representing possible values which could be taken by arguments during the bottom-up evaluation. Such mappings can be computed by transforming the original program into a unary logic program whose termination is decidable. Starting from mappings we can identify mapping-restricted arguments, a subset of limited arguments, that is, arguments which can take values from finite domains. The class of mapping-restricted programs, consisting of programs whose arguments are mapping-restricted, is terminating under the bottom-up computation as all its arguments can take values from finite domains. We study the complexity of the presented approach and compare it with other techniques known in the literature. The presented technique is relevant as it individuates as terminating programs not detected by other criteria proposed so far and can be combined with other techniques to further enlarge the class of programs recognized as terminating under the bottom-up evaluation.

Abstract Recent years have witnessed an increasing interest in enhancing answer set solvers by allowing function symbols. Since the introduction of function symbols makes common inference tasks undecidable, research has focused on identifying classes of programs allowing only a restricted use of function symbols while ensuring decidability of common inference tasks. Finitely-ground programs, introduced in Calimeri et al. (2008), are guaranteed to admit a finite number of stable models with each of them of finite size. Stable models of such programs can be computed and thus common inference tasks become decidable. Unfortunately, checking whether a program is finitely-ground is semi-decidable. This has led to several decidable criteria, called termination criteria, providing sufficient conditions for a program to be finitely-ground. This paper presents a new technique that, used in conjunction with current termination criteria, allows us to detect more programs as finitely-ground. Specifically, the proposed technique takes a logic program ${\cal P}$ and transforms it into an adorned program ${{\cal P}}$ μ with the aim of applying termination criteria to ${{\cal P}}$ μ rather than ${\cal P}$ . The transformation is sound in that if the adorned program satisfies a certain termination criterion, then the original program is finitely-ground. Importantly, applying termination criteria to adorned programs rather than the original ones strictly enlarges the class of programs recognized as finitely-ground.

Several database areas such as data exchange and integration share the problem of fixing database instance violations with respect to a set of constraints. The chase algorithm solves such violations by inserting tuples and setting the value of nulls. Unfortunately, the chase algorithm may not terminate and the problem of deciding whether the chase process terminates is undecidable. Recently there has been an increasing interest in the identification of sufficient structural properties of constraints which guarantee that the chase algorithm terminates [8, 10, 14, 15]. In this paper we propose an original technique which allows to improve current conditions detecting chase termination. Our proposal consists in rewriting the original set of constraints Σ into an 'equivalent' set Σ α and verifying the structural properties for chase termination on Σ α . The rewriting of constraints allows to recognize larger classes of constraints for which chase termination is guaranteed. In particular, we show that if Σ satisfies chase termination conditions T, then the rewritten set Σ α satisfies T as well, but the vice versa is not true, that is there are significant classes of constraints for which Σ α satisfies T and Σ does not.

Dealing with structure and content semantics underlying semistructured documents is challenging for any task of document management and knowledge discovery conceived for such data. In this work we address the novel problem of clustering semantically related XML documents according to their structure and content features. XML features are generated by enriching syntactic with semantic information based on a lexical knowledge base. The backbone of the proposed framework for the semantic clustering of XML documents is a data representation model that exploits the notion of tree tuple to identify semantically cohesive substructures in XML documents and represent them as transactional data. This framework is equipped with two clustering algorithms based on different paradigms, namely centroid-based partitional clustering and frequent-itemset-based hierarchical clustering. An extensive experimental evaluation was conducted on real data sets from various domains, showing the significance of our approach as a solution for the semantic clustering of XML documents.

Abstract This paper presents a logic language for expressing search and optimization problems. Specifically, first a language obtained by extending (positive) DATALOG with intuitive and efficient constructs (namely, stratified negation, constraints, and exclusive disjunction) is introduced. Next, a further restricted language only using a restricted form of disjunction to define (nondeterministically) subsets (or partitions) of relations is investigated. This language, called atalog, captures the power of DATALOG¬ in expressing search and optimization problems. A system prototype implementing atalog is presented. The system translates atalog queries into Optimization Programming Language (OPL) programs which are executed by the ILOG OPL Development Studio. Our proposal combines easy formulation of problems, expressed by means of a declarative logic language, with the efficiency of the ILOG System. Several experiments show the effectiveness of this approach.

Clustering ensembles has been recently recognized as an emerging approach to provide more robust solutions to the data clustering problem.Current methods of clustering ensembles typically fall into instance-based, cluster-based, or hybrid approaches; however, most of such methods fail in discriminating among the various clusterings that participate to the ensemble.In this paper, we address the problem of weighting clustering ensembles by proposing general weighting approaches based on different implementations of the notion of diversity.We introduce three weighting schemes for clustering ensembles, called Single Weighting, Group Weighting and Dendrogram Weighting, which are independent of the particular method of clustering ensembles and designed to take into account correlations among the individual clustering solutions in different ways.We show how these schemes can be instantiated into any instance-based, cluster-based and hybrid clustering ensembles methods.Experiments have shown that the performance of the clustering ensembles algorithms increases when the proposed weighting schemes are employed.

This paper introduces active integrity constraints (AICs), an extension of integrity constraints for consistent database maintenance. An active integrity constraint is a special constraint whose body contains a conjunction of literals which must be false and whose head contains a disjunction of update actions representing actions (insertions and deletions of tuples) to be performed if the constraint is not satisfied (that is its body is true). The AICs work in a domino-like manner as the satisfaction of one AIC may trigger the violation and therefore the activation of another one. The paper also introduces founded repairs, which are minimal sets of update actions that make the database consistent, and are specified and ldquosupportedrdquo by active integrity constraints. The paper presents: 1) a formal declarative semantics allowing the computation of founded repairs and 2) a characterization of this semantics obtained by rewriting active integrity constraints into disjunctive logic rules, so that founded repairs can be derived from the answer sets of the derived logic program. Finally, the paper studies the computational complexity of computing founded repairs.

In recent years there has been a growing interest in clustering uncertain data. In contrast to traditional, "sharp" data representation models, uncertain data objects can be represented in terms of an uncertainty region over which a probability density function (pdf) is defined. In this context, the focus has been mainly on partitional and density-based approaches, whereas hierarchical clustering schemes have drawn less attention. We propose a centroid-linkage-based agglomerative hierarchical algorithm for clustering uncertain objects, named U-AHC. The cluster merging criterion is based on an information-theoretic measure to compute the distance between cluster prototypes. These prototypes are represented as mixture densities that summarize the pdfs of all the uncertain objects in the clusters. Experiments have shown that our method outperforms state-of-the-art clustering algorithms from an accuracy viewpoint while achieving reasonably good efficiency.

BACKGROUND: Isotope-coded affinity tags (ICAT) is a method for quantitative proteomics based on differential isotopic labeling, sample digestion and mass spectrometry (MS). The method allows the identification and relative quantification of proteins present in two samples and consists of the following phases. First, cysteine residues are either labeled using the ICAT Light or ICAT Heavy reagent (having identical chemical properties but different masses). Then, after whole sample digestion, the labeled peptides are captured selectively using the biotin tag contained in both ICAT reagents. Finally, the simplified peptide mixture is analyzed by nanoscale liquid chromatography-tandem mass spectrometry (LC-MS/MS). Nevertheless, the ICAT LC-MS/MS method still suffers from insufficient sample-to-sample reproducibility on peptide identification. In particular, the number and the type of peptides identified in different experiments can vary considerably and, thus, the statistical (comparative) analysis of sample sets is very challenging. Low information overlap at the peptide and, consequently, at the protein level, is very detrimental in situations where the number of samples to be analyzed is high. RESULTS: We designed a method for improving the data processing and peptide identification in sample sets subjected to ICAT labeling and LC-MS/MS analysis, based on cross validating MS/MS results. Such a method has been implemented in a tool, called EIPeptiDi, which boosts the ICAT data analysis software improving peptide identification throughout the input data set. Heavy/Light (H/L) pairs quantified but not identified by the MS/MS routine, are assigned to peptide sequences identified in other samples, by using similarity criteria based on chromatographic retention time and Heavy/Light mass attributes. EIPeptiDi significantly improves the number of identified peptides per sample, proving that the proposed method has a considerable impact on the protein identification process and, consequently, on the amount of potentially critical information in clinical studies. The EIPeptiDi tool is available at http://bioingegneria.unicz.it/~veltri/projects/eipeptidi/ with a demo data set. CONCLUSION: EIPeptiDi significantly increases the number of peptides identified and quantified in analyzed samples, thus reducing the number of unassigned H/L pairs and allowing a better comparative analysis of sample data sets.

This work is a contribution to prioritized reasoning in logic programming in the presence of preference relations involving atoms. The technique, providing a new interpretation for prioritized logic programs, is inspired by the semantics of Prioritized Logic Programming and enriched with the use of structural information of preference of Answer Set Optimization Programming. Specifically, the analysis of the logic program is carried out together with the analysis of preferences in order to determine the choice order and the sets of comparable models. The new semantics is compared with other approaches known in the literature and complexity analysis is also performed, showing that, with respect to other similar approaches previously proposed, the complexity of computing preferred stable models does not increase.

We present DSA - Derivative time series Segment Approximation, a novel representation model for time series designed for effective and efficient similarity search. DSA substantially exploits derivative estimation, segmentation and dimensionality reduction to meet at least the requirements of high sensitivity to main features (trends) of time series and robustness to outliers. Experiments show that DSA is drastically faster and still as good or better than the prominent state-of-the-art similarity methods.

The increasing availability of heterogeneous XML informative sources has raised a number of issues concerning how to represent and manage semistructured data. Although XML sources can exhibit proper structures and contents, differently annotated XML documents may in principle encode related semantics due to subjective definitions of markup tags. Discovering knowledge to infer semantic organization of XML documents has become a major challenge in XML data management. In this context, we address the problem of clustering XML data according to structure as well as content features enriched with lexical ontology knowledge. We propose a framework for clustering semantically cohesive XML structures based on a transactional representation model. Experiments on large real datasets give evidence that the proposed approach is highly effective in detecting groups of XML data that exhibit structure and/or content affinities.

This paper presents a logic language, called NP Datalog for NP search and optimization problems. The 'search' language extends stratified Datalog with constraints and partition rules defining (nondeterministically) partition of relations. NP optimization problems are then formulated by adding a max (or min) construct to select the solution (stable model) which maximizes (resp., minimizes) the result of a polynomial function applied to the answer relation. We show that NP Datalog queries can be easily evaluated by translating them into ILOG programs which are next solved by means of the ILOG OPL Studio suite. To prove the effectiveness of our proposal, we have implemented a module, written in Sicstus Prolog, which takes in input a NP Datalog query and outputs an equivalent ILOG program. Several experiments comparing the computation of queries by different logic systems have been also performed.

This paper presents a technique for the optimization of bound queries over disjunctive deductive databases with constraints. The proposed approach is an extension of the well-known Magic-Set technique and is well-suited for being integrated in current bottom-up (stable) model inference engines. More specifically, it is based on the exploitation of binding propagation techniques which reduce the size of the data relevant to answer the query and, consequently, reduces both the complexity of computing a single model and the number of models to be considered. The motivation of this work stems from the observation that traditional binding propagation optimization techniques for bottom-up model generator systems, simulating the goal driven evaluation of top-down engines, are only suitable for positive (disjunctive) queries, while hard problems are expressed using unstratified negation. The main contribution of the paper consists in the extension of a previous technique, defined for positive disjunctive queries, to queries containing both disjunctive heads and constraints (a simple and expressive form of unstratified negation). As the usual way of expressing declaratively hard problems is based on the guess-and-check technique, where the guess part is expressed by means of disjunctive rules and the check part is expressed by means of constraints, the technique proposed here is highly relevant for the optimization of queries expressing hard problems. The value of the technique has been proved by several experiments.

In this paper we deal with inconsistent databases and propose a logic framework that allows specifying sets of actions which should be performed to make databases consistent (repairs). The motivation of this work stems from the observation that in repairing a database it is natural to express among a set of update operations, the (preferred) actions which should be performed to repair the database. We introduce (conditioned) active integrity constraints, a simple and powerful form of active rules with declarative semantics, well suited for computing database repairs and consistent answers. We first consider a "prescriptive" semantics where the allowed actions are those specified by the constraints. Under such a semantics the existence of repairs and consistent answers is not guaranteed. Thus, we also investigate the class of universally quantified constraints under a different semantics where actions are interpreted as preference conditions on the set of possible repairs ("preferable" semantics). Under such a semantics every database with integrity constraints admits repairs and consistent answers. We show that (conditioned) active integrity constraints can be rewritten into disjunctive Datalog programs with classical negation and that (preferred) repairs can be derived through the computation of (preferred) disjunctive stable models. We study the complexity of computing repairs and consistent answers and show that active integrity constraints can also be used to express hard problems.

In this paper, we propose a variant of stable model semantics for disjunctive logic programming and deductive databases. The semantics, called minimal founded, generalizes stable model semantics for normal (i.e. non-disjunctive) programs, but differs from disjunctive stable model semantics (the extension of stable model semantics for disjunctive programs). Compared with disjunctive stable model semantics, minimal founded semantics seems to be more intuitive, it gives meaning to programs which are meaningless under stable model semantics and is no harder to compute. More specifically, minimal founded semantics differs from stable model semantics only for disjunctive programs having constraint rules or rules working as constraints. We study the expressive power of the semantics, and show that for general disjunctive datalog programs it has the same power as disjunctive stable model semantics.

The objective of this paper is to investigate the problems related to the extensional integration of information sources. In particular, we propose an approach for managing inconsistent databases, i.e. databases violating integrity constraints. The presence of inconsistent data can be resolved by "repairing" the database, i.e. by providing a computational mechanism that ensures obtaining consistent "scenarios" of the information or by consistently answering to queries posed on an inconsistent set of data. In this paper we consider preferences among repairs and possible answers by introducing a partial order among them on the base of some preference criteria. More specifically, preferences are expressed by considering polynomial functions applied to repairs and returning real numbers. The goodness of a repair is measured by estimating how much it violates the desiderata conditions and a repair is preferred if it minimizes the value of the polynomial function used to express the preference criteria. The main contribution of this work consists in the proposal of a logic approach for querying and repairing inconsistent databases that extends previous works by allowing to express and manage preference criteria. The approach here proposed allows to express reliability on the information sources and is also suitable for expressing decision and optimization problems. The introduction of preference criteria strongly reduces the number of feasible repairs and answers; for special classes of constraints and functions it gives a unique repair and answer.

In this paper we present a technique for the optimization of bound queries over disjunctive deductive databases with constraints. The proposed approach consists of two distinct phases: i) the rewriting of queries for propagating bindings from the query goal into the program, and ii) the use of specialized algorithms computing rewritten queries. The rewriting of queries is based on the exploitation of a binding propagation technique which reduces the size of the data relevant to answer the query and, consequently, minimizes both the complexity of computing a single model and the whole number of models to be considered. As for general queries the rewriting technique does not ensure soundness, we present two sound and complete algorithms computing rewritten queries under brave and cautious reasoning. The efficiency of our algorithms has been proved by several experiments considering both classical search and optimization problems.

The proliferation of information available on the World Wide Web and the new emerging technologies that have reduced the barriers in organizing and publishing documents, have made the support for navigation and personalization of Web sites an appealing and promising task for the Web community. One of the most challenging activities in the design of modern sites which goes beyond any particular domain consists of making the process of retrieving relevant documents easier. This paper proposes a new technique for Web navigation based on current algorithms used in recommendation systems. Our approach identifies really relevant documents adopting methodologies similar to those successfully used in current search engines. This approach has been effectively used for the implementation of a lightweight Web site personalization tool, that permits to navigate towards relevant Web pages regardless of the original Web site structure.

This paper presents a technique for the optimization of bound queries on disjunctive deductive databases. The optimization is based on the rewriting of the source program into an equivalent program which can be evaluated more efficiently. The proposed optimization reduces the amount of data needed to answer the query and, consequently, 1) reduces the complexity of computing a single model and, more importantly, 2) greatly reduces the number of models to be considered. Although, in this paper, we consider the application of the magic-set method, other rewriting techniques defined for special classes of queries can also be applied. To show the relevance of our technique, we have implemented a prototype of an optimizer. Several experiments have confirmed the value of the technique.

In this paper, we address the problem of managing inconsistent databases, i.e., databases violating integrity constraints. We propose a general logic framework for computing repairs and consistent answers over inconsistent databases. A repair for a possibly inconsistent database is a minimal set of insert and delete operations which makes the database consistent, whereas a consistent answer is a set of tuples derived from the database, satisfying all integrity constraints. In our framework, different types of rules defining general integrity constraints, repair constraints (i.e., rules defining conditions on the insertion or deletion of atoms), and prioritized constraints (i.e., rules defining priorities among updates and repairs) are considered. We propose a technique based on the rewriting of constraints into (prioritized) extended disjunctive rules with two different forms of negation (negation as failure and classical negation). The disjunctive program can be used for two different purposes: to compute "repairs" for the database and produce consistent answers, i.e., a maximal set of atoms which do not violate the constraints. We show that our technique is sound, complete (each preferred stable model defines a repair and each repair is derived from a preferred stable model), and more general than techniques previously proposed.

Informally presents the query language /spl Xscr//spl Gscr//spl Lscr/ (eXtensible Graphical Language). The main features of the language are described by means of two queries on a document named "bib.xml" (a document describing the bibliographic details of a book).

In this paper we present a graphical query language for XML. The language, based on a simple form of graph grammars, permits us to extract data and reorganize information in a new structure. As with most of the current query languages for XML, queries consist of two parts: one extracting a sub-graph and one constructing the output graph. The semantics of queries is given in terms of graph grammars. The use of graph grammars makes it possible to define, in a simple way, the structural properties of both the subgraph that has to be extracted and the graph that has to be constructed. By means of examples, we show the effectiveness and simplicity of our approach.

In the last few years, a lot of research has been devoted to developing new techniques for improving the recall and precision of current Web search engines. Few works deal with the interesting problem of identifying the communities to which pages belong. Most previous approaches tried to cluster data by means of spectral techniques or traditional hierarchical algorithms. The main problem with these techniques is that they ignore the fact that Web communities are social networks with distinctive statistical properties. We analyze Web communities on the basis of the evolution of an initial set of hubs and authoritative pages. The evolution law captures the behaviour of page authors with respect to the popularity of existing pages for topics of interest. Assuming such a model, we have found interesting properties of Web communities and have proposed a technique for computing relevant properties for specific topics. Several experiments have confirmed the validity of both the model and the identification method.

The World Wide Web (WWW) is becoming the most important system for delivering information. Search services on the WWW are becoming increasing popular among users because of the huge amount of data available and consequently it is difficult to retrieve and filter it. Several works have argued that traditional term-based search engines are not very useful since the resulting ranking depends on the precision of the user in expressing the query. However, usually, users are unclear about the information they need and so they do not give much thought to query formulation. Moreover, if the query pertains to topics which are abundant on the Web, search services become unusable because of the huge number of pages obtained. For instance, at the time of this work, AltaVista returned more than 18,000,000 pages in reply to the query asking for the documents related to the word "java".

In this paper, we consider the problem of answering queries using materialized views in the presence of negative goals. The solution is carried out by "inverting" views and deriving both positive and negative knowledge. In order to derive negative knowledge, we invert conjunctive views with negation into a set of (extended) views which may also have, in addition to negation-as-failure, a different form of negation called classical (or strong) negation. We also consider the case of disjunctive views and present a technique which permits us to infer both positive and negative knowledge. Furthermore, we extend previous techniques for inferring knowledge from views based on relations with functional dependencies. Finally, we present a prototype of a system developed at the University of Calabria.

In the design of algorithms, the greedy paradigm provides a powerful tool for solving efficiently classical computational problems, within the framework of procedural languages. However, expressing these algorithms within the declarative framework of logic-based languages has proven a difficult research challenge. In this paper, we extend the framework of Datalog-like languages to obtain simple declarative formulations for such problems, and propose effective implementation techniques to ensure computational complexities comparable to those of procedural formulations. These advances are achieved through the use of the choice construct, extended with preference annotations to effect the selection of alternative stable-models and nondeterministic fixpoints. We show that, with suitable storage structures, the differential fixpoint computation of our programs matches the complexity of procedural algorithms in classical search and optimization problems.

In this paper we propose the combined use of different methods to improve the data analysis process. This is obtained by combining inductive and deductive techniques. Inductive techniques are used for generating hypotheses from data whereas deductive techniques are used to derive knowledge and to verify hypotheses. In order to guide users in the the analysis process, we have developed a system which integrates deductive tools, data mining tools (such as classification algorithms and features selection algorithms), visualization tools and tools for the easy manipulation of data sets. The system developed is currently used in a large project whose aim is the integration of information sources containing data concerning the socio-economic aspects of Calabria and the analysis of the integrated data. Several experiments on socio-economic indicators of Calabrian cities have shown that the combined use of different techniques improves both the comprehensibility and the accuracy of models. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

The authors discuss data models and query languages for XML data. They propose a data model, called XDT, which takes care of the structural features of XML data. XDT represents XML data by means of labeled oriented graphs. With respect to other previously proposed models, XDT handles links definable in both XML and XLL. Queries are made through an SQL-like language which uses weighted path queries, i.e. path queries based on weighted regular languages and gives, as a result, a set of pairs (node/weight) where node is an 'element' of an XML document and weight gives information about the relevance of the node.

Dynamic programming is a general technique for solving optimization problems. It is based on the division of problems into simpler subproblems that can be computed separately. In this paper, we show that Datalog with aggregates and other nonmonotonic constructs can express classical dynamic programming optimization problems in a natural fashion, and then we discuss the important classes of queries and applications that benefit from these techniques.

The greedy paradigm of algorithm design is a well known tool used for efficiently solving many classical computational problems within the framework of procedural languages. However, it is very difficult to express these algorithms within the declarative framework of logic-based languages. In this paper, we extend the framework of Datalog-like languages to provide simple and declarative formulations of such problems, with computational complexities comparable to those of procedural formulations. This is achieved through the use of constructs, such as least and choice, that have semantics reducible to that of negative programs under stable model semantics. Therefore, we show that the formulation of greedy algorithms using these constructs lead to a syntactic class of programs, called stage-stratified programs, that are easily recognized at compile time. The fixpoint-based implementation of these recursive programs is very efficient and, combined with suitable storage structures, yields asymptotic complexities comparable to those obtained using procedural languages.

The design and a prototypical implementation of COMPLEX, which is a logic-based system extended with concepts from the object-oriented paradigm and is intended as a tool for the development of knowledge-based applications, are described. The system supports a logic language, called Complex-Datalog (C-Datalog), enhanced by semantic constructs to provide facility for data abstraction. Its implementation is based on a bottom-up computational model that guarantees a fully declarative style of programming. However, the user is also given the possibility of running a query using a top-down model of computation. Efficiency of execution is the result of the integration of different novel technologies for the compilation and the execution of queries.>

A novel approach is proposed for ezpressing and computing efficiently a large class of problems, including finding the shortest path in a graph, that were previously considered impervious to an efficient treatment in the declarative framework of logic-based languages. Our approach is based on the use of rain and max predicates having a first-order semantics defined using rules with negation in their bodies. We show that when cer- tain monotonictry conditions hold then (1) there ezists a totM well-founded model for these programs contain- ing negation, () this model can be computed efciently using a procedure called greedy flxpoint, and (3) the original program can be rewritten into a more efficient one by pushing rain and max predicates into recursion.