0

I understand a 1-many relationship is most easily represented by the child item having a foreign key reference pointing back to the parent. 

Parent
  - id

Child
  - id
  - parentId // fk

In this case accessing the parent from the child is trivial. Simply do an O(1) access on the parent table.

But how to manage an efficient access of all the children of a parent?

E.g. how is a method like Parent.children() normally implemented in an orm so that it is efficient?

Some things I've considered / tried:

If the parent also had a list of childIds: [], this would work, but then you'd have to insert the childId into the parents childIds after creation. Two operations to create a model seems wrong, even if it get's us O(1) access to the list of child ids.

You could simply loop through all children children.filter(({ parentId }) => parentId === 2) to get the children of here e.g. Parent 2 every tie you want to access all of Parent 2's children. But this is O(n) operations, and becomes inefficient.

Is there some standard way to avoid both these pitfalls? I.e. what is the / are the standard approaches to implementing an orm method that returns the children of a parent model in a 1-many relationship?

Dan
  • 2,830
  • 19
  • 37
  • Please tag with your ORM. Please read & act on [ask], hits googling 'stackexchange homework' & the downvote arrow mouseover text. This is too broad yet is also a faq. Also you don't seem to know what an ORM is, because the whole point of using an ORM instead of a non-relational solution is that one can write such an expression in a non-relational style that doesn't have to be executed via non-relational "loop through all". – philipxy May 21 '18 at 07:07
  • The question was about how this aspect of orm's is generally implemented, I'm not using an ORM, I'm writing my own normalized store and the orm around it. After hours of searching I could not find what principles are generally applied when implementing the forward direction of a 1-many relationship. I understand this question is not extremely well written, but it is a very straightforward question: how are forward 1-many relationship methods usually implemented. – Dan May 22 '18 at 09:10
  • Yes but my first comment still applies. – philipxy May 22 '18 at 11:43
  • Possible duplicate of [What is an ORM and where can I learn more about it?](https://stackoverflow.com/q/1279613/3404097) – philipxy May 22 '18 at 11:46

1 Answers1

0

Based on @philipxy's comments, the best way forwards is to answer my own question, and maybe others can answer it better.

An ORM allows you to declare relationships and methods to get the results of related entity queries, but the query exercised by the ORM is store specific, and that is where it would be made "more efficient". In a SQL store the developer wouldn't normally think about this, the ORM would just run e.g. select * from children where parentId = 2, and the store would make this efficient.

It appears you have a javascript object store. Unless performance is a genuine problem, children.filter({ parentId }) === parent.id is the approach used by redux-orm, and will most likely be adequate given the speed of modern browsers.

For SQL stores, there are probably much lower level approaches to optimizing such queries. For example, if all children were sorted by parentId, more efficient than O(n) algorithms could be used. Some such approaches could apply for javascript object stores also.

In other words using a parentId on the child model results in a filtering problem when going from the 1 to the many.

You have also alluded to the fact that you could represent a 1-many relationship where the parent has the child ids. Given that you would still be faced with a filtering problem in this case if you wanted to go from a child to a parent (find parent where one of it's children has the child id you're after), unless for some reason you plan to go from the parent to children extremely often, but not vice versa, this is probably less appropriate. It doesn't fit so nicely with business problems where the child doesn't meaningfully exist without the parent, e.g. a comment on a post, because storing the relationship in this manner requires the child to exist first.

In short, O(n) looping to implement a 1-many method will take a large n to become a performance bottleneck, and if it does, there are other filtering approaches that are less than O(n). You could explore CS filtering algorithms to understand this further. Also if you are implementing your store, many options are valid, it just depends on your exact case. SQL normally abstracts the algorithms used somewhat, but if you're implementing your own store you need to think about this more carefully based on your cases.

Dan
  • 2,830
  • 19
  • 37