We address the context of Single-Audience Value-Based Abstract Argumentation Framework (AVAF), where the arguments are labeled with the social values that they promote and the activation/deactivation of the attacks depends on the audience profile (expressed as a set of preferences between the social values). Herein, we introduce a new notion of robustness for measuring the sensitivity of the outcome of the reasoning to the extent of changes in the audience profile. In particular, for a set of arguments S or a single argument a, we define the robustness degree of the status of S or a as the maximum number k* of deletions/insertions of preferences from/into the audience profile that are tolerable, in the sense that S remains an extension (or a non-extension) or a accepted (or unaccepted) after performing at most k* deletions/insertions. We introduce the decision problems related to the computation of the robustness degree and focus on thoroughly investigating their computational complexity.

Abstract Training deep neural networks (DNNs) is increasingly recognized as a major contributor to the energy footprint of Artificial Intelligence (AI). Existing dataset pruning (DP) and active learning (AL) techniques reduce training data volumes but often introduce costly computations that undermine their energy-saving potential. This paper introduces Play it Straight and its enhanced variant Re-Play it Straight , two adaptive training algorithms that combine random subset sampling with lightweight AL-inspired instance selection. The proposed framework achieves a better balance between accuracy and energy efficiency by incrementally fine-tuning models on small, informative subsets, while controlling computational overhead. Experiments on multiple benchmark datasets demonstrate substantial reductions in training energy compared to state-of-the-art DP and AL methods, with Re-Play it Straight consistently delivering superior performance. These results highlight the potential of our approach to support more sustainable deep learning practices, contributing to the broader goals of Green AI.

Abstract The escalating climate crisis demands urgent action to mitigate the environmental impact of energy-intensive technologies, including Artificial Intelligence (AI). Lowering AI’s environmental impact requires adopting energy-efficient approaches for training Deep Neural Networks (DNNs). One such approach is to use Dataset Pruning (DP) methods to reduce the number of training instances, and thus the total energy consumed. Numerous DP methods have been proposed in the literature (e.g., GraNd and Craig), with the ultimate aim of speeding up model training. On the other hand, Active Learning (AL) approaches, originally conceived to repeatedly select the best data to be labeled by a human expert (from a large collection of unlabeled data), can be exploited as well to train a model on a relatively small subset of (informative) examples. However, despite allowing for reducing the total amount of training data, most DP methods and pure AL-based schemes entail costly computations that may strongly limit their energy saving potential. In this work, we empirically study the effectiveness of DP and AL methods in curbing energy consumption in DNN training, and propose a novel approach to DNN learning, named Play it straight, which efficiently combines data selection methods and AL-like incremental training. Play it straight is shown to outperform traditional DP and AL approaches, achieving a better trade-off between accuracy and energy efficiency.

Active learning is focused on minimizing the effort required to obtain labeled data by iteratively choosing fresh data samples for training a machine learning model. One of the primary challenges in active learning involves the selection of the most informative instances for labeling by an annotation oracle at each iteration. A viable approach is to develop an active learning strategy that aligns with the performance of a meta-learning model. This strategy evaluates the quality of previously selected instances and subsequently trains a machine learning model to predict the quality of instances to be labeled in the current iteration. This paper introduces a novel approach to learning for active learning, wherein instances are chosen for labeling based on their potential to induce the most substantial change in the current classifier. We explore various strategies for assessing the significance of an instance, taking into account variations in the learning gradient of the classification model. Our approach can be applied to any classifier that can be trained using gradient descent optimization. Here, we present a formulation that leverages a deep neural network model, which has not been extensively explored in existing learning-to-active-learn methodologies. Through experimental validation, our approach demonstrates promising results, especially in scenarios where there are limited initially labeled instances, particularly when the number of labeled instances per class is extremely limited.

We introduce Incomplete Bipolar Argumentation Frameworks (iBAFs), the extension of Dung’s Abstract Argumentation Frameworks (AAFs) allowing the simultaneous presence of supports (borrowed from BAFs – Bipolar AAFs) and of uncertain elements of the argumentation graph (borrowed from iAAFs – incomplete AAFs). We investigate the computational complexity of verification problem (under the possible perspective) and the acceptance problem, by studying its sensitivity to the semantics of supports and the semantics of extensions. On the one hand, we show that adding supports on top of incompleteness does not affect the complexity of the acceptance. On the other hand, surprisingly, we show that the joint use of bipolarity and incompleteness has a deep impact on the complexity of the verification: for the semantics under which the verification over AAFs is polynomial-time solvable, although moving from AAFs to BAFs or to iAAFs does not change the complexity, the complexity of the verification over iBAFs may increase up to NP-complete.

