Help with Relation Algebra

[pepsipwns]

Hello there, I'm new to this forum, but I'm pretty desperate with what I'm doing.
I'm in 3rd year of university studying software engineering, and the last time I touched java was in 1st year when we were doing simplistic things like Hello World, and making flag shapes etc.
After 2 years of C# we suddenly have switched back to java, and I'm supposed to know what I knew in C# in java... I know its not that different.. but Its still very challenging for me..

Anyway, I've been given some coursework and I'm really struggling with it. I've been given a class 'Relation' which is somewhat unefficient, and I've been told to recreate this class using some algorithms I've learnt (I can only imagine hashmapping or tree's) but I really don't know how or where to start... Here is the class I've been given: [Java] import java.util.*; import java.io.*; public class Relation { ArrayLi - Pastebin.com

I appreciate any help where possible.
Thanks in advanced.

[KevinWorkman]

If you want help, I suggest you not waste time complaining about your situation. Plenty of people learn without the aid of a teacher, fellow students, teachers, books, or any of the other perks you get from school.

Instead, post an SSCCE that demonstrates one problem at a time, ask a specific technical question, and we'll go from there.

[pepsipwns]

Ok sorry if I hit a nerve by mentioning university, the question isnt exactly simple as I'm really unsure of a lot of what I am suppose to be doing.
If I would make the question as simple as possible I guess it would be:
How can I make this class more efficient by using hashmapping?

[KevinWorkman]

I am behind a firewall that doesn't allow me to go to sites like pastebin, so I'm not sure how to help you. That's one reason we ask for an SSCCE. It's also going to depend on which algorithms you've learned, since we don't know that either.

But generally, you'll probably want to look for places in the code where you're taking a lot of steps that you could do in fewer steps using a different algorithm or data structure. One example might be searching through a List to find an Object that contains a specific ID, which can be improved by using a map of IDs to Objects. That's just an example though, and the specifics are going to depend on your code and what you've learned so far.

[pepsipwns]

Ok thanks for your help, I'll just paste the code here. Its kinda large thats why I didnt do it before.

import java.util.*;
import java.io.*;

public class Relation {

	
	ArrayList<ArrayList<String>> grid;
	int arity;
	
	//Constructor - creates an empty relation
	// arity is the number of columns in the relation
	public Relation(int arity)
	{
		grid=new ArrayList<ArrayList<String>>();
		this.arity= arity;
	}

	//Constructor: reads data from a file.
	//The file should include tab delimited data
	//The number of fields per line must match the arity given
	public Relation(int arity, String filename) throws Exception
	{
		grid=new ArrayList<ArrayList<String>>();
		this.arity= arity;
		BufferedReader fh = new BufferedReader(new FileReader(filename));
		String s;
		int lineNum = 0;
		while ((s=fh.readLine())!=null)
		{
			lineNum++;
			//When split has a negative integer then consecutive tab characters
			//result in a empty string being include in the array
			String f[] = s.split("\t",-2);
			if (f.length!=arity)
				throw new Exception("Invalid data in file:"+filename+":"+lineNum);
			ArrayList<String> r = new ArrayList<String>();
			for(String i : f)
				r.add(i);
			grid.add(r);
		}
		fh.close();
	}
	
	public String toString()
	{
		StringBuffer sb = new StringBuffer();
		for(ArrayList<String> row : grid)
			sb.append(row.toString()+"\n");
		return sb.toString();
	}

	// Join this to relation r
	// Ensure that col1 of this equals to col2 of r
	public Relation Join(int col1, Relation r, int col2)
	{
		return this.Cross(r).SelectEqCol(col1, this.arity+col2);
	}
	
	// The cross join of two relations
	// Every possible combination of rows from the two relations are included
	private Relation Cross(Relation x)
	{
		Relation result = new Relation(this.arity+x.arity);
		for(ArrayList<String> i: this.grid)
			for(ArrayList<String> j:x.grid)
			{
				ArrayList<String> newrow = new ArrayList<String>();
				newrow.addAll(i);
				newrow.addAll(j);
				result.grid.add(newrow);
			}
		return result;	
	}
	
	// Return a filtered relation
	// Only rows where the value of the specified column match the value given
	public Relation SelectEq(int colNum, String val)
	{
		Relation result = new Relation(this.arity);
		for(ArrayList<String> row:this.grid)
		{
			if (row.size()<=colNum)
				System.out.println("Error: "+row.toString());
			if (row.get(colNum).equals(val))
				result.grid.add(row);
		}
		return result;
	}

	// Return only those columns where the two specified columns
	// have matching values
	public Relation SelectEqCol(int col1, int col2)
	{
		Relation result = new Relation(this.arity);
		for(ArrayList<String> row:this.grid)
		{
			if (row.get(col1).equals(row.get(col2)))
				result.grid.add(row);
		}
		return result;
	}

	// Return only those rows where the specified column starts with the given string
	public Relation SelectStartsWith(int colNum, String val)
	{
		Relation result = new Relation(this.arity);
		for(ArrayList<String> row:this.grid)
		{
			if (row.size()<=colNum)
				System.out.println("Error: "+row.toString());
			if (row.get(colNum).startsWith(val))
				result.grid.add(row);
		}
		return result;
	}
	
	public Relation union(Relation r)
	{
		Relation r2 = new Relation(this.arity);
		r2.grid.addAll(this.grid);
		r2.grid.addAll(r.grid);
		return r2;
	}
	public int size()
	{
		return this.grid.size();
	}
}

[KevinWorkman]

That's another reason we ask for an SSCCE- it's not supposed to be an entire program, it's a small example that demonstrates a single problem.

I see a lot of for loops. You might want to go through each of them and figure out if there's a better way to approach the problem.

[pepsipwns]

Ahh.. I think your on to something! Kinda made something click in my head.
Thanks a bunch, let me see if I get anywhere with that.

[pepsipwns]

Hello again, so I've started attempting to remake the Relation class, this time I'm using HashMap instead of ArrayList I've gotten as far as this:

import java.util.*;
import java.io.*;

public class Relation 
{
	HashMap<Relation, String> r;
	int arity;
	
	//Create new relation with 'artity' columns
	public Relation(int arity)
	{
		
		this.arity = arity;
	}
	
	//Create a relation and read in tab delimited data from the file specified
	public Relation(int arity, String filename) throws Exception
	{
		r = new HashMap<Relation, String>();
		this.arity = arity;
		BufferedReader fh = new BufferedReader(new FileReader(filename));
		String s;
		int lineNum = 0;
		while ((s=fh.readLine())!=null)
		{
			lineNum++;
			String f[] = s.split("\t", -2);
			if (f.length!=arity)
				throw new Exception("Invalid data in file: " + filename + "at line: " + lineNum);
			for(String i : f)
				r.put(this, i);
			
		}
		fh.close();
	}
	
	//Select only those rows where the value in column colNum exactly matches the given  val
	public Relation SelectEq(int colNum, String val)
	{
		//Atm return null
		return null;
	}
	
	//Perform the join operation on this relation and relation r. The join condition is that column col1 of this matches column col2 of r.
	public Relation Join(int col1, Relation r, int col2)
	{
		//Atm return null
		return null;
	}


}

At the moment I'm trying to print a Relation I've made, and its just returning Something like "Relation@48586403" the number being a random hash value everytime.
I'm not really sure if what I'm doing is right, or if I'm on the right track at all, but I thought its better to start doing something than sitting doing nothing!
Do you think I'm on the right track? If so do you know how I can make it return the values inside the hashtable instead of what its returning now...

[KevinWorkman]

It sounds like you're trying to print an Object. What is the String representation of that Object? Java doesn't know that automagically, so it simply prints out the stuff you're seeing instead. If you want it to print something else, you have to override the toString() method or call a method that returns a String yourself.

[pepsipwns]

Interesting... In the old relation class they have toString there:

	public String toString()
	{
		StringBuffer sb = new StringBuffer();
		for(ArrayList<String> row : grid)
			sb.append(row.toString()+"\n");
		return sb.toString();
	}

Is that the idea that I want to do also?
How can I do this with a hashmap?

I also tried it like this, but it just printed nothing

		Relation movies = new Relation(6,"tabmovie.txt");
		System.out.println(movies.r.values());

also tried movies.toString() and it came with same result "Relation@randomhashnumber"

[KevinWorkman]

What do you expect it to print out? What is the String representation of a Relation? Where are you telling Java that's what it should print out?

[pepsipwns]

Ok I have simplified everything, I made a new text file just for testing. The text file contains:

1 Test1
2 Test2
3 Test3

I have both my new relation class and old one trying to print out this text file as a relation.
The old relation file (the one given to me as an example) prints it as:

[1, Test1]
[2, Test2]
[3, Test3]

My new one prints only:

[3, Test3]

So I'm assuming its overwriting the info and just printing the last value only. My code looks like this:

	HashMap<Relation, ArrayList<String>> r;
	int arity;
	
	//Create new relation with 'artity' columns
	public Relation(int arity)
	{
		
		this.arity = arity;
	}
	
	//Create a relation and read in tab delimited data from the file specified
	public Relation(int arity, String filename) throws Exception
	{
		r = new HashMap<Relation, ArrayList<String>>();
		this.arity = arity;
		BufferedReader fh = new BufferedReader(new FileReader(filename));
		String s;
		int lineNum = 0;
		while ((s=fh.readLine())!=null)
		{
			lineNum++;
			String f[] = s.split("\t", -2);
			if (f.length!=arity)
				throw new Exception("Invalid data in file: " + filename + "at line: " + lineNum);
			ArrayList<String> v = new ArrayList<String>();
			for(String i : f)
				v.add(i);
			r.put(this, v);
		}
		fh.close();
	}
	
	public String toString()
	{
		StringBuffer sb = new StringBuffer();
		for(ArrayList<String> row : r.values())
			sb.append(row.toString()+"\n");
		return sb.toString();
	}

So I think I'm getting close, I'm basically using a mixture of arraylists and hashmaps now... any idea why its overwriting the info, and how to make it stop?

[pepsipwns]

Bump, edited my previous post

[KevinWorkman]

What are you putting in the map? What is the key? A key can only map to a single value. If that value is a List, mapping another List to it overwrites the first List.

[pepsipwns]

I really dont know... I want the key to be the name of the Relation, but how can I include that?
When creating the Relation "Relation test = new Relation(2, "test");" I want the key to be test, the relations name. I thought thats what it would do when making the key Relation...
I added System.out.println(r); into the while loop, just to try to understand what its doing, and it returned:

{[1, Test1]
=[1, Test1]}
{[2, Test2]
=[2, Test2]}
{[3, Test3]
=[3, Test3]}

So its really weird, I'm kind of confused, why is 'Relation' (the key) the same as the value?

[KevinWorkman]

You need to take a step back and look at exactly what you're doing. Does this line make sense:

r.put(this, v);

You're only ever mapping a single key to different values, which doesn't make sense to me. You say you want to use the name of a Relation as the key, but here you're using an entire Relation as a key.

I really suggest you do some debugging here and take a closer look at what your code is actually doing.

[pepsipwns]

I see what you mean, it doesnt make much sense what I'm doing, I'm kind of lost again, how should I use HashMaps here? :S Am I completely thinking of using them in the wrong area...

[KevinWorkman]

I don't know. What benefit do you think they give you?

[pepsipwns]

They are a lot faster and more efficient than ArrayLists? I just dont know which part of the program they would be most useful at.

[KevinWorkman]

You're comparing apples and oranges. The point is not that one is faster or better than the other. They each do a very different task, so they are better-suited for different problems. If Maps were inherently better than Lists, nobody would use Lists anymore.

The question is, is your task better-suited for the things Lists are good at, or the things Maps are good at? Or maybe a Set or a Tree or a LinkedList or something else? That I can't really help you with, as it's really up to you to decide.