Smart tags are compact electronic devices affixed to or embedded into objects to facilitate identification, monitoring, and data exchange. Consequently, secure authentication of these tags is a crucial issue, as objects must reliably verify their identity before sharing sensitive information with other entities. The application of Physical Unclonable Functions (PUF) as a device's “digital fingerprint” has attracted significant attention, yet existing PUF-based authentication methods exhibit security vulnerabilities, either due to the authentication protocol itself or the limited reliability of the PUF technology used. Moreover, there has been a considerable focus on the software aspect, often overlooking the critical role of hardware design, which can become a target for attacks aimed at compromising the device's identity or act as a hindrance in the manufacturing process. In light of these points, this paper introduces an identification tag architecture that leverages PUF technology, focusing on authentication. This architecture features a straightforward but efficient authentication protocol, underpinned by a new and highly stable PUF model. The overall architecture encompasses particular hardware implementation aspects that significantly simplify the tag's enrollment phase and minimize vulnerabilities to attacks. The paper also describes a prototype of this identification tag and provide detailed insights into its application.

Counterfeiting represents one of the most widespread phenomena at a global level that indiscriminately affects all product sectors, from fashion to food, from medicines to digital media. The fight against counterfeiting remains a significant challenge for industries. Most of the current supply chains rely on centralized authorities or intermediaries that are not sufficient robust to guarantee anti-counterfeiting and traceability of goods.

The data posting framework introduced in [8] adapts the well-known Data Exchange techniques to the new Big Data management and analysis challenges that can be found in real world scenarios. Although it is expressive enough, it requires the ability of using count constraints and may be difficult for a non expert user. Moreover, the data posting problem is NP-complete under the data complexity in the general case, then the use of the non-deterministic variables is performed. Indeed, identifying the conditions that guarantee polynomial-time execution in the presence of non-deterministic choices is very important for practical purposes. In this paper, we present a simplified version of data posting framework, based on the use of the smart mapping rules, that integrate the simple mapping description with some parameters, avoiding the complex specifications with count constraints. We show that the data posting problem in the new setting is NP- complete and identify the conditions under which this problem becomes polynomial even in the presence of non-deterministic choices.

CalcuList (Calculator with List manipulation), is an educational language for teaching functional programming extended with some imperative and side-effect features, which are enabled under explicit request by the programmer. In addition to strings and lists, the language natively supports json objects and may be effectively used to implement generic MapReduce recursive procedures to manipulate json lists. MapReduce is a popular model in distributed computing that underpins many NoSQL systems and a json list can be thought of as a dataset of a document NoSQL datastore. It turns out that CalcuList can be used as a tool for teaching advanced query algorithms for document datastores such as MongoDB and CouchDB.

Count constraint is a data dependency that requires the results of given count operations on a relation to be within a certain range. By means of count constraints a new decisional problem, called the Inverse OLAP, has been recently introduced: given a flat fact table, does there exist an instance satisfying a set of given count constraints? This paper focuses on a special case of Inverse OLAP, called Inverse Tree-OLAP, for which the flat fact table key is modeled by a Dimensional Fact Model (DFM) with a tree structure. The count constraints define aggregation patterns to be respected by both the many-to-many relationship among the basic dimensions and the one-to-many relationships within dimension hierarchies. A count constraint is required to have a particular structure so that the problem of handling fact table projections with duplicates is avoided. The simplified structure enables the invention of an effective method for its solution that consists of three main steps: (1) using some of the count constraints to extract a subproblem that is formulated as a known data mining problem (inverse frequent itemset mining), (2) solving the subproblem using a recent method that has been shown to be effective in practical situations also for large size instances and (3) enforcing the remaining count constraints on the solution returned by step 2 using a system of linear equations. The overall proposed approach can be effectively used to generate OLAP cubes for benchmarking that reflect patterns of real datasets.

Big Data rise made traditional data management techniques inadequate in many real life scenarios. In particular, the availability of huge amounts of data pertaining to user suggestions and searches calls for advanced analysis strategies in order to profitably leverage these data. Furthermore, heterogeneity and high speed of this data require suitable data storage and management tools to be designed from scratch. In this paper, we describe our proposal for analysing the way user searches and suggestions influence their social environment in order to quickly identify users able to spread their influence across the network. It is worth noting that, gathering information about user preferences is crucial in several scenarios like viral marketing, tourism promotion and food education.

