Lecture Notes in Computer Science 7153 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison LancasterUniversity,UK TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA AlfredKobsa UniversityofCalifornia,Irvine,CA,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA MoniNaor WeizmannInstituteofScience,Rehovot,Israel OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen TUDortmundUniversity,Germany MadhuSudan MicrosoftResearch,Cambridge,MA,USA DemetriTerzopoulos UniversityofCalifornia,LosAngeles,CA,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA GerhardWeikum MaxPlanckInstituteforInformatics,Saarbruecken,Germany Thomas Lukasiewicz Attila Sali (Eds.) Foundations of Information and Knowledge Systems 7th International Symposium, FoIKS 2012 Kiel, Germany, March 5-9, 2012 Proceedings 1 3 VolumeEditors ThomasLukasiewicz UniversityofOxford DepartmentofComputerScience WolfsonBuilding,ParksRoad,Oxford,OX13QD,UK E-mail:[email protected] AttilaSali HungarianAcademyofSciences AlfrédRényiInstitute Reáltanodautca13-15,1053Budapest,Hungary E-mail:[email protected] ISSN0302-9743 e-ISSN1611-3349 ISBN978-3-642-28471-7 e-ISBN978-3-642-28472-4 DOI10.1007/978-3-642-28472-4 SpringerHeidelbergDordrechtLondonNewYork LibraryofCongressControlNumber:2012931445 CRSubjectClassification(1998):G.2,F.4.1,I.2.3,I.2.4,D.3 LNCSSublibrary:SL3–InformationSystemsandApplication,incl.Internet/Web andHCI ©Springer-VerlagBerlinHeidelberg2012 Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsareliable toprosecutionundertheGermanCopyrightLaw. Theuseofgeneraldescriptivenames,registerednames,trademarks,etc.inthispublicationdoesnotimply, evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevantprotectivelaws andregulationsandthereforefreeforgeneraluse. Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) Preface This volume contains the articles that were presented at the 7th International Symposium on Foundations of Information and Knowledge Systems (FoIKS 2012), which was held in Kiel, Germany, March 5–9, 2012. The FoIKS symposia provide a biennial forum for presenting and discussing theoreticalandappliedresearchoninformationandknowledgesystems.Thegoal is to bring together researchers with an interest in this subject, share research experiences, promote collaboration, and identify new issues and directions for future research. FoIKS 2012 solicited original contributions on foundational aspects of in- formation and knowledge systems. This included submissions that apply ideas, theories or methods from specific disciplines to information and knowledge sys- tems. Examples of such disciplines are discrete mathematics, logic and algebra, model theory, information theory, complexity theory, algorithmics and compu- tation, statistics, and optimization. PreviousFoIKSsymposiawereheldinSofia(Bulgaria)in2010,Pisa(Italy)in 2008,Budapest(Hungary)in2006,Vienna(Austria)in2004,SchlossSalzaunear Kiel (Germany) in 2002, and Burg/Spreewald near Berlin (Germany) in 2000. FoIKS took up the tradition of the conference series Mathematical Fundamen- tals ofDatabaseSystems (MFDBS), whichinitiated East–Westcollaborationin the field of database theory. Former MFDBS conferences were held in Rostock (Germany) in 1991, Visegrad (Hungary) in 1989, and Dresden (Germany) in 1987. The FoIKS symposia are a forum for intense discussions. Speakers are given sufficient time to present their ideas and results within the larger context of their research.Furthermore,participants are askedin advance to prepare a first response to a contribution of another author in order to initiate discussion. Suggested topics for FoIKS 2012 included, but were not limited to: – Database Design: formal models, dependencies and independencies – Dynamics of Information: models of transactions, concurrency control, updates, consistency preservation, belief revision – InformationFusion:heterogeneity,views,schemadominance,multiplesource information merging, reasoning under inconsistency – Integrity and Constraint Management: verification, validation, consistent query answering, information cleaning – Intelligent Agents: multi-agent systems, autonomous agents, foundations of software agents, cooperative agents, formal models of interactions, logical models of emotions – Knowledge Discovery and Information Retrieval: machine learning, data mining, formal concept analysis and association rules, text mining, infor- mation extraction VI Preface – Knowledge Representation, Reasoning and Planning: non-monotonic for- malisms,probabilisticandnon-probabilisticmodelsofuncertainty,graphical models and independence, similarity-based reasoning, preference modeling and handling, argumentation systems – LogicsinDatabasesandAI:classicalandnon-classicallogics,logicprogram- ming,descriptionlogics,spatialandtemporallogics,probabilitylogic,fuzzy logic – MathematicalFoundations:discretestructuresandalgorithms,graphs,gram- mars,automata,abstractmachines,finite modeltheory,informationtheory, coding theory, complexity theory, randomness – Security in Information and Knowledge Systems: identity theft, privacy, trust, intrusion detection, access control, inference control, secure Web ser- vices, secure Semantic Web, risk management – Semi-StructuredDataandXML:datamodeling,dataprocessing,datacom- pression, data exchange – Social Computing: collective intelligence and self-organizingknowledge,col- laborative filtering, computational social choice, Boolean games, coalition formation, reputation systems – The Semantic Web and Knowledge Management: languages, ontologies, agents, adaption, intelligent algorithms – The WWW: models of Web databases, Web dynamics, Web services, Web transactions and negotiations Thisvolumecontains20articles(12regularand8shortpresentations),which were selected out of 53 submissions for FoIKS 2012 in a rigorousreviewing pro- cess,whereeachsubmissionwasreviewedby atleastthree ProgramCommittee members. The volume also contains articles for two of the three invited talks. We wish to thank all authors who submitted papers and all conference par- ticipants for fruitful discussions. We are grateful to Andra´s Benczu´r, Thomas Eiter, and Thomas Schwentick for their invited talks. We would like to thank the Program Committee members and additional reviewers for their timely ex- pertiseincarefullyreviewingthe submissions.SpecialthankstoBernhardThal- heimandhisteam(inparticular,StefanieJureit,SteffenGaede,KaiJannaschk, Hans-Joachim Klein, Ren´e Noack, and Ove So¨rensen) from the Christian Al- brechts University Kiel for the organization of the conference and wonderful days in Kiel. We want to thank Markus Kirchberg for his work as Publicity Chair.ManythanksalsotothedevelopersoftheEasyChairConferenceSystem, which we used for the reviewing process and the preparationof this volume. March 2012 Thomas Lukasiewicz Attila Sali Conference Organization FoIKS2012wasorganizedbytheChristianAlbrechtsUniversityKiel,Germany. Program Chairs Thomas Lukasiewicz University of Oxford, UK Attila Sali Alfr´ed R´enyi Institute, Hungarian Academy of Sciences, Hungary Local Organization Chair Bernhard Thalheim Christian Albrechts University Kiel, Germany Publicity Chair Markus Kirchberg Hewlett-Packard Labs, Singapore Program Committee Jos´e Ju´lio Alferes Universidade Nova de Lisboa, Portugal Leila Amgoud University of Toulouse, France Paolo Atzeni Roma Tre University, Italy Salem Benferhat University of Lens, France Leopoldo Bertossi Carleton University, Canada Philippe Besnard University of Toulouse, France Joachim Biskup University of Dortmund, Germany Piero A. Bonatti University of Naples “Federico II”, Italy Andrea Cal`ı Birkbeck, University of London, UK Paolo Cappellari Dublin City University, Ireland Jan Chomicki University at Buffalo, USA Alfredo Cuzzocrea ICAR-CNR and University of Calabria, Italy Marina De Vos University of Bath, UK Michael I. Dekhtyar Tver State University, Russia James P. Delgrande Simon Fraser University, Canada Tommaso Di Noia Technical University of Bari, Italy Ju¨rgen Dix Clausthal University of Technology, Germany Francesco M. Donini University of Tuscia, Italy Thomas Eiter Vienna University of Technology, Austria Ronald Fagin IBMAlmadenResearchCenter,SanJose,USA Victor Felea “Al.I. Cuza” University of Ia¸si, Romania Flavio Ferrarotti VictoriaUniversityofWellington,NewZealand VIII Conference Organization Sergio Flesca University of Calabria, Italy Lluis Godo Artificial Intelligence Research Institute (IIIA - CSIC), Spain Gianluigi Greco University of Calabria, Italy Claudio Gutierrez University of Chile, Chile Sven Hartmann Clausthal University of Technology, Germany Stephen J. Hegner Ume˚a University, Sweden Edward Hermann Haeusler Pontif´ıcia Universidade Cat´olica do Rio de Janeiro, Brazil Andreas Herzig University of Toulouse, France PascalHitzler Wright State University, USA Eyke Hu¨llermeier University of Marburg, Germany Anthony Hunter University College London, UK Yasunori Ishihara Osaka University, Japan Gyula O.H. Katona Alfr´ed R´enyi Institute, Hungarian Academy of Sciences, Hungary Gabriele Kern-Isberner University of Dortmund, Germany Attila Kiss Eo¨tvo¨s Lora´nd University, Budapest, Hungary S´ebastien Konieczny University of Lens, France Gerhard Lakemeyer RWTH Aachen, Germany J´erˆome Lang University of Paris 9, France Domenico Lembo Sapienza University of Rome, Italy Mark Levene Birkbeck, University of London, UK Sebastian Link VictoriaUniversityofWellington,NewZealand Weiru Liu Queen’s University Belfast, UK Sebastian Maneth NICTA and University of New South Wales, Australia Pierre Marquis University of Artois, France Wolfgang May University of Go¨ttingen, Germany Carlo Meghini ISTI-CNR Pisa, Italy Leora Morgenstern New York University, USA Amedeo Napoli LORIA Nancy, France Wilfred S.H. Ng Hong Kong University of Science and Technology, Hong Kong Dan Olteanu University of Oxford, UK Henri Prade University of Toulouse, France Andrea Pugliese University of Calabria, Italy Sebastian Rudolph University of Karlsruhe, Germany Francesco Scarcello University of Calabria, Italy Klaus-Dieter Schewe Software Competence Center Hagenberg, Austria Dietmar Seipel University of Wu¨rzburg, Germany Nematollaah Shiri Concordia University, Montreal, Canada Gerardo I. Simari University of Oxford, UK Guillermo R. Simari Universidad Nacional del Sur, Argentina Nicolas Spyratos University of Paris-South, France Conference Organization IX Umberto Straccia ISTI-CNR Pisa, Italy Letizia Tanca Politecnico di Milano, Italy Alex Thomo University of Victoria, Canada Kriszti´an Tichler Eo¨tvo¨s Lora´nd University, Budapest, Hungary Miroslaw Truszczynski University of Kentucky, USA Jos´e Maria Turull-Torres Massey University Wellington, New Zealand Wiebe van der Hoek University of Liverpool, UK Dirk Van Gucht Indiana University, USA Victor Vianu University of California San Diego, USA Evgenii E. Vityaev Russian Academy of Sciences, Russia Peter Vojt´aˇs Charles University, Czech Republic Jef Wijsen University of Mons-Hainaut, Belgium Stefan Woltran Vienna University of Technology, Austria Additional Reviewers David Carral Mart´ınez Long Chen Sean Chester Anna Corazza Minh Dao-Tran Michel de Rougemont Wolfgang Dvora´k Ingo Feinerer Alejandro Leonardo Grosso Maria Vanina Martinez Joa˜o Moura Pires Carles Noguera Luigi Sauro Vadim Savenkov Edoardo Serra Maryam Shoaran Cristina Sirangelo Tony Tan Thu Trinh Mars K. Valiev Local Organization Stefanie Jureit Steffen Gaede Kai Jannaschk Hans-Joachim Klein Ren´e Noack Ove So¨rensen Table of Contents Invited Talks Uniform Evaluation of Nonmonotonic DL-Programs .................. 1 Thomas Eiter, Thomas Krennwallner, Patrik Schneider, and Guohui Xiao Foundations of XML Based on Logic and Automata: A Snapshot ...... 23 Thomas Schwentick Regular Articles Inconsistency-Tolerance in Knowledge-Based Systems by Dissimilarities ................................................... 34 Ofer Arieli and Anna Zamansky Revising Belief without Revealing Secrets ........................... 51 Joachim Biskup and Cornelia Tadros More Than the Sum of Its Parts – Holistic Ontology Alignment by Population-BasedOptimisation .................................... 71 Ju¨rgen Bock, Sebastian Rudolph, and Michael Mutter Handling Preferences in P2P Systems............................... 91 Luciano Caroprese and Ester Zumpano Backing and Undercutting in Abstract Argumentation Frameworks..... 107 Andrea Cohen, Alejandro J. Garc´ıa, and Guillermo R. Simari The Impact of Transitive Closure on the Boolean Expressiveness of NavigationalQuery Languages on Graphs........................... 124 George H.L. Fletcher, Marc Gyssens, Dirk Leinders, Jan Van den Bussche, Dirk Van Gucht, Stijn Vansummeren, and Yuqing Wu Using Functional Dependencies for Reducing the Size of a Data Cube... 144 Eve Garnaud, Sofian Maabout, and Mohamed Mosbah Armstrong Databases and Reasoning for Functional Dependencies and Cardinality Constraints over Partial Bags ........................... 164 Sven Hartmann, Henning K¨ohler, Sebastian Link, and Bernhard Thalheim FD Covers and Universal Complements of Simple Projections.......... 184 Stephen J. Hegner