Skip to main content

About this book

This book constitutes the proceedings of the 7th International Symposium on Foundations of Information and Knowledge Systems, FoIKS 2012, held in Kiel, Germany, in March 2012. The 12 regular and 8 short papers, presented together with two invited talks in full paper-length, were carefully reviewed and selected from 53 submissions. The contributions cover foundational aspects of information and knowledge systems. These include the application of ideas, theories or methods from specific disciplines to information and knowledge systems, such as discrete mathematics, logic and algebra, model theory, informaiton theory, complexity theory, algorithmics and computation, statistics, and optimization.

Table of Contents


Invited Talks

Uniform Evaluation of Nonmonotonic DL-Programs

Nonmonotonic description logic programs are a major formalism for a loose coupling of rules and ontologies, formalized in logic programming and description logics, respectively. While this approach is attractive for combining systems, the impedance mismatch between different reasoning engines and the API-style interfacing are an obstacle to efficient evaluation of dl-programs in general. Uniform evaluation circumvents this by transforming programs into a single formalism, which can be evaluated on a single reasoning engine. In this paper, we consider recent and ongoing work on this approach which uses relational first-order logic (and thus relational database engines) and datalog with negation as target formalisms. Experimental data show that significant performance gains are possible and suggest the potential of this approach.
Thomas Eiter, Thomas Krennwallner, Patrik Schneider, Guohui Xiao

Foundations of XML Based on Logic and Automata: A Snapshot

XML query and schema languages have some obvious connections to Formal Language Theory. For example, Document Type Definitions (DTDs) can be viewed as tree grammars and use regular expressions, XML Schemas resemble tree automata. Likewise, there are immediate links to Logic, e.g., through the classical characterization of regular tree languages by monadic second-order logic.
It is therefore not surprising that concepts from Logic and Formal Language Theory played an important role in the development of the theoretical foundations of XML query and schema languages. For example, they helped to analyze the expressiveness of languages, to understand the restrictions posed by the W3C standards, and to develop algorithms for various purposes, including efficient evaluation and static analysis.
However, methods from Logic and Formal Languages have not merely been applied to XML theory, the fertilization took place both ways. XML theory posed a lot of new challenges for Logic and Formal Language Theory and triggered various new research lines, e.g., the study of deterministic regular expressions and the development of automata for trees with data values.
The aim of the talk at FoIKS 2012 is to present some of the fundamental connections between XML query and schema languages and Logic and Formal Language Theory, to report on recent developments in the area, and to highlight some current directions of research. This accompanying paper is a kind of annotated bibliography for that talk.
Thomas Schwentick

Regular Articles

Inconsistency-Tolerance in Knowledge-Based Systems by Dissimilarities

Distance-based reasoning is a well-known approach for defining non-monotonic and paraconsistent formalisms, which so far has been mainly used in the context of standard two-valued semantics. In this paper, we extend this approach to arbitrary denotational semantics by considering dissimilarities, a generalization of distances. Dissimilarity-based reasoning is then applied for handling inconsistency in knowledge-based systems using various non-classical logics. This includes logics defined by multi-valued semantics, non-deterministic semantics, and possible-worlds (Kripke-style) semantics. In particular, we show that our approach allows to define a variety of inconsistency-tolerant entailment relations, and that it extends many well-studied forms of reasoning in the context of belief revision and database integration.
Ofer Arieli, Anna Zamansky

Revising Belief without Revealing Secrets

In multiagent systems, agents interact and in particular exchange information to achieve a joint goal, e.g., arrange a meeting, negotiate a sales contract etc. An agent, as a rational reasoner, is able to incorporate new information into her belief about her environment (belief revision) or to share her belief with other agents (query answering). Yet, such an agent might be interested to hide confidential parts of her belief from other negotiating agents while these agents are supposed to reason about her reactions to revisions and queries. We study how an agent can control her reactions to revisions and queries requested by another agent who may attempt to skeptically entail confidential beliefs. As our main contribution, we present procedures that provably enforce confidentiality, to be employed by the reacting agent.
Joachim Biskup, Cornelia Tadros

More Than the Sum of Its Parts – Holistic Ontology Alignment by Population-Based Optimisation

Ontology alignment is a key challenge to allow for interoperability between heterogeneous semantic data sources. Today, most algorithms extract an alignment from a matrix of the pairwise similarities of ontological entities of two ontologies. However, this standard approach has severe disadvantages regarding scalability and is incapable of accounting for global alignment quality criteria that go beyond the aggregation of independent pairwise correspondence evaluations. This paper considers the ontology alignment problem as an optimisation problem that can be addressed using nature-inspired population-based optimisation heuristics. This allows for the deployment of an objective function which can be freely defined to take into account individual correspondence evaluations as well as global alignment constraints. Moreover, such algorithms can easily be parallelised and show anytime behaviour due to their iterative nature. The paper generalises an existing approach to the alignment problem based on discrete particle swarm optimisation, and presents a novel implementation based on evolutionary programming. First experimental results demonstrate feasibility and scalability of the presented approaches.
Jürgen Bock, Sebastian Rudolph, Michael Mutter