Summary Cybersecurity compliance analysis is the process of assessing whether the behavior of an IT system or application conforms to the cybersecurity rules and regulations in force. This assessment can be offered as a service by exploiting available cloud technologies, and, indeed, it is one of the services classified by the Cloud Security Alliance (CSA) as part of the security information and event management (SIEM) category of the SecaaS (security as a service) domain. The definition and implementation of this typology of cloud services are challenging activities due to the complexity of both the reference business domain and the compliance analysis services to be provided themselves. The paper exploits a recently proposed requirements methodology, called GOReM (goal‐oriented requirements methodology), to support the conceptualization and subsequent implementation of cybersecurity compliance analysis services. In particular, two different application scenarios regarding compliance analysis of an existing or under development IT system/application are presented and discussed. In both the scenarios, GOReM allows to grasp and understand the many and complex issues to address for providing secure cloud services to worldwide customers, also due to the numerous, different and ever changing legal aspects, which have to be taken into account by service providers.

In the Risk Analysis domain an increasing interest has been gaining by the System Risk Analysis that aims at investigating the risk deriving by the interdependence of the system under consideration by other systems and, in general, by the interactions among them. Indeed, an adverse event occurring in a certain system can cause negative effects on the other interconnected systems and compromise their operation. An effective analysis of the Systemic Risk requires suitable methods and techniques able to handle the high level of complexity typical of Systems and Systems characterized by several interconnected, distributed, autonomous and changing components. In this context, the paper proposes a method for Systemic Risk Analysis that combines a Goal-Oriented Methodology for Requirement Modeling (GOReM) with a Model-Based method for System Dependability Analysis (RAMSoS). Such combination enables the modeling and the evaluation of Systemic Risk scenarios by using agent-based simulations and the complementary quantitative evaluation of performance indices through Bayesian Networks. A concrete exploitation of the proposed approach to Systemic Risk Analysis in the cyber-security domain is also presented1.

Due to the emerging Big Data paradigm, driven by the increasing availability of intelligent services easily accessible by a large number of users (e.g., social networks), traditional data management techniques are inadequate in many real-life scenarios. In particular, the availability of huge amounts of data pertaining to user social interactions, user preferences, and opinions calls for advanced analysis strategies to understand potentially interesting social dynamics. Furthermore, heterogeneity and high speed of user-generated data require suitable data storage and management tools to be designed from scratch. This article presents a framework tailored for analyzing user interactions with intelligent systems while seeking some domain-specific information (e.g., choosing a good restaurant in a visited area). The framework enhances a user's quest for information by exploiting previous knowledge about their social environment, the extent of influence the users are potentially subject to, and the influence they may exert on other users. User influence spread across the network is dynamically computed as well to improve user search strategy by providing specific suggestions, represented as tailored faceted features. Such features are the result of data exchange activity (called data posting) that enriches information sources with additional background information and knowledge derived from experiences and behavioral properties of domain experts and users. The approach is tested in an important application scenario such as tourist recommendation, but it can be profitably exploited in several other contexts, for example, viral marketing and food education.

We propose a hypergraph-based framework for modeling and detecting malevolent activities. The proposed model supports the specification of order-independent sets of action symbols along with temporal and cardinality constraints on the execution of actions. We study and characterize the problems of consistency checking, equivalence, and minimality of hypergraph-based models. In addition, we define and characterize the general activity detection problem, that amounts to finding all subsequences that represent a malevolent activity in a sequence of logged actions. Since the problem is intractable, we also develop an index data structure that allows the security expert to efficiently extract occurrences of activities of interest.