We propose a new paradigm for reasoning over abstract argumentation frameworks where the “who said what” relation, associating each argument with the set of agents who claimed it, is taken into account, along with possible information on the trustworthiness of the agents. Specifically, we extend the traditional reasoning based on the classical verification and acceptance problems and introduce a reasoning paradigm investigating how the “robustness” of a set of arguments S (in terms of being an extension or not) or of an argument a (in terms of being accepted or not) can change if what has been claimed by some agents is ignored (as if these agents were removed from the dispute modeled by the argumentation framework). In this regard, we address the problems of searching the “minimum extent” of the removal of agents that makes a set S an extension or an argument a accepted. Compared with the case where only the “yes/no” answer of the traditional verification and acceptance problems are available, the knowledge of such a minimum provides the analyst with further insights allowing them to better judge the robustness of S and a. We consider the above minimization problems in two variants, where the agents are associated with a measure of their trustworthiness or not and provide a thorough characterization of their complexities.

A major challenge in active learning is to select the most informative instances to be labeled by an annotation oracle at each step. In this respect, one effective paradigm is to learn the active learning strategy that best suits the performance of a meta-learning model. This strategy first measures the quality of the instances selected in the previous steps and then trains a machine learning model that is used to predict the quality of instances to be labeled in the current step.In this paper, we propose a new approach of learning-to-active-learn that selects the instances to be labeled as the ones producing the maximum change to the current classifier. Our key idea is to select such instances according to their importance reflecting variations in the learning gradient of the classification model. Our approach can be instantiated with any classifier trainable via gradient descent optimization, and here we provide a formulation based on a deep neural network model, which has not deeply been investigated in existing learning-to-active-learn approaches. The experimental validation of our approach has shown promising results in scenarios characterized by relatively few initially labeled instances.

In the context of probabilistic AAFs, we intro- duce AAFs with marginal probabilities (mAAFs) requiring only marginal probabilities of argu- ments/attacks to be specified and not relying on the independence assumption. Reasoning over mAAFs requires taking into account multiple probability distributions over the possible worlds, so that the probability of extensions is not determined by a unique value, but by an interval. We focus on the problems of computing the max and min probabil- ities of extensions over mAAFs under Dung’s se- mantics, characterize their complexity, and provide closed formulas for polynomial cases.

We introduce "argument-incomplete Abstract Argumentation Frameworks with dependencies", that extend the traditional abstract argumentation reasoning to the case where some arguments are uncertain and correlated through logical dependencies (such as mutual exclusion, implication, etc.). We characterize the complexities of the problems DSAT of deciding the satisfiability of the dependencies and PDVER of verifying extensions, and show how they depend on the forms of dependencies and, for PDVER, also on the semantics of the extensions.

Attack-Incomplete Abstract Argumentation Frameworks (att- iAAFs) are a popular extension of AAFs where attacks are marked as uncertain when they are not unanimously per- ceived by different agents reasoning on the same arguments. We here extend att-iAAFs with the possibility of specifying correlations involving the uncertain attacks. This feature sup- ports a unified and more precise representation of the differ- ent scenarios for the argumentation, where, for instance, it can be stated that an attack α has to be considered only if an attack β is considered, or that α and β are alternative, and so on. In order to provide a user-friendly language for spec- ifying the correlations, we allow the argumentation analyst to express them in terms of a set of elementary dependen- cies, using common logical operators (namely, OR , NAND , CHOICE , ⇒). In this context, we focus on the problem of verifying extensions under the possible perspective, and study the sensitivity of its computational complexity to the forms of correlations expressed and the semantics of the extensions.

We revisit the notion of i-extension, i.e., the adaption of the fundamental notion of extension to the case of incomplete Abstract Argumentation Frameworks. We show that the definition of i-extension raises some concerns in the "possible" variant, e.g., it allows even conflicting arguments to be collectively considered as members of an (i-)extension. Thus, we introduce the alternative notion of i*-extension overcoming the highlighted problems, and provide a thorough complexity characterization of the corresponding verification problem. Interestingly, we show that the revisitation not only has beneficial effects for the semantics, but also for the complexity: under various semantics, the verification problem under the possible perspective moves from NP-complete to P.