Handling Preferences in P2P Systems

A peer to peer system easily provides a way to aggregate information distributed in the network. Anyhow, while collecting data it is quite natural for a source peer to associate different degrees of reliability to the portion of data provided by its neighbor peers. This paper investigates the data exchange problem among distributed independent sources and concentrates on the task of using dynamic preferences to drive the integration process in the case of conflicting information. Previous works in the literature are rigid in the sense that preferences between conflicting sets of atoms, that a peer can import, only depends on the priorities associated to the source peers at design time. These approaches do not allow to model concepts such as “import tuples from the peer having the highest upload speed if they conflict” or “among conflicting values import the most recent ones”. In this paper it is supposed the existence of a special peer, called authority peer. It contains information about the peers in the network, is accessible from each peer of the system and is used to enhance preference mechanism. The framework, here proposed, ensures dynamism by allowing to select among different scenarios looking at the properties of data provided by the peers: this is done by “dynamically” establishing priorities among mapping rules.
Luciano Caroprese, Ester Zumpano

Backing and Undercutting in Abstract Argumentation Frameworks

This work will introduce a novel combination of two important argumentation related notions. We will start from the well-known basis of Abstract Argumentation Frameworks or AFs, and we will build a new formalism in which the notions corresponding to Toulmin’s backings and Pollock’s undercutting defeaters are considered. The resulting system, Backing-Undercutting Argumentation Frameworks or BUAFs, will be an extension of the AFs that includes a specialized support relation, a distinction between different attack types, and a preference relation among arguments. Thus, BUAFs will provide a richer representation tool for handling scenarios where information can be attacked and supported.
Andrea Cohen, Alejandro J. García, Guillermo R. Simari

The Impact of Transitive Closure on the Boolean Expressiveness of Navigational Query Languages on Graphs

Several established and novel applications motivate us to study the expressive power of navigational query languages on graphs, which represent binary relations. Our basic language has only the operators union and composition, together with the identity relation. Richer languages can be obtained by adding other features such as other set operators, projection and coprojection, converse, and the diversity relation. In this paper, we show that, when evaluated at the level of boolean queries with an unlabeled input graph (i.e., a single relation), adding transitive closure to the languages with coprojection adds expressive power, while this is not the case for the basic language to which none, one, or both of projection and the diversity relation are added. In combination with earlier work [10], these results yield a complete understanding of the impact of transitive closure on the languages under consideration.
George H. L. Fletcher, Marc Gyssens, Dirk Leinders, Jan Van den Bussche, Dirk Van Gucht, Stijn Vansummeren, Yuqing Wu

Using Functional Dependencies for Reducing the Size of a Data Cube

Functional dependencies (FD’s) are a powerful concept in data organization. They have been proven very useful in e.g., relational databases for reducing data redundancy. Little work however has been done so far for using them in the context of data cubes. In the present paper, we propose to characterize the parts of a data cube to be materialized with the help of the FD’s present in the underlying data. For this purpose, we consider two applications: (i) how to choose the best cuboids of a data cube to materialize in order to guarantee a fixed performance of queries and, (ii) how to choose the best tuples, hence partial cuboids, in order to reduce the size of the data cube without loosing information. In both cases we show how FD’s are fundamental.
Eve Garnaud, Sofian Maabout, Mohamed Mosbah

Armstrong Databases and Reasoning for Functional Dependencies and Cardinality Constraints over Partial Bags

Data dependencies capture meaningful information about an application domain within the target database. The theory of data dependencies is largely a theory over relations. To make data processing more efficient in practice, partial bags are permitted as database instances to accommodate partial and duplicate information. However, data dependencies interact differently over partial bags than over the idealized special case of relations. In this paper, we study the implication problem of the combined class of functional dependencies and cardinality constraints over partial bags. We establish an axiomatic and an algorithmic characterization of the implication problem. These findings have important applications in database design and data processing. Finally, we investigate structural and computational properties of Armstrong databases for the class of data dependencies under consideration. These results can be utilized to consolidate and communicate the understanding of the application domain between different stake-holders of a database.
Sven Hartmann, Henning Köhler, Sebastian Link, Bernhard Thalheim

FD Covers and Universal Complements of Simple Projections