The development of high quality complex software systems and quick time-to-market with full customer satisfaction often appear as two competing forces. Many industry efforts have been directed towards agile methodologies completed with the DevOps approach, whereas traditional requirements engineering with much documentation, is considered surpassed. The aim is to obtain a longer life software because it suddenly responds to the customers changing requirements from which it receives continuous input. This might create a serious cost implication and a real risk to lose system requirements control. In this paper, we propose a framework able to govern the complexity of the system requirements and to allow the embedding, occasionally, of technological innovations into the overall system. ResDevOps joins the value of the agile world with DevOps, with the additional value deriving from an unceasing parallel innovation management process, which we call ResDevs. ResDevOps includes a continuous research and innovation process, which provides an asynchronous, additional input to the agile process inside a chain of concurrent engineering collaboration. This is a suitable trade-off to maintain modern IT Systems live for a longer time, with many consequent advantages for both total investment and system quality. The practical use of the ResDevOps approach is shown by means of a case study.

Due to the emerging Big Data paradigm traditional data management techniques result inadequate in many real life scenarios. In particular, OLAP techniques require substantial changes in order to offer useful analysis due to huge amount of data to be analyzed and their velocity and variety. In this paper, we describe an approach for dynamic Big Data searching that based on data collected by a suitable storage system, enriches data in order to guide users through data exploration in an efficient and effective way.

The pervasive diffusion of new generation devices like smart phones and tablets along with the widespread use of social networks causes the generation of massive data flows containing heterogeneous information generated at different rates and having different formats. These data are referred as \emph{Big Data} and require new storage and analysis approaches to be investigated for managing them. In this paper we will describe a system for dealing with massive tourism flows that we exploited for the analysis of tourist behavior in Italy. We defined a framework that exploits a NoSQL approach for data management and map reduce for improving the analysis of the data gathered from different sources

Recently, a great deal of interest for Big Data has risen, mainly driven from a widespread number of research problems strongly related to real-life applications and systems, such as representing, modeling, processing, querying and mining massive, distributed, large-scale repositories (mostly being of unstructured nature). Inspired by this main trend, in this paper we discuss three important aspects of Big Data research, namely OLAP over Big Data, Big Data Posting, and Privacy of Big Data. We also depict future research directions, hence implicitly defining a research agenda aiming at leading future challenges in this research field.

SUMMARY Aggregate queries are useful tools in the context of sensor network‐based systems as they retrieve knowledge from huge amounts of summarized readings to be exploited for knowledge discovery purposes. Actually, data representation and query models are problematic issues for managing sensor network data, because streams produced by sensors are theoretically unbounded. In this paper, we present a Grid framework, called SensorGrid, on the basis of data compression and approximation paradigms, which allows us to provide approximate answers to aggregate queries on summarized sensor network data. These queries are the basis for achieving Online Analytical Processing (OLAP) over sensor network readings in Data Grid environments, with both effectiveness and efficiency. We also present our experience in the context of a real‐life system focused on the management of environmental sensor network data. Another contribution of our research is represented by the extensive experimental evaluation and analysis of SensorGrid, which, in more details, focuses on two main classes of aggregate range queries over sensor readings, namely, (i) the window queries, which apply an SQL aggregation operator over a fixed window over the reading stream produced by the sensor network, and (ii) the continuous queries, which instead consider a ‘moving’ window and produce as output a stream of answers. Both classes of queries are extremely useful to extract summarized knowledge to be exploited by OLAP‐like analysis tools over sensor network data. The experimental results, conducted on both synthetic and real‐life data sets, clearly confirm the benefits deriving from embedding data compression and approximation paradigms into Grid‐based sensor network data‐intensive management systems.Copyright © 2013 John Wiley & Sons, Ltd.

Inverse frequent set mining (IFM) is the problem of computing a transaction database D satisfying given support constraints for some itemsets, which are typically the frequent ones. This article proposes a new formulation of IFM, called IFM I (IFM with infrequency constraints ), where the itemsets that are not listed as frequent are constrained to be infrequent; that is, they must have a support less than or equal to a specified unique threshold. An instance of IFM I can be seen as an instance of the original IFM by making explicit the infrequency constraints for the minimal infrequent itemsets, corresponding to the so-called negative generator border defined in the literature. The complexity increase from PSPACE (complexity of IFM) to NEXP (complexity of IFM I ) is caused by the cardinality of the negative generator border, which can be exponential in the original input size. Therefore, the article introduces a specific problem parameter κ that computes an upper bound to this cardinality using a hypergraph interpretation for which minimal infrequent itemsets correspond to minimal transversals. By fixing a constant k , the article formulates a k -bounded definition of the problem, called k -IFM I , that collects all instances for which the value of the parameter κ is less than or equal to k —its complexity is in PSPACE as for IFM. The bounded problem is encoded as an integer linear program with a large number of variables (actually exponential w.r.t. the number of constraints), which is thereafter approximated by relaxing integer constraints—the decision problem of solving the linear program is proven to be in NP. In order to solve the linear program, a column generation technique is used that is a variation of the simplex method designed to solve large-scale linear programs, in particular with a huge number of variables. The method at each step requires the solution of an auxiliary integer linear program, which is proven to be NP hard in this case and for which a greedy heuristic is presented. The resulting overall column generation solution algorithm enjoys very good scaling as evidenced by the intensive experimentation, thereby paving the way for its application in real-life scenarios.