Digital content piracy is nowadays really burden-some both for companies and professionals. To overcome this problem, digital data producers usually protect their documents from illegal distributions by leveraging digital fingerprinting techniques for marking each copy of their documents in order to uniquely identify it. Unfortunately, in the case that multiple malicious users jointly collaborate for illegally sharing a document copy, they may forge the embedded fingerprint by simply comparing their copies and modifying the fingerprint's bits that differ in their copies. In [1] an optimal fingerprinting schema has been defined for accusing a guilty user with very high probability under the assumption that the fingerprinting code is sufficiently long. To remove this assumption, several joint-decoding techniques have been recently proposed [2], [3]. In this work, we perform a deep experimental analysis of the Metropolis-Hastings based joint-decoding approach defined in [3], with the aim of assessing the sensitivity to various parameters of the model, thus making it usable in practical contexts.

The complexity of the probabilistic counterparts of the verification and acceptance problems is investigated over probabilistic Abstract Argumentation Frameworks (prAAFs), in a setting more general than the literature, where the complexity has been characterized only under independence between arguments/defeats. The complexity of these problems is shown to depend on the semantics of the extensions, the way of encoding the prAAF, and the correlations between arguments/defeats. In this regard, in order to study the impact of different correlations between arguments/defeats on the complexity, a new form of prAAF is introduced, called gen. It is based on the well-known paradigm of world-set sets, and it allows the correlations to be easily distinguishable.

Probabilistic Bipolar Abstract Argumentation Frameworks (prBAFs), combining the possibility of specifying supports between arguments with a probabilistic modeling of the uncertainty, are considered, and the complexity of the fundamentalproblem of computing extensions' probabilities is addressed.The most popular semantics of supports and extensions are considered, as well as different paradigms for defining the probabilistic encoding of the uncertainty.Interestingly, the presence of supports, which does not alter the complexity of verifying extensions in the deterministic case, is shown to introduce a new source of complexity in some probabilistic settings, for which tractable cases are also identified.

Social Networks analysis is driving both research and industrial effort as the outcomes of this activity are relevant both from a merely theoretical point of view and for the potential market advantages they can provide to companies. Indeed, there is a growing number of applications that call for user (social) intervention with the aim of helping each other in solving complex tasks or rating other users work. The topic is even more intriguing when a reward is given to users that properly complete their tasks. In this paper, we focus on the analysis of user mutual rankings in a collaborative network where they contribute to the solution of complex tasks. We leverage Exponential Random Graph to model user interaction rankings and we evaluate our approach in a real life scenario.

research-article Share on WFinger: a joint-decoder for very short Tardos fingerprinting codes Authors: Bettina Fazzinga ICAR-CNR, Rende (CS), Italy ICAR-CNR, Rende (CS), ItalyView Profile , Sergio Flesca DIMES, University of Calabria, Rende (CS), Italy DIMES, University of Calabria, Rende (CS), ItalyView Profile , Filippo Furfaro DIMES, University of Calabria, Rende (CS), Italy DIMES, University of Calabria, Rende (CS), ItalyView Profile , Elio Masciari ICAR-CNR, Rende (CS), Italy ICAR-CNR, Rende (CS), ItalyView Profile Authors Info & Claims IDEAS '17: Proceedings of the 21st International Database Engineering & Applications SymposiumJuly 2017 Pages 176–183https://doi.org/10.1145/3105831.3105860Published:12 July 2017Publication History 1citation36DownloadsMetricsTotal Citations1Total Downloads36Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Nowadays, many applications call for collaborative solutions in order to accomplish complex projects requiring huge amounts of computing resources, e.g., physical science simulation. Many approaches have been proposed in order to design a task partitioning strategy able to assign pieces of execution to the appropriate workers. In this paper, we describe our peer to peer solution for solving complex works by using the idling computational resources of users connected to our network. More in detail, we designed a framework that allows users to share their CPU and memory in a secure and efficient way. By doing this, users help each others by asking the network available computational resources when they face high computing demanding tasks. Differently from many proposal available for volunteer computing, users providing their resources are rewarded with tangible credits, i.e., they can redeem their credits by asking computation power to solve their own task or/and they can redeem them earning coins. As we do not require to power additional resources for solving tasks (we better exploit unused resources already powered instead).