The constant-complement strategy, in which the admissible updates to a given view are those which hold a second complementary view constant, remains one of the most attractive formalisms for identifying suitable translation mechanisms for updates to views of database schemata. However, in general, it suffers from the drawback that the reflections of view updates to the main schema can depend upon the choice of complement in various ways. To overcome this drawback completely, a special kind of complement, called a universal complement, is required. In this paper, sufficient conditions for the existence of such a complement are established for a classical but nevertheless very important setting — views defined by simple projection of a universal relational schema constrained by functional dependencies (FDs). Certain uniqueness properties of covers of these dependencies prove critical in the characterization. The results are extended to quasi-universal complements, which are unique up to exchange of equivalent attributes, thus recapturing certain situations for which unique covers do not exist.
Stephen J. Hegner

Encoding Databases Satisfying a Given Set of Dependencies

Consider a relation schema with a set of dependency constraints. A fundamental question is what is the minimum space where the possible instances of the schema can be ”stored”. We study the following model. Encode the instances by giving a function which maps the set of possible instances into the set of words of a given length over the binary alphabet in a decodable way. The problem is to find the minimum length needed. This minimum is called the information content of the database.
We investigate several cases where the set of dependency constraints consist of relatively simple sets of functional or multivalued dependencies.
We also consider the following natural extension. Is it possible to encode the instances such a way that small changes in the instance cause a small change in the code.
Gyula O. H. Katona, Krisztián Tichler

On Lifted Inference for a Relational Probabilistic Conditional Logic with Maximum Entropy Semantics