In this paper, we present a complete demonstration of Hand-OLAP, a Java-based distributed system that relies on intelligent data cube compression techniques for effectively and efficiently supporting OLAP in mobile environments. Hand-OLAP is based on an innovative systematic technique according to which first a two-dimensional OLAP view of interest is extracted from the target multidimensional data cube via the so-called OLAP dimension flattening process, and then this view is compressed by means of a meaningful semantics-based data cube compression approach. The compressed two-dimensional view is finally delivered to mobile devices, and used to support interactive OLAP exploration and querying tasks in an off-line manner.

In this paper we propose an innovative framework based on flexible sampling-based data cube compression techniques for computing privacy preserving OLAP aggregations on data cubes while allowing approximate answers to be efficiently evaluated over such aggregations. In our proposal, this scenario is accomplished by means of the so-called accuracy/privacy contract, which determines how OLAP aggregations must be accessed throughout balancing accuracy of approximate answers and privacy of sensitive ranges of multidimensional data.

The inverse frequent set mining problem is the problem of computing a database on which a given collection of itemsets must emerge to be frequent. Earlier studies focused on investigating computational and approximability properties of this problem. In this paper, we face it under the pragmatic perspective of defining heuristic solution approaches that are effective and scalable in real scenarios. In particular, a general formulation of the problem is considered where minimum and maximum support constraints can be defined on each itemset, and where no bound is given beforehand on the size of the resulting output database. Within this setting, an algorithm is proposed that always satisfies the maximum support constraints, but which treats minimum support constraints as soft ones that are enforced as long as possible. A thorough experimentation evidences that minimum support constraints are hardly violated in practice, and that such negligible degradation in accuracy (which is unavoidable due to the theoretical intractability of the problem) is compensated by very good scaling performances.

In this paper, we present further research achievements due to Hand-OLAP, a Java-based distributed system that relies on semantics-based intelligent data cube compression techniques, and effectively and efficiently supports OLAP in mobile environments. Hand-OLAP is based on a systematic approach according to which first a two-dimensional OLAP view of interest is extracted from the target multidimensional data cube via the so-called OLAP dimension flattening process, and then this view is compressed by means of a meaningful semantics-based data cube compression approach. The compressed two-dimensional view is finally delivered to mobile devices, and used to interactive OLAP exploration and querying tasks in an off-line manner.

This paper introduces a novel data cube compression technique for data cubes whose main idea consists in exploiting the knowledge kept in OLAP hierarchies to drive the compression process. This approach leads to the so-called knowledge-oriented data cube compression paradigm, which is a noticeable alternative to the traditional algorithmic-oriented paradigm that focuses the attention on the issue of compressing the data cube like the latter would be a simple multidimensional array without additional knowledge. This amenity allows us to achieve several benefits, among which a more meaningful exploration of the compressed data cube enriched by semantics-aware metaphors. Our analytical contribution is finally completed by a comprehensive experimental evaluation of our proposed technique on both benchmark and real-life data cubes, also in comparison with well-established histogram-based data cube compression techniques.