We characterize the complexity of the problem of computing the probabilities of the extensions in probabilistic abstract argumentation. We consider all the most popular semantics of extensions (admissible, stable, preferred, complete, grounded, ideal-set, ideal and semi-stable) and different forms of correlations that can be defined between arguments and defeats. We show that the complexity of the problem ranges from FP to FP#P-complete, with FP||NP-complete cases, depending on the semantics of the extensions and the imposed correlations.

Log analysis and querying recently received a renewed interest from the research community, as the effective understanding of process behavior is crucial for improving business process management. Indeed, currently available log querying tools are not completely satisfactory, especially from the viewpoint of easiness of use. As a matter of fact, there is no framework which meets the requirements of easiness of use, flexibility and efficiency of query evaluation. In this paper, we propose a framework for graphical querying of (process) log data that makes the log analysis task quite easy and efficient, adopting a very general model of process log data which guarantees a high level of flexibility. We implemented our framework by using a flexible storage architecture and a user-friendly data analysis interface, based on an intuitive and yet expressive graph-based query language. Experiments performed on real data confirm the validity of the approach.

A probabilistic framework for cleaning the data collected by Radio-Frequency IDentification (RFID) tracking systems is introduced. What has to be cleaned is the set of trajectories that are the possible interpretations of the readings: a trajectory in this set is a sequence whose generic element is a location covered by the reader(s) that made the detection at the corresponding time point. The cleaning is guided by integrity constraints and consists of discarding the inconsistent trajectories and assigning to the others a suitable probability of being the actual one. The probabilities are evaluated by adopting probabilistic conditioning that logically consists of the following steps. First, the trajectories are assigned a priori probabilities that rely on the independence assumption between the time points. Then, these probabilities are revised according to the spatio-temporal correlations encoded by the constraints. This is done by conditioning the a priori probability of each trajectory to the event that the constraints are satisfied: this means taking the ratio of this a priori probability to the sum of the a priori probabilities of all the consistent trajectories. Instead of performing these steps by materializing all the trajectories and their a priori probabilities (which is infeasible, owing to the typically huge number of trajectories), our approach exploits a data structure called conditioned trajectory graph (ct-graph) that compactly represents the trajectories and their conditioned probabilities, and an algorithm for efficiently constructing the ct-graph, which progressively builds it while avoiding the construction of components encoding inconsistent trajectories.

The increasing availability of large process log repositories calls for efficient solutions for their analysis. In this regard, a novel specialized compression technique for process logs is proposed, that builds a synopsis supporting a fast estimation of aggregate queries, which are of crucial importance in exploratory and high-level analysis tasks. The synopsis is constructed by progressively merging the original log-tuples, which represent single activity executions within the process instances, into aggregate tuples, summarizing sets of activity executions. The compression strategy is guided by a heuristic aiming at limiting the loss of information caused by summarization, while guaranteeing that no information is lost on the set of activities performed within the process instances and on the order among their executions. The selection conditions in an aggregate query are specified in terms of a graph pattern, that allows precedence relationships over activity executions to be expressed, along with conditions on their starting times, durations, and executors. The efficacy of the compression technique, in terms of capability of reducing the size of the log and of accuracy of the estimates retrieved from the synopsis, has been experimentally validated.

Probabilistic abstract argumentation combines Dung’s abstract argumentation framework with probability theory in order to model uncertainty in argumentation. In this setting, we address the fundamental problem of computing the probability that a set of arguments is anextensionaccording to a given semantics. We focus on the most popular semantics (i.e.,admissible,stable,complete,grounded,preferred,ideal-set,ideal,stage, andsemistable) and show the following dichotomy result: computing the probability that a set of arguments is an extension is eitherFPorFP#P-complete depending on the semantics adopted. Our polynomial-time results are particularly interesting, as they hold for some semantics for which no polynomial-time technique was known so far.

A probabilistic framework is introduced for reducing the inherent uncertainty of trajectory data collected for RFID-monitored ob-jects. The framework represents the position of an object at each instant as a random variable over the set of possible locations. The probability density function of this random variable is initialized according to an a-priori probability distribution, and then revised by conditioning it w.r.t. the event that integrity constraints are sat-isfied. In particular, integrity constraints implied by the structure of the map of locations and the motility characteristics (such as the maximum speed) of the monitored objects are exploited (namely, direct unreachability, latency and minimum traveling time constraints). The efficiency and effectiveness of the proposed approach are as-sessed experimentally on synthetic data. 1.

