Lecture Notes in Computer Science 2929 EditedbyG.Goos,J.Hartmanis,andJ.vanLeeuwen 3 Berlin Heidelberg NewYork HongKong London Milan Paris Tokyo Harrie de Swart Ewa Orłowska Gunther Schmidt Marc Roubens (Eds.) Theory and Applications of Relational Structures as Knowledge Instruments COST Action 274, TARSKI Revised Papers 1 3 SeriesEditors GerhardGoos,KarlsruheUniversity,Germany JurisHartmanis,CornellUniversity,NY,USA JanvanLeeuwen,UtrechtUniversity,TheNetherlands VolumeEditors HarriedeSwart TilburgUniversity,FacultyofPhilosophy P.O.Box90153,5000LETilburg,TheNetherlands E-mail:[email protected] EwaOrłowska NationalInstituteofTelecommunications ul.Szachowa1,04-894Warsaw,Poland E-mail:[email protected] GuntherSchmidt Universita¨tderBundeswehrMu¨nchen Fakulta¨tfu¨rInformatik,Institutfu¨rSoftwaretechnologie 85577Neubiberg,Germany E-mail:[email protected] MarcRoubens UniversityofLie`ge,DepartmentofMathematics SartTilmanBuilding,14GrandeTraverse,B37,4000Lie`ge1,Belgium E-mail:[email protected] Cataloging-in-PublicationDataappliedfor AcatalogrecordforthisbookisavailablefromtheLibraryofCongress. BibliographicinformationpublishedbyDieDeutscheBibliothek DieDeutscheBibliothekliststhispublicationintheDeutscheNationalbibliografie; detailedbibliographicdataisavailableintheInternetat<http://dnb.ddb.de>. CRSubjectClassification(1998):I.1,I.2,F.4,H.2.8 ISSN0302-9743 ISBN3-540-20780-5Springer-VerlagBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer-Verlag.Violationsare liableforprosecutionundertheGermanCopyrightLaw. Springer-VerlagisapartofSpringerScience+BusinessMedia springeronline.com (cid:1)c Springer-VerlagBerlinHeidelberg2003 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyOlgunComputergrafik Printedonacid-freepaper SPIN:10976067 06/3142 543210 Preface Relational structures abound in the daily environment: relational databases, data mining, scaling procedures, preference relations, etc. Reasoning about and with relations has a long-standing European tradition. Today, there are strong European research groups in the theoretical as well as the applied branches. European research in the field may be divided into three broad areas: 1. Algebraic Logic: algebras of relations, relational semantics, and algebras and logics derived from information systems. 2.ComputationalAspectsofAutomatedRelationalReasoning:decidabilityand complexity of algorithms, network satisfaction. 3. Applications: Linguistics, Psychology, Economics, etc. While there is a wealth of theoretical knowledge to be used, there has been littleinteractionbetweenbasicandappliedresearchinthefield.Forthisreason, a European Concerted Research Action has been implemented, designated as COST Action 274: TARSKI (Theory and Applications of Relational Structures as Knowledge Instruments). The main objective of this book is to advance the understanding of relational structuresandtheuseofrelationalmethodsinapplicableobjectdomains.There are the following sub-objectives: 1.tostudythesemanticalandsyntacticalaspectsofrelationalstructuresarising from ‘real world’ situations; 2. to investigate automated inference for relational systems, and, where possible orfeasible,developdeductivesystemswhichcanbeimplementedintoindustrial applications, such as diagnostic systems; 3. to develop non-invasive scaling methods for predicting relational data; and 4. to make software for dealing with relational systems commonly available. Weareconfidentthatthepresentbookwillfurthertheunderstandingofinterdis- ciplinaryissuesinvolvingrelationalreasoning.Thestudyandpossibleintegration of different approaches to the same problem, which may have arisen at different locations, will be of practical value to the developers of information systems. The first five papers concern the mechanization of relational reasoning. This group of mechanization papers starts with a comparative report on two already existingsystemsbyRudolfBerghammer,GuntherSchmidt,andMichaelWinter. The GUHA article by Petr Ha´jek, Martin Holenˇa, and Jan Rauch refers to the well-developed system in Prague which derives information relations from infor- mation systems and is therefore some sort of a program for relational data min- ing. While there have been extensive studies in automated reasoning for propo- sitional logics, Renate Schmidt and Ullrich Hustadt give a respective overview for modal and description logic reasoning systems. An attempt to develop a for- VI Preface mal basis for theory extraction from relational data guided by some ontology is undertaken by Gunther Schmidt. Pasquale Caianiello, Stefania Costantini, and EugenioOmodeofocusondefinitionalextensionsappliedtorelationalformalisms as a way of overcoming expressive limitations of logical formalisms. The next three papers concern the field of relational scaling and preferences. KimCao-VanandBernardDeBaetsdiscusshowaproperdefinitionofaranking can be introduced into the framework of supervised learning. Agnieszka Rusi- nowska gives an overview of axiomatic and strategic approaches to bargaining problems. Harrie de Swart et al. give an overview of the four major categories of voting procedures and their flaws. The last four papers deal with the algebraic and logical foundations of real world relations. Wojciech Buszkowski presents relational representability results fortheclassesofalgebrasrelatedtotheLambeksyntacticcalculus.IvoDu¨ntsch and Gu¨nther Gediga study modal-like approximation operators determined by binaryrelationsandpresenttheirapplicationstopracticalproblemsthatrequire a qualitative data analysis. Ivo Du¨ntsch, Ewa Orl(cid:2)owska and Anna Radzikowska introduce and study a class of weak relation algebras based on not necessar- ily distributive lattices. Ingrid Rewitzky developed a relational model of pro- gramming languages whose commands may involve both angelic and demonic non-determinism. Referees Ricardo Caferra Roger Maddux Dimiter Vakarelov Jules Desharnais Ewa Orl(cid:2)owska Hui Wang Saˇso Dˇzeroski Irina Perfilieva Michael Winter Marcelo Frias Marc Roubens Gu¨nther Gediga Gunther Schmidt Wendy MacCaull Harrie de Swart Acknowledgements We owe much to the referees mentioned above and are most grateful to them. Jozef Pijnenburg was instrumental in editing this book because of his highly appreciated expertise in LATEX. The cooperation of many authors in this book was supported by COST action 274, TARSKI, and is gratefully acknowledged. Editors Prof. Harrie de Swart, Chair, Tilburg University, The Netherlands Prof. Ewa Orl(cid:2)owska, Institute for Telecommunications, Warsaw, Poland Prof. Gunther Schmidt, Universita¨t der Bundeswehr, Mu¨nchen, Germany Prof. Marc Roubens, Universit´e de Li`ege and Facult´e Polytechnique de Mons, Belgium Table of Contents RelView and Rath – Two Systems for Dealing with Relations ......... 1 Rudolf Berghammer, Gunther Schmidt, and Michael Winter The GUHA Method and Foundations of (Relational) Data Mining ....... 17 Petr H´ajek, Martin Holenˇa, and Jan Rauch Mechanised Reasoning and Model Generation for Extended Modal Logics.......................................... 38 Renate A. Schmidt and Ullrich Hustadt Theory Extraction in Relational Data Analysis ........................ 68 Gunther Schmidt An Environment for Specifying Properties of Dyadic Relations and Reasoning about Them. I: Language Extension Mechanisms ......... 87 Pasquale Caianiello, Stefania Costantini, and Eugenio G. Omodeo Consistent Representation of Rankings................................ 107 Kim Cao-Van and Bernard De Baets Axiomatic and Strategic Approaches to Bargaining Problems ............ 124 Agnieszka Rusinowska Categoric and Ordinal Voting: An Overview........................... 147 Harrie de Swart, Ad van Deemen, Eliora van der Hout, and Peter Kop Relational Models of Lambek Logics.................................. 196 Wojciech Buszkowski Approximation Operators in Qualitative Data Analysis ................ 214 Ivo Du¨ntsch and Gu¨nther Gediga Lattice–Based Relation Algebras and Their Representability............. 231 Ivo Du¨ntsch, Ewa Orl(cid:1)owska, and Anna Maria Radzikowska Binary Multirelations............................................... 256 Ingrid Rewitzky Author Index ................................................. 273 RelView and Rath – Two Systems for Dealing with Relations Rudolf Berghammer1,(cid:1), Gunther Schmidt2,(cid:1), and Michael Winter3,(cid:1) 1 Institut fu¨r Informatik und Praktische Mathematik Christian-Albrechts-Universit¨at zu Kiel 24098 Kiel, Germany 2 Fakult¨at fu¨r Informatik Universit¨at der Bundeswehr Mu¨nchen 85577 Neubiberg, Germany 3 Computer Science Department Brock University St. Catharines, Ontario, Canada, L2S 3A1 Abstract. In this paper we present two systems for dealing with rela- tions,theRelViewandtheRathsystem.Afterashortintroductionto bothsystemsweexhibittheirusualdomainofapplicationbypresenting some typical examples. 1 Introduction In the area of logical reasoning, people began soon to look for subsets easier to handlethan,forexample,fullpredicatelogic.Thisattemptresultednotleastin relational reasoning. Already as early as 1915, Leopold Lo¨wenheim postulated that one should resort to reasoning with relations in the “Gebietekalkul”, and should “Schro¨derize” all of mathematics. This approach is certainly burdened with a loss in expressiveness. Nevertheless, such a loss has been accepted in the past by many scientists, as everything looks much simpler and it does not deteriorate expressiveness too much. Whenworkingwithrelationstoday,oneusuallyasksforadditionalcomputer aid.Threesystemswithquitedifferentapproacheshavebeenproposedfromour groups the last years. First, there may be just a specialized support in formula manipulationasinRalf(see[7,8]),amendedevenbysomeautomatedfeatures. A second approach is completely “on the model side” as with RelView. Here, instead of working with binary predicates that may result in true or false, one works with Boolean matrices. This is a paradigm shift allowing to incorporate techniques known from linear algebra. In the RelView system this has been elaborated in great detail to the extent that now something is available which might be compared to a “numerics package” – this time however for relational algebra. Thirdly, one may remain on the syntactic side, still avoiding to work (cid:1) Co-operationforthispaperwassupportedbyEuropeanCOSTAction274“Theory and Applications of Relational Structures as Knowledge Instruments” (TARSKI). H.deSwartetal.(Eds.):TARSKI,LNCS2929,pp.1–16,2003. (cid:1)c Springer-VerlagBerlinHeidelberg2003 2 Rudolf Berghammer, Gunther Schmidt, and Michael Winter in a model. This means concentrating solely on the algebraic rules valid in the relational fragment. This characterizes the Rath approach. Logical reasoning is facilitatedsincetheRathsystemoffersprecisetypecontrol.Negation,e.g.,need not be avoided, as due to the type restriction no unacceptably large result will showup.Rathalsoworksifsomeoftherulesofrelationalgebraareabandoned focusingonDedekindcategories,divisionallegories,etc.Allthecommonaspects are handled simultaneously. Considered in the context of the newly founded COST action 274: TARSKI, all systems seem extremely well-suited to fostering mechanization. Given the observationthatmanypeoplekeepinventingideastocopewithrelationalstruc- tures arising around real-world phenomena, there is always the task to study whether these ideas are really helpful – whether they really work. The systems offer detailed computer help in different directions. Here, we exhibit in which way they may be used. Since Ralf is currently not maintained, we concentrate on RelView and Rath. There is however a lot of work going on to further mechanize any form of work with relations. On the one hand side, a successor of RALF is currently under construction. On the other hand side, methods to decompose relations with respect to different criteria have been developed recently [14]. 2 Relation-Algebraic Preliminaries In this section, we briefly introduce the basic concepts of relation algebra, some special relations, and some relation-algebraic constructions. For more details concerning the algebraic theory of relations, see e.g., [4,13]. Given non-empty sets X and Y, the set of all (set-theoretic or concrete) relations with domain X and range Y is denoted by [X↔Y] and we write R : X↔Y instead of R ∈ [X↔Y]. If X and Y are finite and of cardinality m and n, respectively, then we may consider R as a Boolean matrix with m rows and n columns. This matrix interpretation is well-suited for many purposes. Therefore, in this paper we frequently will use matrix concepts and notations also for relations. Especially, we will speak of rows and columns, and we will denote membership by Rxy instead of (x,y)∈R. We assume the reader to be familiar with the basic operations on relations, viz. RT (transposition), R (negation), R ∪ S (union), R ∩ S (intersection), RS (composition), R ⊆ S (inclusion, subrelation test), and the special relations O (empty relation), L (universal relation), and I (identity relation). With the set- theoreticoperations ,∪,∩,⊆andtheconstantsO,Lsuchrelations,respectively Boolean, matrices form a complete Boolean lattice. Further well-known laws for operations on relations are, for instance: RTT =R Q(R∩S)⊆QR∩QS (RS)T =STRT The theoretical framework for such laws to hold is that of a relation algebra. First, such an algebraic structure is a category. I.e., there is a class of objects; foreverypairA,BofobjectsthereisaclassRAB ofmorphisms,andforalltriples RelView and Rath – Two Systems for Dealing with Relations 3 RAB, RBC, RAC there is a composition from RAB ×RBC to RAC such that associativity holds and for all RAB there exists precisely one left identity from RAA and one right identity from RBB. The morphisms are called (abstract) relations and for their composition and the identity relations we use here the same notation as for concrete relations. However, this category is extended by a transposition operation mapping relations from RAB to RBA, where we use again the notation of the concrete case. Furthermore, the following properties are demanded to hold: 1. Every class RAB is a complete Boolean lattice with the usual operations , ∪, ∩, the ordering ⊆, and the least (empty) relation O and greatest (universal) relation L. 2. For all relations Q ∈ RAB, R ∈ RBC, and S ∈ RAC the following so-called Schr¨oder equivalences hold: QTS ⊆R ⇐⇒ QR⊆S ⇐⇒ SRT ⊆Q (1) Often, in particular within the RelView system, the following so-called Tarski rule is required as a further axiom; it is strongly connected to a gen- eralization of the notion of simplicity known from universal algebra: LRL=L ⇐⇒ R(cid:8)=O (2) NotethatforR∈RBC intheequalityof(2)thereoccurthree–possibledifferent – universal relations, viz. from RAB and RCD on the left-hand side and from RAD on the right-hand, which all are denoted by the same symbol. Let R be a (concrete or abstract) relation. Then R is called univalent (or functional respectively a partial mapping) if RTR ⊆ I, and total if RL = L. As usual, a mapping is a univalent and total relation. Relation R is called injective ifRT isunivalentandsurjective ifRT istotal.Abijective relationisaninjective and surjective relation. Now, let R in addition be homogeneous, i.e., a relation for which the specific product RR exists. (In the abstract case this is equivalent to R ∈ RAA and in the concrete case this is equivalent to R:X↔X.) Then R is called reflexive if I ⊆ R, transitive if RR ⊆ R, and antisymmetric if R∩RT ⊆ I. A partial order is a reflexive, antisy(cid:1)mmetric, and transitive relation. The transitive closure of R is defined as R+ = Ri, where R0 =I and Ri+1 =RRi for all i∈N. Using i>0 R+,thereflexive-transitiveclosureR∗ ofRmaybedefinedthroughR∗ =I∪R+. If R+ ⊆I, then R is said to be acyclic. A relation v with v = vL is called a (row-) vector. In the case of a concrete relation v : X↔Y this condition means that an element from X is either in relation to none of the elements or to all elements of Y. Hence, v equals a Cartesian product X(cid:3)×Y, where X(cid:3) is a subset of X. As for a concrete vector the range is without relevance, we consider in the following frequently vectors v : X↔1 with a singleton set 1 = {⊥} as range and write then vx instead of vx⊥, i.e., suppress the second index. Such a vector v may be considered as a Boolean matrix with exactly one column, i.e., as a Boolean column vector. It describes the set X(cid:3) ={x∈X |vx}.