Process mining techniques have recently received notable attention in the literature; for their ability to assist in the (re)design of complex processes by automatically discovering models that explain the events registered in some log traces provided as input. Following this line of research, the paper investigates an extension of such basic approaches, where the identification of different variants for the process is explicitly accounted for, based on the clustering of log traces. Indeed, modeling each group of similar executions with a different schema allows us to single out "conformant" models, which, specifically, minimize the number of modeled enactments that are extraneous to the process semantics. Therefore, a novel process mining framework is introduced and some relevant computational issues are deeply studied. As finding an exact solution to such an enhanced process mining problem is proven to require high computational costs, in most practical cases, a greedy approach is devised. This is founded on an iterative, hierarchical, refinement of the process model, where, at each step, traces sharing similar behavior patterns are clustered together and equipped with a specialized schema. The algorithm guarantees that each refinement leads to an increasingly sound mDdel, thus attaining a monotonic search. Experimental results evidence the validity of the approach with respect to both effectiveness and scalability.

This paper investigates the problem of mining unconnected patterns in workflows and presents for its solution two algorithms, both adapting the Apriori approach to the graphical structure of workflows. The first one is a straightforward extension of the level-wise style of Apriori whereas the second one introduces sophisticated graphical analysis of the frequencies of workflow instances. The experiments show that graphical analysis improves the performance of pattern mining by dramatically pruning the search space of candidate patterns.

Today's workflow management systems represent a key technological infrastructure for advanced applications that is attracting a growing body of research, mainly focused in developing tools for workflow management, that allow users both to specify the "static" aspects, like preconditions, precedences among activities, and rules for exception handling, and to control its execution by scheduling the activities on the available resources. This paper deals with an aspect of workflows which has so far not received much attention even though it is crucial for the forthcoming scenarios of large scale applications on the Web: providing facilities for the human system administrator for identifying the choices performed more frequently in the past that had lead to a desired final configuration. In this context, we formalize the problem of discovering the most frequent patterns of executions, i.e., the workflow substructures that have been scheduled more frequently by the system. We attacked the problem by developing two data mining algorithms on the basis of an intuitive and original graph formalization of a workflow schema and its occurrences. The model is used both to prove some intractability results that strongly motivate the use of data mining techniques and to derive interesting structural properties for reducing the search space for frequent patterns. Indeed, the experiments we have carried out show that our algorithms outperform standard data mining algorithms adapted to discover frequent patterns of workflow executions.

This paper presents a rule-based declarative database language which extends DATALOG to express events and nondeterministic state transitions, by using the choice construct to model uncertainty in dynamic rules. The proposed language, called Event Choice DATALOG (DATALOG!ev for short), provides a powerful mechanism to formulate queries on the evolution of a knowledge base, given a sequence of events envisioned to occur in the future. A distinguished feature of this language is the use of multiple spatio-temporal dimensions in order to model a finer control of evolution. A comprehensive study of the computational complexity of answering DATALOG!ev queries is reported.

The main drawbacks of handheld devices (small storage space, small size of the display screen, discontinuance of the connection to the WLAN, etc.) are often incompatible with the need of querying and browsing information extracted from the enormous amount of data which are accessible through the network. In this application scenario, the issues of compression and summarization of data have a leading role: data in a lossy compressed format can be transmitted more efficiently than original ones, and can be effectively stored in the handheld devices (setting the compression ratio accordingly). In this paper we describe a very effective compression technique for datacubes and the architecture of a system (based on this compression technique), called Hand-OLAP, which allows a handheld device to extract and browse compressed information coming from an OLAP server distributed on a wired network.

In many application contexts, like statistical databases, scientific databases, query optimizers, OLAP, and so on, data are often summarized into synopses of aggregate values. Summarization has the great advantage of saving space, but querying aggregate data rather than the original ones introduces estimation errors which cannot be in general avoided, as summarization is a lossy compression. A central problem in designing summarization techniques is to retain a certain degree of accuracy in reconstructing query answers. In this paper we restrict our attention to two-dimensional data, which are relevant for a number of applications, and propose a hierarchical summarization technique, which is combined with the use of indices, i.e. compact structures providing an approximate description of portions of the original data. Experimental results show that the technique gives approximation errors much smaller than other "general purpose" techniques, such as wavelets and various types of multi-dimensional histogram.

