Posts Tagged ‘modal logic’

A note on distributive and modular lattices

No Comments »

I’ve been working a little with an old friend, modal logic, this weekend. This digressed into a study of lattices and Boolean algebras, so I thought I would write up some of my observations for archival. Also, I just like to say “lattice”.

Smock

If you know anything about lattices, you will probably find this stuff trivial. If you don’t know anything about lattices, a free and much better introduction can be found in A Course in Universal Algebra.

Definition: A distributive lattice is a lattice which satisfies the distributive laws:

D1: x \land (y \lor z) \simeq (x \land y) \lor (x \land z)
D2: x \lor (y \land z) \simeq (x \lor y) \land (x \lor z)

Actually, it can be shown that a lattice satisfies D1 iff it satisfies D2.

Definition: A lattice L is said to be modular if the modular law holds:

M : x \leq y \Rightarrow x \lor (y \land z) \simeq y \land (x \lor z)

Lemma: The modular law for lattices is equivalent to the identity

 (x \land y) \lor (y \land z) \simeq y \land ((x \land y) \lor z)

Proof
Assume that the modular law holds and consider the expression y \land ((x \land y) \lor z). Since x \land y \leq y we can apply the modular law to infer that y \land ((x \land y) \lor z) \simeq (x \land y) \lor (y \land z).

Now, assume that the identity holds and that x \leq y for some x, y, z \in L. Then x = x \land y so

x \lor (y \land z) \simeq
(x \land y) \lor (y \land z) \stackrel{\dagger}{\simeq}
y \land ((x \land y) \lor z) \simeq
y \land (x \lor z),

where the identity was used in \dagger. Thus, the modular law holds.\Box

Theorem: Every distributive lattice is modular.

Proof
Assume that x \leq y for some x, y, z \in L where L is a distributive lattice. Then y = x \lor y so
 x \lor (y \land z) \simeq (x \lor y) \land (x \lor z) \simeq y \land (x \lor z)

where we have made use of D2. The desired result now follows from the lemma.


Building the Mulgara Semantic Store

No Comments »

Mulgara is an RDF datastore, that is, it is a database specifically designed for storing RDF data (triples). RDF is a W3C recommendation for describing facts about all sorts of resources. A very readable introduction to RDF is the W3C Recommendation RDF Primer.
I happened upon the Mulgara project last week, when I was surfing for articles on modal and description logics and the semantic web. I found the blog of Paul Gearon to be very interesting. Paul is the lead developer of Mulgara and as such blogs a lot about Mulgara. After listening to a few podcasts on the Nodalities blog I decided to have a go at building and toying with Mulgara. This is an account of my experiences building the Mulgara project.

You may find the authoritative (and updated)  Mulgara installation guide here.

Preparations

Installing Eclipse

Go to www.eclipse.org to download the “Eclipse IDE for Java Developers” bundle.
I downloaded a ZIP file for Windows and extracted the contents to my Program Files folder and hit eclipse.exe.
The first time Eclipse starts it asks you where you want to place your workspace. The workspace is a location on disk much like the default Projects folder of Visual Studio. I accepted the default location, marked “Use this as default location and do not ask me again” and hit OK.

Getting the source code

I went to http://www.mulgara.org/download.html, downloaded mulgara-2.0-alpha-src.zip and unzipped it to C:\semantic web\Mulgara Source.

Installing the correct version of Java

My machine was equipped with Java SE 1.6, but Mulgara only supports 1.5, so I had to go to Sun’s website to get the Java SE Development Kit 5.0.
I now had both Java 1.5 and 1.6 installed. To have 1.5 chosen by default, I added the environment variable JAVA_HOME and had it point at C:\Program Files\Java\jdk1.5.0_15. I also set up the environment varialble MULGARA_HOME and pointed it to the place where I had placed the Mulgara source code, in this case C:\semantic web\Mulgara Source\mulgara-2.0-alpha. After having verified that these environment variables had taken effect, it was time to build the source.

Building the project

In my command prompt I went on to the %MULGARA_HOME% directory and executed the command

build -projecthelp

Wohooo! The first sort of ‘interaction’ with the project :-) Out comes a long list of build targets. Next, I executed

build.bat clean dist,

the compiler did its thing and presto! After 5 minutes and 25 seconds I was informed that “BUILD SUCCESSFUL”.
To have the Eclipse IDE perform dynamic compilation, you have to generate a number of files. Thus, next I executed

build ideSupport

When the build process completed, I generated the javadoc (build javadoc). This was a lengthy process, so I took the opportunity to piss about on Facebook. Up until now, it had been a smooth ride. However, after a while, the javadoc process aborted abruptly:

[javadoc] C:\semantic web\Mulgara Source\mulgara-2.0-alpha\src\jar\sparql-interpreter\java\org\mulgara\sparql\SparqlIn
rpreter.java:69: warning - @param argument "graph" is not a parameter name.
[javadoc] java.lang.OutOfMemoryError: Java heap space

I don’t expect to find the time to dive into the source code any time soon, so I decided to ignore this for now.

Building the server and the shell

Before building the server and shell artifacts it is recommended that you configure the logging framework, that is, the log4j appender. However, the clock had passed midnight, so I decided to go with the default settings for now.
Actually building the server and shell, thereby creating the files mulgara-2.0-alpha.jar and itql-2.0-alpha.jar files in the %MULGARAHOME%\dist directory, was just a matter of executing


build dist

Yet again, the compiler didn’t bat an eyelash and everything worked out nicely, BUILD SUCCESSFUL. Wow! At this point I was genuinely impressed. I’ve got to admit that, since it’s been years since I’ve done any Java development, I had anticipated having to fiddle with the environment, dependencies and the like for at least a couple of hours. Kudos to the Mulgara team :-) OK, so I had been waiting for this all weekend and I was pretty excited, so after a bit of air-drumming (I was listening to this excellent record at the time), crotch-grabbing and flexing of the biceps, I fired up the iTQL shell:


java -jar %MULGARA_HOME%\dist\itql-2.0-alpha.jar
and I was greeted by the shell:

Whew!

I still don’t know much about Mulgara, but I’ll continue to play around with it and post my findings in later installments of what I expect to be a series of posts on Mulgara. 

Time for bed…