An offline cleaning technique is proposed for translating the readings generated by RFID-tracked moving objects into positions over a map. It consists in a grid-based two-way filtering scheme embedding a sampling strategy for addressing missing detections. The readings are first processed in time order: at each time point t, the positions (i.e., cells of a grid assumed over the map) compatible with the reading at t are filtered according to their reachability from the positions that survived the filtering for the previous time point. Then, the positions that survived the first filtering are re-filtered, applying the same scheme in inverse order. As the two phases proceed, a probability is progressively evaluated for each candidate position at each time point t: at the end, this probability assembles the three probabilities of being the actual position given the past and future positions, and given the reading at t. A sampling procedure is employed at certain steps of the first filtering phase to intelligently reduce the number of cells to be considered as candidate positions at the next steps, as their number can grow dramatically in the presence of consecutive missing detections. The proposed approach is experimentally validated and shown to be efficient and effective in accomplishing its task.

RFID-based systems for object tracking and supply chain management have been emerging since the RFID technology proved effective in monitoring movements of objects. The monitoring activity typically results in huge numbers of readings, thus making the problem of efficiently retrieving aggregate information from the collected data a challenging issue. In fact, tackling this problem is of crucial importance, as fast answers to aggregate queries are often mandatory to support the decision making process. In this regard, a compression technique for RFID data is proposed, and used as the core of a system supporting the efficient estimation of aggregate queries. Specifically, this technique aims at constructing a lossy synopsis of the data over which aggregate queries can be estimated, without accessing the original data. Owing to the lossy nature of the compression, query estimates are approximate, and are returned along with intervals that are guaranteed to contain the exact query answers. The effectiveness of the proposed approach has been experimentally validated, showing a remarkable trade-off between the efficiency and the accuracy of the query estimation.

Query relaxation is the process of weakening a query to a more general one, and it is frequently employed to support approximate query answering. In this paper, rewriting systems for a wide fragment of XPath are investigated, which accomplish query relaxation through the application of simple rewriting rules transforming navigational axes and node tests into relaxed ones. Specifically, a general yet simple form of rewriting rules is considered, which subsumes the forms adopted in several rewriting systems for approximate XPath query answering. The expressiveness of rewriting systems based on this form of rules is characterized in terms of their capability of transforming a query into every more general formulation. It is shown that traditional rewriting systems are not only incomplete w.r.t. containment, but also w.r.t. the stricter form known as containment by homomorphism. This limitation is overcome by defining a set R* of rewriting rules which are still of the same simple form of traditional ones, but are expressive enough to catch at least containment by homomorphism. Then, an algorithm is proposed which exploits R* to provide approximate answers of queries along with a measure of their approximation degree.

The PDF format represents the de facto standard for print-oriented documents. In this paper, we address the problem of wrapping PDF documents, which raises new challenges in several contexts of text data management. Our proposal is based on a novel bottom-up hierarchical wrapping approach that exploits fuzzy logic to handle the “uncertainty” which is intrinsic to the structure and presentation of PDF documents. A PDF wrapper is defined by specifying a set of group type definitions that impose a target structure to groups of tokens containing the required information. Constraints on token groupings are formulated as fuzzy conditions, which are defined on spatial and content predicates of tokens. We define a formal semantics for PDF wrappers and propose an algorithm for wrapper evaluation working in polynomial time with respect to the size of a PDF document. The proposed approach has been implemented in a wrapper generation system that offers visual capabilities to assist the designer in specifying and evaluating a PDF wrapper. Experimental results have shown good accuracy and applicability of our system to PDF documents of various domains.

The problem of defining suitable rewriting mechanisms for XML query languages to support approximate query answering has received a great deal of attention in the last few years, owing to its practical impact in several scenarios. For instance, in the typical scenario of distributed XML data without a shared data scheme, accomplishing the extraction of the information of interest often requires queries to be rewritten into relaxed ones, in order to adapt them to the schemes adopted in the different sources.In this paper, rewriting systems for a wide fragment of XPath (which is the core of several languages for manipulating XML data) are investigated, and a general form of rewriting rules (namely, generalization rules) is considered, which subsumes the forms adopted in the most well-known rewriting systems. Specifically, the expressiveness of rewriting systems based on this form of rules is characterized: on the one hand, it is shown that rewriting systems based on generalization rules are incomplete w.r.t. containment (thus, traditional rewriting mechanisms do not suffice to rewrite a query into any more general one). On the other hand, it is also shown that the expressiveness of state-of-the-art rewriting systems can be improved by employing rewriting primitives as simple as those traditionally used, which enable any query to be relaxed into every more general one related to it via homomorphism.