The availability of automatic tools for inferring semantics of database schemes is useful to solve several database design problems such as that of obtaining cooperative information systems or data warehouses from large sets of data sources. In this context, a main problem is to single out similarities or dissimilarities among scheme objects (interscheme properties). This paper presents graph-based techniques for a uniform derivation of interscheme properties including synonymies, homonymies, type conflicts, and subscheme similarities. These techniques are characterized by a common core: the computation of maximum weight matchings on some bipartite weighted graphs derived using a suitable metrics to measure semantic closeness of objects. The techniques have been implemented in a system prototype. Several experiments conducted with it, and (in part) accounted for in the paper, confirmed the effectiveness of our approach.

Histograms are used to summarize the contents of relations for the estimation of query result sizes into a number of buckets. Several techniques (e.g., MaxDiff and V-Optimal) have been proposed in the past for determining bucket boundaries which provide better estimations. This paper proposes to use 32 bit information (4-level tree index) for each bucket for storing approximated cumulative frequencies at 7 internal intervals of a bucket. Both theoretical analysis and experimental results show that the 4-level tree index provides the best frequency estimation inside a bucket. The index is later added to two well-known techniques for constructing histograms, MaxDiff and V-Optimal, thus obtaining high improvements in the frequency estimation over inter-bucket ranges w.r.t. the original methods.

The availability of automatic tools for inferring semantics from database schemes is very relevant in designing large cooperative information system applications involving many information sources. Deriving semantics from existing data sources exploits properties of objects belonging to different input schemes (interscheme properties), such as synonymies, homonymies, type conflicts, and subscheme similarities. The paper gives a contribution in this context by proposing a collection of graph based techniques for a uniform derivation of all interscheme properties. All techniques are characterized by a common core consisting of the computation of a maximum weight matching on suitable bipartite graphs. The computation of the maximum weight matching is based on a suitable metrics which is used to measure object semantic similarities. A running example is provided to illustrate the approach.

Article Free Access Share on An automatic technique for detecting type conflicts in database schemes Authors: Luigi Palopoli Dipartimento di Elettronica, Informatica e Sistemistica, Università della Calabra, 87036 Rende (CS), Italy Dipartimento di Elettronica, Informatica e Sistemistica, Università della Calabra, 87036 Rende (CS), ItalyView Profile , Domenico Saccá View Profile , Domenico Ursino Dipartimento di Elettronica, Informatica e Sistemistica, Università della Calabra, 87036 Rende (CS), Italy Dipartimento di Elettronica, Informatica e Sistemistica, Università della Calabra, 87036 Rende (CS), ItalyView Profile Authors Info & Claims CIKM '98: Proceedings of the seventh international conference on Information and knowledge managementNovember 1998 Pages 306–313https://doi.org/10.1145/288627.288671Online:01 November 1998Publication History 22citation346DownloadsMetricsTotal Citations22Total Downloads346Last 12 Months9Last 6 weeks1 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 SiteeReaderPDF

An important tool for the integration of large federated database systems is a global dictionary describing all the involved schemes into an unified framework. The first step in the construction of such a dictionary is the discovery of the properties holding among objects in different schemes. This paper presents novel algorithms to discover possible synonyms, homonyms and inclusions. In addition, the paper also deals with another crucial step in the construction of a dictionary: schema integration. The approach proposed for this step exploits inter-schema properties discovered in the previous step to achieve schema integration. This approach is also concerned with producing suitable abstractions in order to structure the description of the global dictionary into a hierarchy of concepts in order to yield a more flexible, uniform view of the attached databases. The above two steps are interleaved with other steps (mainly devoted to interfacing with database administrators and to validating the discovered properties) and have been experimented with for the construction of a global dictionary for a large number of public administration database systems.

Stable models have been first introduced in the domain of total interpretations (T- stable models), where the existence of multiple T-stable models for the same program provides a powerful mechanism to express non-determinism. Stable models have been later extended to the domain of partial interpretations (P-stable models). In this paper, we show that the presence of multiple P-stable models need not be a direct manifestation of non-determinism, for it can be instead an expression of assorted degrees of undefinedness. To separate the two factors, non-determinism and undefinedness, this paper introduces the notion of deterministic stable models and strictly non-deterministic ones. Deterministic stable models form an interesting family, having a lattice structure where the well-founded model serves as the bottom; the top of the lattice, the maximum deterministic stable model, resolves differences between any two P-stable models in the family. On the other hand, every two models in a fam...