When extending probabilistic logic to a relational setting, it is desirable to still be able to use efficient inference mechanisms developed for the propositional case. In this paper, we investigate the relational probabilistic conditional logic FO-PCL whose semantics employs the principle of maximum entropy. While in general, this semantics is defined via the ground instances of the rules in an FO-PCL knowledge base \(\mathcal{R}\), the maximum entropy model can be computed on the level of rules rather than on the level of instances of the rules if \(\mathcal{R}\) is parametrically uniform, thus providing lifted inference.We elaborate in detail the reasons precluding \(\mathcal{R}\) from being parametrically uniform. Based on this investigation, we derive a new syntactic criterion for parametric uniformity and develop an algorithm that transforms any FO-PCL knowledge base \(\mathcal{R}\) into an equivalent knowledge base \(\mathcal{R'}\) that is parametrically uniform.
Annika Krämer, Christoph Beierle

Flexible and Efficient Distributed Resolution of Large Entities

Entity resolution (ER) is a computationally hard problem of data integration scenarios, where database records have to be grouped according to the real-world entities they belong to. In practice these entities may consist of only a few records from different data sources with typos or historical data. In other cases they may contain significantly more records, especially when we search for entities on a higher level of a concept hierarchy than records.
In this paper we give theoretical foundation of a variety of practically important match functions. We show that under these formulations, ER with large entities can be solved efficiently with algorithms based on MapReduce, a distributed computing paradigm. Our algorithm can efficiently incorporate probabilistic and similarity-based record match, enabling flexible match function definition. We demonstrate the usability of our model and algorithm in a real-world insurance ER scenario, where we identify household groups of client records.
András J. Molnár, András A. Benczúr, Csaba István Sidló

On Real-Valued Evaluation of Propositional Formulas

Arguably, [0,1]-valued evaluation of formulas is dominant form of representation of uncertainty, believes, preferences and so on despite some theoretical issues - most notable one is incompleteness of any unrestricted finitary formalization. We offer an infinitary propositional logic (formulas remain finite strings of symbols, but we use infinitary inference rules with countably many premises, primarily in order to address the incompleteness issue) which is expressible enough to capture finitely additive probabilistic evaluations, some special cases of truth functionality (evaluations in Lukasiewicz, product, Gödel and \(\L\mathrm\Pi\frac{1}{2}\) logics) and the usual comparison of such evaluations. The main technical result is the proof of completeness theorem (every consistent set of formulas is satisfiable).
Aleksandar Perović, Dragan Doder, Zoran Ognjanović

Detecting Suspect Answers in the Presence of Inconsistent Information

In the presence of inconsistent information, two classical approaches consist in (i) cleaning the information by means of an automated process, for instance by performing a minimal set of updates aimed at restoring consistency, (ii) returning only the answers that are certain with respect to a given query, as in consistent query answering. In this paper, we propose an alternative approach, somewhat inspired by artificial intelligence works, which is aimed at warning the user about the presence of suspect answers in a query result. Roughly speaking, the idea is that such elements can be identified inasmuch as they can be found in the answers to contradictory queries. This idea may also be refined by introducing some gradedness in terms of cardinality or similarity.
Olivier Pivert, Henri Prade

Learning the News in Social Networks

In social media such as facebook, the most popular desire is to learn the news about other people. In this paper, we study the following problem related to information propagation: Suppose that there is a set U of N users in a social network. They meet online from time to time and share information they know about themselves and the other users in the network. Whenever a group g ⊂ U of users meet, they want to know who has the latest information about every user in U. A naive solution to this problem is to use timestamps. However, there are drawbacks to this scheme including the burden on the users to maintain reliable timestamps and the fact that the timestamps grow unbounded over time. It is natural to ask if it is possible to learn the latest information without using timestamps. We present an efficient method which removes the need to timestamp user information (news). Instead, only the meetings of the groups have to be indexed. Furthermore, we show that this indexing can be performed using a finite set of labels so that each user stores at most O(N 2 logN) bits of information. We also show that this bound can be improved in some cases if we have further information on the topology of the network.
Krishnan Rajagopalan, Venkatesh Srinivasan, Alex Thomo

Verifying Resource Requirements for Ontology-Driven Rule-Based Agents

Recent efforts towards the Semantic Web have resulted in powerful languages such as Semantic Web Rule Language (SWRL) based on OWL-DL and RuleML. Rule languages and inference engines incorporate reasoning capabilities to Semantic Web application systems. In this paper we present an approach for the design and specification of ontology-driven multi-agent rule-based systems. We use the Maude rewriting system and its Linear Temporal Logic (LTL) model checking tool to verify response time guarantees for the target systems. We present TOVRBA, an extended version of a verification tool developed by the first author, for ontology-driven multi-agent rule-based systems which allows the designer to specify information about agents’ interactions, behavior, and execution strategies at different levels of abstraction. TOVRBA generates an encoding of the system for the Maude LTL model checker, allowing properties of the system to be verified. We illustrate the use of the framework on a simple healthcare system.
Abdur Rakib, Rokan Uddin Faruqui, Wendy MacCaull

Formalizing Production Systems with Rule-Based Ontologies

In this paper we proposed a new semantics for the combination of production systems with arbitrary DL ontologies. Unlike previous approaches, the semantics presented here allow looping rules and can handle inconsistencies produced by the interaction of the rule actions and the ontology. We also define a sound embedding of such semantics, restricted to rule-based DL Ontologies, into Transaction Logic with partial action definitions (\(\mathcal{TR}^{PAD}\)). This reduction adds a declarative semantics to the combination. To model production systems in \(\mathcal{TR}^{PAD}\), we extend \(\mathcal{TR}^{PAD}\) with default negation and define the well-founded semantics for it.
Martín Rezk, Michael Kifer

Count Constraints and the Inverse OLAP Problem: Definition, Complexity and a Step toward Aggregate Data Exchange

A typical problem in database theory is to verify whether there exists a relation (or database) instance satisfying a number of given dependency constraints. This problem has recently received a renewed deal of interest within the context of data exchange, but the issue of handling constraints on aggregate data has not been much investigated so far, notwithstanding the relevance of aggregate operations in exchange systems. This paper introduces count constraints that require the results of given count operations on a relation to be within a certain range. Count constraints are defined by a suitable extension of first order predicate calculus, based on set terms, and they are then used in a new decisional problem, the Inverse OLAP: given a star schema, does there exist a relation instance satisfying a set of given count constraints? The new problem turns out to be NEXP complete under various conditions: program complexity, data complexity and combined complexity. Count constraints can be also used into a data exchange system context, where data from the source database are transferred to the target database using aggregate operations.
Domenico Saccà, Edoardo Serra, Antonella Guzzo

Synchronous Parallel Database Transformations

The DB-ASM thesis states that every database transformation can be expressed by a variant of Abstract State Machines. These machines permit unbounded parallelism only on the finite database part of a state. This paper generalises this work by permitting unbounded parallelism on the algorithmic part of the state as well. The “parallel DB-ASM”-thesis results from combining Gurevich’s parallel ASM thesis with the DB-ASM thesis. In doing so, it turns out that the postulates for synchronous parallel database transformations can be significantly simplified compared with the seminal work of Gurevich. The key idea is to generalise the notion of bounded exploration witnesses allowing them to include special non-ground terms.
Klaus-Dieter Schewe, Qing Wang

Functional Dependencies on Extended Relations Defined by Regular Languages

In this paper, we first rephrase the notion of extended tuple as a sentence from a regular language generated by a grammar G where the nonterminal symbols of the grammar are the attribute names of the tuple. Finite sets of extended tuples play the role of extended relation instances. Then we introduce the dual language, which generates the accepted tuple-types of the extended relation. We define the syntactical form of functional dependencies for extended relation on the graph of the finite state automaton associated to the dual language. Using this model we can handle extended relations generated by recursive regular expressions too. The implication problem of our class of dependencies is decidable by a version of Chase algorithm specified on the graph of the associated FSA.
Gyula I. Szabó, András Benczúr


Additional information

Premium Partner

    Image Credits