The problem of extracting consistent information from relational databases violating integrity constraints on numerical data is addressed. In particular, aggregate constraints defined as linear inequalities on aggregate-sum queries on input data are considered. The notion of repair as consistent set of updates at attribute-value level is exploited, and the characterization of several data-complexity issues related to repairing data and computing consistent query answers is provided. Moreover, a method for computing “reasonable” repairs of inconsistent numerical databases is provided, for a restricted but expressive class of aggregate constraints. Several experiments are presented which assess the effectiveness of the proposed approach in real-life application scenarios.

Radio Frequency Identification (RFID) applications are emerging as key components in object tracking and supply chain management systems since in the next future almost every major retailer will use RFID systems to track the shipment of products from suppliers to warehouses. Due to the streaming nature of RFID readings, large amounts of data are generated by these devices at high production rates. This phenomenon is even more relevant since RFIDs are so cheap that every individual item can be tagged thus leaving a "trail" of data as it moves across different locations. This scenario raises new challenges in effectively and efficiently exploiting such large amounts of data. In this paper we address the problem of compressing RFID data in order to enable devices with limited amount of available memory (such as PDAs) to issue queries on RFID warehouses. In particular, we designed a lossy strategy for collapsing tuples carrying information about items being delivered at different location of the supply chain.

We propose a framework for querying heterogeneous XML data sources. The framework ensures high autonomy to participating sources as it does not rely on a global schema or on semantic mappings between schemas. The basic intuition is that of extending traditional approaches for approximate query evaluation, by providing techniques for combining partial answers coming from different sources, possibly on the basis of limited knowledge about the local schemas (i.e., key constraints). We define a query language and its associated semantics, that allows us to collect as much information as possible from several heterogeneous XML sources. We provide algorithms for query evaluation and characterize the complexity of the query language. Finally, we validate the approach in a medical application scenario.

XPath expressions define navigational queries on XML data and are issued on XML documents to select sets of element nodes. Due to the wide use of XPath, which is embedded into several languages for querying and manipulating XML data, the problem of efficiently answering XPath queries has received increasing attention from the research community. As the efficiency of computing the answer of an XPath query depends on its size, replacing XPath expressions with equivalent ones having the smallest size is a crucial issue in this direction. This article investigates the minimization problem for a wide fragment of XPath (namely X P [✶] ), where the use of the most common operators (child, descendant, wildcard and branching) is allowed with some syntactic restrictions. The examined fragment consists of expressions which have not been specifically studied in the relational setting before: neither are they mere conjunctive queries (as the combination of “//” and “*” enables an implicit form of disjunction to be expressed) nor do they coincide with disjunctive ones (as the latter are more expressive). Three main contributions are provided. The “global minimality” property is shown to hold: the minimization of a given XPath expression can be accomplished by removing pieces of the expression, without having to re-formulate it (as for “general” disjunctive queries). Then, the complexity of the minimization problem is characterized, showing that it is the same as the containment problem. Finally, specific forms of XPath expressions are identified, which can be minimized in polynomial time.

Because of the widespread diffusion of semistructured data in XML format, much research effort is currently devoted to support the storage and retrieval of large collections of such documents. XML documents can be compared as to their structural similarity, in order to group them into clusters so that different storage, retrieval, and processing techniques can be effectively exploited. In this scenario, an efficient and effective similarity function is the key of a successful data management process. We present an approach for detecting structural similarity between XML documents which significantly differs from standard methods based on graph-matching algorithms, and allows a significant reduction of the required computation costs. Our proposal roughly consists of linearizing the structure of each XML document, by representing it as a numerical sequence and, then, comparing such sequences through the analysis of their frequencies. First, some basic strategies for encoding a document are proposed, which can focus on diverse structural facets. Moreover, the theory of discrete Fourier transform is exploited to effectively and efficiently compare the encoded documents (i.e., signals) in the domain of frequencies. Experimental results reveal the effectiveness of the approach, also in comparison with standard methods.

DATA

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.

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.

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 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.

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.