Previous researchers have proposed generalizations of Horn clause logic to support negation and non-determinism as two separate extensions. In this paper, we show that the stable model semantics for logic programs provides a unified basis for the treatment of both concepts. First, we introduce the concepts of partial models, stable models, strongly founded models and deterministic models and other interesting classes of partial models and study their relationships. We show that the maximal deterministic model of a program is a subset of the intersection of all its stable models and that the well-founded model of a program is a subset of its maximal deterministic model. Then, we show that the use of stable models subsumes the use of the non-deterministic choice construct in LDL and provides an alternative definition of the semantics of this construct. Finally, we provide a constructive definition for stable models with the introduction of a procedure, called backtracking fixpoint, that non-deterministically constructs a total stable model, if such a model exists.

An extension of logic programming, called “ordered logic programming”, which includes some abstractions of the object-oriented paradigm, is presented. An ordered program consists of a number of modules (objects), where each module is composed by a number of rules possibly with negated head predicates. A sort of “isa” hierarchy can be defined among the modules in order to allow for rule inheritance. Therefore, every module sees its own rules as local rules and the rules of the other modules to which it is connected by the “isa” hierarchy as global rules. In this way, as local rules may hide global rules, it is possible to deal with default properties and exceptions. This new approach represents a novel attempt to combine the logic paradigm with the object-oriented one in knowledge base systems. Moreover, this approach provides a new ground for explaining some recent proposals of semantics for classical logic programs with negation in the rule bodies and gives an interesting semantics to logic programs with negated rule heads.

Systems EROS is a physical design tool for CODASYL database systems which covers a large spectrum of decision variables, notably location mode, set implementation, set order, and search keys. System EROS is based on a model where the CODASYL physical database design problem is formulated as an extension of the index selection problem in the relational database environment. Optimization algorithms for index selection are extended to solve the more complex problem of selecting a good physical access path configuration for CODASYL databases. The proposed approach represents a unified solution to the physical database design problem for both CODASYL and relational systems.>

Article Worst-case complexity analysis of methods for logic query implementation Share on Authors: A. Marchetti-Spaccamella Dipartimento di Informatica e Slstemistica, Università di Roma "La Saptenza", Rome, Italy Dipartimento di Informatica e Slstemistica, Università di Roma "La Saptenza", Rome, ItalyView Profile , A. Pelaggi Dipartimento di Informatica e Slstemistica, Università di Roma "La Saptenza", Rome, Italy Dipartimento di Informatica e Slstemistica, Università di Roma "La Saptenza", Rome, ItalyView Profile , D. Sacca Dipartimento di Sistemi, Università della Calabria and CRAI, Rende, Italy Dipartimento di Sistemi, Università della Calabria and CRAI, Rende, ItalyView Profile Authors Info & Claims PODS '87: Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systemsJune 1987 Pages 294–301https://doi.org/10.1145/28659.28691Published:01 June 1987 29citation191DownloadsMetricsTotal Citations29Total Downloads191Last 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

The problem considered is that of implementing recursive queries, expressed in a logic-based language, by efficient fixpoint computations. In particular, the situation is studied where the initial bindings in the recursive predicate can be used to restrict the search space and ensure safety of execution. Two key techniques previously proposed to solve this problem are (i) the highly efficient counting method, and (ii) the magic set method which is safe in a wider range of situations than (i). In this paper, we present a family of methods, called the magic counting methods, that combines the advantages of (i) and (ii). This is made possible by the similarity of the strategies used by the counting method and the magic set method for propagating the bindings. This paper introduces these new methods, examines their computational complexity, and illustrates the trade-offs between the family members and their superiority with respect to the old methods.

A heuristic algorithm for the selection of an optimal access path configuration for CODASYL databases is presented. This algorithm is based on the idea of extending index selection techniques proposed for relational systems to COD ASYL systems. The proposed approach has the worth effacing the physical design problem in a unified way; moreover, it allows for covering a large spectrum of physical decision variables, namely, location modes, set implementations, set orders and search keys.

this paper, we study the problem of efficient implementations of queries on recursire rules without function symbols. We focus on an important subclass, called canonical strongly linear queries (CSL queries), and study the binding-passing property, which entails the propagation of the initial bindings (established by constants in the query goal) during the top-down (as in backward chaining) execu- tion phase

In this paper the problem of minimal representations for particular classes of directed hypergraphs is analyzed. Various concepts of minimal representations of directed hypergraphs (called minimal equivalent hypergraphs) are introduced as extensions to the concepts of transitive reduction and minimum equivalent graph of directed graphs. In particular, we consider equivalent hypergraphs which are minimal with respect to all parameters which may be adopted to characterize a given hypergraph (number of hyperarcs, number of adjacency lists required for the representation, length of the overall description,etc.). The relationships among the various concepts of minimality are discussed and their computational properties are analyzed. In order to derive such results, a graph representation of hypergraphs is introduced.

A hypergraph formalism is introduced to represent database schemata. In particular, a database schema B , described by one full join dependency and a set of functional dependencies, is represented by a (database) hypergraph H , containing both undirected and directed hyperedges. Undirected hyperedges correspond to the relations in the join dependency, and directed hyperedges correspond to the functional dependencies. In addition, two classes of database hypergraphs are defined: e -acyclic hypergraphs and e -independent hypergraphs. A hypergraph is e -acyclic if it is equivalent to some acyclic hypergraph; it is e -independent if it is equivalent to some independent (i.e., cover-embedding) hypergraph. Furthermore, the closure of a database hypergraph is defined as the extension of the transitive closure of a graph. By using a lower bound and an upper bound of the hypergraph closure (called L-closure and U-closure, respectively), it is proved that two e -acyclic ( e -independent) hypergraphs are equivalent if and only if they have the same closure. Moreover, a hypergraph is e -acyclic ( e -independent) if and only if its closure is acyclic (independent) and, in most cases, such a recognition can be done in polynomial time. Finally, it is shown how to use the database hypergraph closure to solve some database design problems.

In a distributed database system the partitioning and allocation of the database over the processor nodes of the network can be a critical aspect of the database design effort. In this paper we develop and evaluate algorithms that perform this task in a computationally feasible manner. The network we consider is characterized by a relatively high communication bandwidth, considering the processing and input output capacities in its processors. Such a balance is typical if the processors are connected via busses or local networks. The common constraint that transactions have a specific root node no longer exists, so that there are more distribution choices. However, a poor distribution leads to less efficient computation, higher costs, and higher loads in the nodes or in the communication network so that the system may not be able to handle the required set of transactions. Our approach is to first split the database into fragments which constitute appropriate units for allocation. The fragments to be allocated are selected based on maximal benefit criteria using a greedy heuristic. The assignment to processor nodes uses a first-fit algorithm. The complete algorithm, called GFF, is stated in a procedural form. The complexity of the problem and of its candidate solutions are analyzed and several interesting relationships are proven. Alternate benefit metrics are considered, since the execution cost of the allocation procedure varies by orders of magnitude with the alternatives of benefit evaluation. A mixed benefit evaluation strategy is eventually proposed. A model for evaluation is presented. Two of the strategies are experimentally evaluated, and the reported results support the discussion. The approach should be suitable for other cases where resources have to be allocated subject to resource constraints.

Article Free Access Share on Properties of database schemata with functional dependencies Authors: D. Sacca CRAI, Rende, Italy CRAI, Rende, ItalyView Profile , F. Maufredi CRAI, Rende, Italy CRAI, Rende, ItalyView Profile , A. Mecchia CRAI, Rende, Italy CRAI, Rende, ItalyView Profile Authors Info & Claims PODS '84: Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systemsApril 1984 Pages 19–28https://doi.org/10.1145/588011.588015Online:02 April 1984Publication History 5citation220DownloadsMetricsTotal Citations5Total Downloads220Last 12 Months3Last 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 SiteeReaderPDF

A graph-theoretic approach for the representation of functional dependenoes in relauonal databases is introduced and applied in the construction of algorithms for manipulating dependencies.This approach allows a homogeneous treatment of several problems (closure, minimization, etc.), which leads to simpler proofs and, m some cases, more efficient algorithms than in the current literature.